AtCoder Heuristic Contest 003

AHC003楽しかったです。本当に。結果は163位で、自分なりに実力を出し切った感はあります。

最近競プロをやっていてレートが上がらず精神的に苦しい、という方をちらほら見かけます。僕もその一人です。

そんな方達にこそ、AHC(特にマラソンコンテスト)はおすすめなんじゃないかな、とふと思いました。理由は以下です。

• ABC/ARC/AGCよりまったりと取り組める(考える問題はたった1問。コンテスト期間が1週間なら、お風呂とか布団の中でのんびり考えてもOK)
• WA、TLEしてもペナルティがないし失敗してもレートが下がらないので、改善案思いついたらとりあえず提出して実験、が気軽にできる
• 結果が単純な正解、不正解じゃなくて細かく刻まれたスコアで返ってくる(英検とTOEICみたいなもの)ので、一度ACできれば以降は不正解による心理的ダメージを受けにくい
• 周囲にも競争相手はいるけど、それよりまず越えるべきは自分！自分のベストスコアが対戦相手になるので、比較的他人に目が行きにくい
• 数学力が無くてもある程度雰囲気で戦える(上位陣はやっぱり数学強いですが…)

ただ、仮に自分が低順位の時やそもそもACができない時でもAHC楽しい！って胸を張って言えるかは、引き続き要検証ですね。

さて、僕がAHCに挑戦するのは今回のAHC003で2回目です。1回目はAHC002で4時間のコンテストだったので、1週間のマラソンコンテストは今回が初めてですね。 せっかく楽しく取り組めましたし、コンテスト中に記録していた思考過程とスコア推移を後々の参考に残しておこうと思います。

問題概要

問題本文はこちら。

Shortest Path Queriesという問題名ですが、ざっくり言うと道案内アプリ(カーナビみたいなイメージ)の精度をどれだけ上げられるかを競うものです。

30×30のグリッド状道路網があって、入力にスタート地点とゴール地点が与えられるので、ゴールまでの最短経路を出力するのが与えられたタスクなのですが、なんと初期状態ではどの道を選ぶとどのくらいの距離になるのか何も分かりません(グラフの重み情報が皆無)。ただし、自分が選んだ経路だと実際どのくらいの距離だったかを教えてもらえるので、1000回道案内を繰り返す過程で徐々に道案内の精度を上げていってね、という話です。実行時間制限が2秒なので、いくらでも学習に時間をかけられる、というわけでもないのがミソです。

自分が得られる得点の計算は、これもざっくり言うと自分が選んだ経路長が最短路長に近ければ近いほど(短いルートを選べば選ぶほど)得点が高くなります。また、後半の道案内ほど得点比率が高くなります。

具体的なイメージは下図をご覧ください。これは僕の最終的なプログラムで道案内した様子を公式のビジュアライザで図示したものです。緑の線が最短路で、茶色の線が自分が選んだ経路です。図の下の方に赤い点が1000個プロットされてますが、これは各回の(最短路長)/(自分が選んだ経路長)になっていて、赤い点が上の方にプロットされているほど得点が高いです。最初は赤い点がばらけていますが、徐々に上の方に固まっていくのが分かるかと思います。

以下では、自分がどのようにプログラムを改善していったか、思考と実験の過程を記録しました。

1日目(2021/5/22)

まず問題文を眺めて、大方針を立てました。二次元グリッド版のダイクストラ法使えば最短経路問題は解けるから、あとはいかにして1000ループ中でグラフの各辺の重みを更新していくかが肝だと考え、まずはグリッド版ダイクストラのお勉強をはじめました。具体的にはPaizaラーニングにちょうどいい問題セットがあったので、使わせて頂きました。

また、対話型の問題に取り組むのが初めてだったので、flushの使い方も調べました。Pythonだと、print(output, flush=True)みたいに書くだけでOKなので楽チンですね。

あと対話型だと手動のローカルテストがやりにくかったため、途中からRustを自分のマシンにインストールしてローカルテスト環境も構築しました(試行錯誤がやりやすくなるのでこれはマラソンコンテスト取り組むなら絶対にやった方がいいと思います。できれば自動テストスクリプトの作成も)。

ちなみに入力生成方法は数式が多くて脳が理解を拒否したのでスルーして、マンハッタン距離が極端に短い経路はあり得ないというクソ浅理解だけで実装に進みました。この怠慢が大きな損失を生むとも知らずに…

最初の戦略

