AHC11参加記 「緑コーダーの山登り法による17M点解法」
あいねむと申します。 長期AHCが大好きで、色んな方に取り組んでもらいたい気持ちがあり、少しでもハードルを下げられたらと思い、誠に僭越ながら解説記事を書かせていただきます。
問題
ざっっっくり説明すると、16種類のピースがあるスライドパズルを動かしてできるだけ大きな(=頂点数の多い)木を作ろう！
もし全てのピースをつなぐ木を作った場合、作った早さも得点になるぞ！
最初に浮かんだアイデア
①山登り
空きマスを上下左右に1マス動かすことを1操作と考えると、1操作だけではスコア（盤面がもつ最大の木）が変化しないことが多い
7操作ぐらいずつランダムで動かすルートを100個ぐらい列挙し、木が大きくなるものを選ぶ。(貪欲法)
評価関数がどれだけ遅いか？時間ぎりぎりまで探索する。時間たりなさそうなら盤面を分割して考える？
②自由に操作
例えば葉を外にとか、例えば理想の木を作るとかの目標を決めて、その盤面への操作を求めるまず理想の木を作れる気がしない、そしてその盤面への操作もできる気がしない… ABC224D(うにだよさん解説)を読むも、これが最大100マスあるとなると計算量が爆発するどころじゃない…宇宙爆発待ったなし…
ということで
まずは①山登りの方針で実装してみることにした。
実装
実装が重いことが参加のハードルとなっている可能性があるな、と思いましたのでかなり詳細にgoogle colab上で説明しました。
リンク先の「Open in Colab」から、実際に実行できるはず、、、です！
この記事のメインコンテンツのつもりです。DFSが書けるレベルであれば、理解できるんじゃないかと思います。是非Twitterとかで質問してください！
スコアが改善したもの
【WA】満を持しての初提出
WA！！ひゃっほい！（ターン制限を全く考えていなかった）
【13668040】正の得点GET
Submission #32126657 - AtCoder Heuristic Contest 011
T以上になった時ループを中断するようにして、2回目の提出で正の得点ゲットだぜ！
【13668040 -> 15377134】往復移動を無くした
Submission #32136371 - AtCoder Heuristic Contest 011 ルートを作る際、LRLRLRLR..などの往復移動も候補にあげていたので、元いた場所に戻るルートは作らないようにしました
【15377134 -> 15614987】 木の破壊の許可/非許可のルートを作るようにした
Submission #32139580 - AtCoder Heuristic Contest 011
木の破壊を許可しない、つまり最大の木の頂点を記録して、そこは通らないルートを作るようにしたら、いわゆる局所解にはまった、最大の木に閉じ込められて動けない状態になりスコア改善しなくなった
候補のルートのうち半分を木の破壊を許可、もう半分を木の破壊を許さないルートにして、そのうちスコアがもっともいいものを選ぶようにした
でも、これは最終的には木の破壊を許可するルートだけにした方がスコアがあがった
おそらく、乱数のブレだったんだろう…
【15614987 -> 16401198】 二次元配列を一次元にした
Submission #32154320 - AtCoder Heuristic Contest 011
ありがとう、ゆうさんろんどんさん…
ちょっと日曜までは詳しく言えないんですが、AHC、ゆうさんのおかげでものすごく助かりました！！ありがとうございます！
— ainem (@ainemixion) 2022年6月2日
matrix[x][y] -> matrix[10*x + y]に変更した (ほんとは[N*x + y]なんだけどメモリ使用量に大きな影響なさそうだし、見やすい10倍にした)
【16401198 -> 17384415】ルートの評価
Submission #32191011 - AtCoder Heuristic Contest 011
今まではルートの評価は移動後の盤面の状態だけだったが、ルート自体の評価もするようにした 最後の方、木に囲まれてぐるぐるしがちなので移動の範囲の大きさを評価に入れてみた
この提出を何度も行い、50万点ぐらいの振れ幅があることに気づいた！これは今までの改善の幅ぐらいある…笑 次回からはランダムのシードを固定(note.nkmk.me)して改善したかどうかはっきりさせようと思った
スコアの改善がなかったか、実装に至らなかったもの
ハイパラ調整
ROOT_LENGTH(一度に移動する量) TEST_TIME(ルート候補をつくる量) の値をいじっても、スコアは大きくは改善しなかった iPhoneからでもパラメータ調整はできるので実装の時間とれるときにやる必要なし もう何も浮かばないけど時間はある最終日にはやってもいいかも、でもやるとしたら大量のテストケースが必要 randam.seedを使ってseed値を固定していじらないと意味がない！！
前処理の関数を作る
例えば空きマスを最初に真ん中に寄せるとか まだ実装できないけど葉を端に寄せておくとか 空きマスを寄せるのだけ帰ってからサクッと実装してみたが、ダメ きっと他のアイデアと組み合わせなければ意味がないものなんだろう…
参考にしたもの
診断人さんの焼きなまし法のコツ Ver. 1.3を大変に参考にさせていただきました。百回読みました。
困ったこと
M1Macの罠
ローカルテスタ、全然提出の点数と連動しなくて困っていましたが、ローカルではPythonで回していて、提出はPyPyで回していたので、そのせいでローカルだと全然点数が伸びない、ということが起きていた
よし、じゃあPyPy入れちゃうかーとなりますが、PyPyはM1Macに対応していない（驚愕）
長期AHCだけ他言語使うことを本気で考えた(N回目)
焼きなましたい！
山登りだとおそらく限界がある、焼きなましできる遷移を見つけたい、と日記に毎日書いてあった（笑） 山登りには限界がありそう(上位陣みんな25Mを超えてる→制限ターン以内に木を完成させてる) 今回の方針で焼きなましするには、少しの変更でスコアが下がりすぎる(今までの木を壊してしまう) 焼き鈍し法（状態：盤面 次の状態：ランダムなルート スコア：最大の木の大きさ）をやってみたが、試行回数を増やすために操作回数制限がボトルネックになり、おそらく時間制限前にルート確定してしまい、うまく行かなかった、この遷移だと前半はスコアが上がらないのが当たり前で、後半は大幅にスコアが下がりやすいのであんまり意味がなさそう ツカモさんの記事で言う焼きなまししにくい構造になっていそう
上位陣(現人神たち)の解法をみてびっくり、まさか完成図の方を焼きなましするとは！！たしかに、近傍を作ることができそう。いつか実装してみたい…
振り返り
結果的に最初に思いついたアイデアを改善し続ける形になった 25Mの壁（完成形を作れたかどうか）には気づいていたが、どうしても実装できる気がしなかった 焼き鈍し法の気持ちが少しだけ理解できた（どんなふうにうまくいかないか）
日記の大事さに気づけた。日記を記録せず/読み返さずに熱烈実装！をしていたときはスコアの上昇がほぼなかった 実装しながら考える は私にとっては愚行のようだった。
脳内イメージはあくまでもやもやっとした曖昧なイメージなので、実装に落とし込むには粗すぎる…脳内イメージで完璧に整理がついた、と思った概念をシェーマを書いたり文章で説明しようとするとつまるところがたくさんある。実装はかなり精密な作業なので、いきなり実装、は天才の所業
そんなことわかってはいるんだけどいざ実際、順位表とかツイッタとかビジュアライザを見ると早く提出したい焦りに勝てなくなる…
コメントも大事！！３０分前の自分が何を意図して書いたのかわからないことが多発。コードはあとから微調整がきかない（絡み合っている）意図がわかれば改変もしやすい。むしろ改変しやすい構造で最初から書くのが大事。リーダブルコード読み返そうと思った。 型ヒントは便利 変数名の他にもう一つ情報が増える、しかもエディタにチェックしてもらえる！
でもPythonの場合List[int]とか書くためにはジェネリック型？とかが必要でimportしなきゃないからめんどくさいよね…
Pythonの限界を感じた 手元でテストを実行するときに遅い、コードをわかりやすくするために、たとえば座標などの簡単なものを構造体代わりにクラスで書いたりすると遅くなったりする。
みなさんも是非、私のコードを写経、改変でもいいのでまずは提出してみてください、そしてAHCの喜びを分かち合いましょう！
徹頭徹尾、竜頭蛇尾。
ゼロから始めて楽しく続ける競技プログラミング 〜３３歳、入緑しました〜
自己紹介
どうも、ainem(あいねむ)と申します。
子供の頃からずっとプログラミングに憧れたまま、始められずにいた昭和生まれの社会人です。（chokudaiさんとドンパ*1）
ainem - AtCoder
効率的な学習方法は効率よくレートが上がっている人の記事を参考にしていただくことにして、*3 私は「いかに楽しく競プロを続けるか」にフォーカスして、自分がどうやって競プロを続けてきたかを紹介していけたらなと思いまーす。
はじめの一歩
タイトルに「ゼロから」なんて入れちまったもんで、ちょっとだけ振り返らせてくださいネ
京都大学 プログラミング演習 Python
hdl.handle.net
文法は京都大学の全学共通科目として実施されるプログラミング演習(Python)の教科書を使って勉強しました。
はてブで絶賛されていたので、一ヶ月くらいかけてやり終えました。
やっぱ、京大生と同じことしてるって思うと、誇らしいじゃないですか、ほら。
中にはturtleという描画用のモジュールを使ってお絵描きするパートがあったりして楽しかったですよ。
基本的な文法を学んだ後は、
チェックアイ・オー(おすすめ)
ゲーム感覚で問題を解いていけるサイトですが、 なにより、 他の人のコードへの投票機能 があるところが面白いです。 計算量の改善というより、ヘンテコな実装でACする文化があり、おもしろいです。
ワンライナー(複雑な実装を1行ですませる)もたくさんあり、コードゴルフに役立つかも？ 第一問、aかけるbを実装する問題から、世界中の皆さんのクリエイティビティが爆発しています。(問題に正解するだけならf = lambda a, b: a*bでいける)実例をあげたいところなのですが、コード共有していいか微妙なところなので…みなさんもレッツ登録！
解き進めているうちに、dijkstra法が登場し(しかも難易度easy)、なんじゃこれ？！となり、dijkstraでググったことが、AtCoderとの出会いでした。
アルゴ式
今ならいいサービスがあります。友人に布教するときはまずこのサイトを送ってます。(なお、始めてくれた人はいません。涙) algo-method.com 解説がしっかりしているのもグッドポイントなんですが、一つの概念に対する演習量が多い！ちょっとずつステップアップさせてくれる！ とくに動的計画法（DP）を学ぼうとEducational DP Contest - AtCoderに挑戦して挫折した人なんかは、先にアルゴ式をやってみるといいと思います！
レートをあげるには
色変記事の需要ってなんだろう、と考えた時、「どうやってレートを上げたんだろう？」に興味がある人が多いんじゃないかと考え、私のレートの上げ方、を伝えたくてこの記事を書こうと思ったわけですが、 このツイートがすべてでした
競プロ、とりあえず続けていればちょっとずつでも強くなれるので、成長がゆっくりな人はいろいろ寄り道していればよさそうな気がした
— まぐふらい (@0x3b800001) 2022年4月11日
私にとってレートをあげるとは とにかく問題を解くことです*4 継続継続です、
継続は力なり
です。 しかしですね、継続が難しいからこそ、そんな格言が生まれたわけで、*5 どうやって継続できたか？を考えた時、私の答えが「プログラミングを楽しむ」ことでした。
1. 問題を解いて楽しむ
1-1. 大物を狩る
自分の知識を組み合わせて、コンテスト本番では時間が足りず解けないような大物の問題を解く時って楽しいですよね。私が競プロやっていて一番楽しい瞬間かもしれません。真っ先に思いついたし。
印象に残っている２問です。
1-2. 問題の解説を書いてみる
一つの問題にずっとへばりつくのが楽しいと言ったその口で、正反対の事を言います。３０分くらい悩んでも方針の立たない問題は解説ACした方がいいです。解説ACって悔しいけど、"解説AC力"*6という能力を育ててあげないと解けない問題が山積みになり、詰んでしまいます。
でもでも、解説ACってなんかもったいなくないですか、私はもったいなく感じます。そこで、問題を解いた後にもその問題を楽しむ方法を紹介します。解説を書くことです。
寒色の教プロerが解説を書くことに関しては賛否あるようですが、私個人としては、色んな人の書く解説を読んだほうが理解が進むことが多いので、解説記事！！ウェルカム！！！という気持ちです。
あとは単純にスライド作るのが好きなので、作っていてテンションがアガります。
ABC237E Skiing 解説スライド作りました！ pic.twitter.com/fg2saMRXcQ
— ainem (@ainemixion) 2022年2月2日
ABC077_C Snuke Festivalの解説を書いてみました。
— ainem (@ainemixion) 2022年1月14日
後学のために改善点を指摘していただけると幸甚に存じ上げ申し上げのアゲアゲです。https://t.co/Oowply9M8j pic.twitter.com/zIzAoCwRFr
1-3. 継続自体を楽しむ
1-4. スマホコーディング
あなたを教プロ漬けにする秘訣、スマホコーディングです。辞書登録使えば意外となんとかなります。*7 主に通勤電車で精進しています。（厳密にはスマホだけでなくipad miniちゃんも使います） atcoderにはコードテストという便利なものがあり… AHCのときなんかは www.megasoft.co.jp このソフトを使ってdropboxでスマホとPCでコードを共有しています。
1-5. 良き問題集たち
Boot camp for Beginners
ほぼ難易度順に初心者向けの問題が100*3で300問。
え、これむずすぎない！？っていう問題が1, 2問紛れ込んでいますが、それは飛ばして進んでいいと思います。みんな躓く問題です。たぶん。この円グラフが埋まっていくのが楽しいんですよ。ダブルオーみたいで。(円3つだけど。)
競プロ典型 90 問 これにリアルタイムで参戦できたのはかなり大きかったです。朝問題を見て、1日考えて、夜に答え合わせの毎日。本の出版、楽しみだあー！
AtCoder Problems Recommendation Easy 落ち込んだ時、自分のレートに合わせて、サクッとやっつけられるちょうどいい難易度の問題を提案してくれます。神です。ただしAGCの灰Diffは灰Diffではない
1-6. コンテストに出る
私の中ではこのぐらいの順番に来ました。レートに縛られないように楽しもう！が趣旨なので…でも、レート上がるとやっぱ楽しいですよね。あとは、コンテスト時間ギリギリまでパソコンに向かっているの、好きです。鍵垢の方が、「コンテストをしゃぶりつくす」と表現していましたが、まさにそうですよね！
まぁ、撤退！！酒飲む！！！！！！！！！！！もめっちゃ楽しいです。
ところで、私はウイスキー、クラフトビール、ワインが好きで、もっと詳しく話すと、アイラモルト、セゾン、ブルゴーニュ（赤白どっちも）が好きです。唐突ですが自慢させてください。私はウイスキーのメッカ、アイラ島と、クラフトビールの聖地、ポートランドに行った事があります。どちらも最高でした…
2. 人とつながる
2-1. 競プロ道場鯖（おすすめ）
物理好きさんによる教プロ道場鯖。 自分のレベル帯に合わせたグループに入り、同レベル帯の人たちと一緒に問題を解いていきます。discordの機能のおかげでネタバレ対策もばっちし。コンテスト後の振り返りボイチャや、ライトニングトーク会なども開催されてます！*8問題を解いている時、ヒントだけちょっぴり欲しいこと、ありますよね？そんなときこの鯖のみなさんがあなたを助けてくれます。【ゆるぼ】Discord競プロ道場の鯖主やってます！
— 物理好き (@butsurizuki) 2021年12月31日
練習内容は以下です！
灰～青向け:
主に僕が何らかのテーマで定期的に問題セットを組んで、それに対して色々と話しながら理解や知識を深めていく
暖色向け:
定期的にばちゃをやったり、テーマ決めて練習します
参加希望はリプ！DMでリンク送ります！
2-2. Twitter
問題解いていて困ったときに限らず、みなさん優しくてさっと駆けつけてさっと的確なリプを飛ばしてくれます。 そして、逆に誰かのヘルプに応えること、それ自体が勉強になりますし、楽しくないですか？私はお節介かもな…なんて思いながら果敢に突撃します（自分より上の色の人のヘルプでも）迷惑だったらすみません…
2-3. AtCoder Find Rivals
自分と同じぐらいのレート遷移の人と繋がりたくありませんか？そんな要望を叶えるWebアプリです。私のライバル、ネギ坊主さんが作りました。こっからツイッターフォローをよくします。私もこういうの作りたい。頑張りたい！！
3. 寄り道を楽しむ
3-1. AHC
果たして寄り道なのかという疑問がありますが、AtCoder Heuristic Contestです。最初の提出に至るまでにそびえ立つ高いハードルがあるんですが、日常ふとした瞬間にアイデアが閃くあの瞬間とそれを実装に落とし込んだ時にスコアが上がる瞬間の気持ちよさはもう、なんといったらいいか、脳汁出ます！！！
3-2. いろいろなコードに触れる
同じ目的を達成するコードでもいろんな書き方があって、数字で競うshortest, fastestに限らず、計算オーダーは変わらないのに実行速度が違うとか、読みやすいかどうか、え、これでこんなことできるの、なんてそんなことを突き詰めるのも楽しいですよね。たぶん、この楽しみはライブラリ整理に行き着くんだと思うんですが、デスクトップ散らかりっぱなし人間の私には、ちょっと無理でした、作っても失くす。
まさにcheck.ioはいろんな実装が見れて楽しいので、是非！！！
いつかライブラリを整理できるような大人になったなら、Library Checkerでチューンナップするのが夢です
3-3. プログラミングをやってみよう！
なんだか本末転倒な気がしますが、競プロの息抜きに日常に潜む退屈なことをPythonにやらせてみたりするといいですよ。
- RPA(マウスとキーボード操作の自動化)
- 在庫管理(ノーコード開発-appsheet)
- シフト表の自動計算(VBA)
などなど。 なんか記事の文字数が多くなりすぎちゃって、この辺は端折りますがいつか記事にしたい気持ちを再確認できたことがよかったです。
あ、締めの一言とかはありません、徹頭徹尾竜頭蛇尾が座右の銘なので…
*1:ドンパ:北海道の謎の言葉で同級生の意。https://twitter.com/chokudai/status/1372185472634482693?s=21
*2:奥さんは「なにこれ数学じゃん…」と言って辞めてしまいました。他に試みた趣味は３Dプリンタ（初期投資大きすぎて挫折）FF14（奥さんが「戦うのはちょっと…」で挫折）など
*3:AtCoder clans : @hiro_hiroさんによる色変記事まとめhttps://kato-hiro.github.io/AtCoderClans/milestones
*4:https://twitter.com/chokudai/status/1506172842236588035?s=21社長も言ってました。「たくさんやれ」って。
*5:継続ってムツカシイ。最近、RPGとかも最後までクリアできなくて…
*6:解説ACに慣れてないと、解説読んでもACできなくないですか？私の造語です
*7:”えぬ”→"n = int(input())" ”まぷ”→"a, b = map(int, input().split())"など
*8:音声コミュニケーション禁止なので私は参加できませんが…
*9:夫婦の時間を大事にするため、夜に長時間拘束されるコンテストに出場していいのは月に一回まで