• まずグラフの各点(辺ではない)に重みを持たせて最初は全部1で初期化
• グラフの重み更新は、(入力として受け取った真の経路間コスト=actual cost) ÷ (自分が選んだ経路のステップ数(例えば”DDLLDDD”なら7)=len(path))　を各点に与える重みとして毎ループ更新
• ダイクストラを使って最短経路復元、出力

以上を実装して提出すると、最初の2回はWA。原因が分からず埒が明かなかったのでローカルテスタをインストールして試してみると、「グリッドの外にはみ出してるよ！」というありがたい忠告を頂戴します。原因は問題文をちゃんと読まずに、1-indexだと勘違いしていたことでした。「普段AtCoderさん1-indexやん…」と思いながら0-indexに修正し、AC。記念すべき初スコアは77497493710点でした(コード)。

改善(辺に重みを持たせる+重み更新式の変更)

• グラフの各点に重みを持たせるのではなく、各辺に持たせる(各点に対して、どの方向(U,R,D,L)からその点に入ってきたかで重みを管理)ように変更
• グラフの各辺に与える重みを、(現在の重み + 新しく求めた重み)/2で調整していく方式に変更

⇒86780317507点(コード)

2日目(2021/5/23)

考えたこと

• 1000回のループ全てで同じ重み更新式を使うのではなく、ループの途中で更新式を変えてみてはどうか。最初は情報が少ないので選んだ経路に対して得られたactual costの信頼度を高めにして、グラフ全体の重みが整備されるにつれ現在の重みをベースにしてactual costを通った辺に振り分けられないか？⇒成功
• ループの各段階(例：250、500、750)で、グラフに与える重みに補正パラメータをかけてみてはどうか？例えば最初の250ループでは計算した各エッジの重みに対して補正パラメータ(0.95~1.05)を乗算して値を散らして、ループの後半に行くに従い補正パラメータの振れ幅を小さくしていくというもの。⇒失敗

改善(ループの途中でグラフの重み更新式を変更)

• 最初の250ループは単純にactual cost/len(path)を選んだ経路に付与。残りの750ループでは選んだ経路において各辺が持つ現在の重みの比率に応じてactual costを按分したweighted costで更新(この時点の実装だと250ループ目で変更がベストだった)

⇒89446267313点(コード)

更に考えたこと

• 1000億点がMAXスコアで、それに対して現状900億点弱。ビジュアライザを使ってスコア低下の要因を考えていると、初期(～500ループ)のスコアにばらつきが見られる
• 理由を考えると、最初全ての重みが1の状態からスタートして、徐々に通った経路の重みが更新されていくので、ダイクストラは重みが1の未使用ルートを優先的に使うはず。ということは、クネクネと曲がるいびつなルートになりがちで、そのようなルートはactual costとの乖離が激しいのでは？ループの初期段階では進める方向を制限してはどうか？
  ⇒ちなみにこの頃は問題文を誤読してました。自分が出力した経路(RRDDDRRRDDとか)に対して、真の最短経路を選んだ場合のコストが毎回返ってきてると思ってました。真の最短経路が返せるならAHC003の問題設定が破綻しますね…まぁこの改善案は良い方向に働いたので結果オーライですね…

改善(初期段階で進める方向の制限)

• ループの前半(～500ループ)では、スタート座標とゴール座標の位置関係を基に、進んでいい方向を決めることにした(例：ゴールがDR方向ならDR方向だけに進める、ゴールがR方向ならURD方向だけに進める)

⇒90816854383点(コード)を達成。900億点越えて喜ぶ。

3日目(2021/5/24)

考えたこと

• トップランカーたちがほぼ満点のスコアを出しているのを見て、やはりいかにループの早い段階でグラフ全体の尤もらしい重み付けをするかが肝だと確信
• アイデア1：グラフの重みを最初1で初期化しているがこれは根拠のない数字なので、早い段階で尤もらしい重みに更新できないか？⇒成功
• アイデア2：各ループで与えられるスタート、ゴール座標とactual costを保持しておき、ループがある程度進んでグラフの重みが整備された後にもう一度過去のデータを用いてグラフの重みを補正してはどうか⇒この時点では実験するも失敗

改善(ループ初期段階でグラフ全体の重み更新)

• 最初の100ループ分のactual cost/len(path)の平均を計算しておき、ループが100回目に突入した段階でグラフ全体の重み付けを更新する。値が1(未更新)の辺は単純に上書きし、そうでない辺(既に通った辺)は、((現在の重み) + (actual cost/len(path)の平均)) / 2 で計算
• 上記アイデアの実装に加え、2日目に実装した「グラフの重み更新式の変更」を、100ループ目で切り替えるようにした

⇒92065496651点(コード)を達成。暫定83位に。興奮しすぎて体調が悪くなる(雑魚)。

4日目(2021/5/25)

考えたこと

• アイデアが尽きる
• ここで自分が問題文の解釈を間違っていたことに気づく(遅すぎ)。返り値として与えられるのは最短経路のコストでは無く自分が選んだ経路のコストだった
• 入力が自分の選んだ経路に対してかかったコストなら、乱数でぶれてるとは言えめっちゃ値の信頼度高いやん！ということは100ループ目以降のグラフの重み更新式で、actual costから計算したweighted costにより高い比重を置くべきでは？

改善(パラメータ調整)

• 100ループ目以降の重み更新式を、((現在の重み) * 2 + weighted cost * 3) / 5　に変更

⇒92373655103点(コード)。手詰まり感がすごい。

5日目(2021/5/26)～6日目(2021/5/27)

考えたこと

• 入力値として返ってくるのが自分の選んだ経路に対してかかったコストなら、最初のうちはどんどん寄り道してグラフの重みを尤もらしい値に早く塗り替えていく方が後々活きてくるんじゃないか？と思い至る
• 経路探索はこれまで全てダイクストラで最短経路選んでいたが、最初のうちはDFS+乱数でクネクネと道を選ばせてはどうか⇒点数下がる
  ※後々考えてみると、一度も通ったことのない道を積極的に選ばせる、だと点数上がったかもしれません。あと、入力生成のルール上、曲がる回数が増えれば増えるほど計算した重みの正確性が落ちていくようですね。
• 下図は実験の記録。DFSで生成した経路眺めるの楽しいですよね！

改善(パラメータ調整)

• 3日目に実装した「ループ初期段階でのグラフ全体の重み更新」の式のパラメータ微調整

⇒92821497168点(コード)

7日目(2021/5/28)

考えたこと

• 3日目に実装して失敗した、過去の入力を使いまわして重み推定の精度を上げる方法はやっぱりうまくいくのではないか
• 100ループ目までで初期のパラメータ推定やっているが、もっと早くできないか

改善(過去の入力を使った重み推定精度向上+パラメータ調整)

• 400/600/800ループ目に突入した時点で、それまでに使用した経路とactual costを用いてグラフの重みを調整するように変更
• 最初の50ループ目で重み更新式を切り替えるように、加えて50/100ループ終了時点で「ループ初期段階でのグラフ全体の重み更新」をかけるように変更
• その他細々としたパラメータ調整

⇒93382152783点(コード)

8日目(2021/5/29)

考えたこと

• やたらと点数の低い0018.txtのテストケース(890億点ぐらい)を眺めていると、右に一直線に進むべき経路で上下に激しくぶれながら進んでいたので、これはいかんと思いループの最初期段階では進める方向を更に厳しく制限しようと思い立つ
  ⇒これ成功したんですが後で考えるとそれはそうで、入力生成方法がそもそもグリッドの各行、各列で重みが近い値になるようにできてたんですね…

改善(初期段階で進める方向制限+パラメータ調整)

• 最初の50ループでスタート-ゴールの位置関係が上下左右まっすぐの時は絶対に一直線に進むように変更
• その他細々としたパラメータ調整

⇒93417969072点(コード)。プレテスト段階では最高のスコアに。最終日は用事があったので、実質これで自分のAHC003は終了しました。

最終結果

3000ケースのシステスで、2804636391585点、163位でした。AHC002が379位だったので大健闘だと思います。レートもぐんと伸びて1133に。緑コーダー(β)になれました。

ただ上位の方を見ていると、皆さん当たり前のように入力生成方法を理解した上で統計的に処理されているようでした。次回からは自分も数式の羅列だからと毛嫌いせずに、ガンガン読み込んで少しでもヒントを掴んでいきたいと思います。

まとめ

とりあえず思考過程をまとめるためにつけ始めたこの記録ですが、凄く有意義なものでした。

自分の場合、脳内だけで考えていると雑念や主観で考えがごちゃごちゃしがちなんですが、文章化(アウトプット)したらもう主観からは離れていてブレることがないので、改めて自分の目で見つめ直した時に新しいアイデアが浮かぶことがあり思考整理に役立ちました。

AHC003に関しては、自分が早解き苦手な上に緊張しがちなのでAHCマラソンコンテストのようにのんびりじっくり取り組める方が向いてるのだと思いました。すっかりAHCの楽しさに取り憑かれてしまったので、今後はAHCライクなコンテスト(KaggleとかCodinGameがそうですかね？)にも挑戦するかもしれませんね。

以上です。