前回のAHC001、AHC002、CodinGameSpringChallenge2021 など、単一の解を適切なアルゴリズムで求める以外のプログラミングコンテストの楽しさを覚えました。
今回のAHC003は、過去2回のAHCとは趣が違う問題で戸惑いましたが、その参加記録を書いていきます。
参加記とは書いていますが、この問題のより良い解を求めるための試行錯誤の記録というよりは、ビジュアライザの作成記となる可能性が高いです。
問題概要
大雑把に書くと、頂点が30×30の平面グリッドの2点を結ぶ最短経路を求める問題。
ただし、距離情報は与えられない。2点間の経路を出力すると、経路に対しておおよその距離が返ってくる。
予想した経路が最短距離に近ければ点数が高くなる。これを繰り返していき、1000回実施したときの得点が高くなるようなプログラムを提出する。
なお、1000回繰り返すなかでの得点に占める割合は、開始時点は低く、後半になるほど高くなる。
1日目
問題文を見て、まずは正の得点が得られるコードを書きました。
2点の結ぶときに、上下に移動してから、左右に移動するコードを提出します。
得点は、63179310956 / 100000000000 と、出て正の点を得ることが出来ました。
次に、webで公開されているビジュアライザを使用するため、ローカルで入力と出力が出来るようにコードを書いていきます。
今回のコンテストは今まで2回のAHCと違い、入力は「初回の入力」と、「出力に応じた入力」が発生するタイプのため非常に難しく感じました。
初日はwebのヴィジュアライザを使えるようにするところまでのコードを書いて終了しました。
一応、寝る前に、2点を結ぶときに、先ほどと移動する順番を入れ替えて、左右に移動してから上下に移動するコードを提出しました。
得点は、63117719888 / 100000000000 と出てきます。先ほどとあまり変わりませんね。
2日目
初日に、正の得点を得ること。と、ヴィジュアライザが使えるようになること。が達成できました。
ここからは、この問題をいかにして高得点にするかを考えました。
今回、私がこの問題を考える際のポイントは2つだと考えました。
- 最短経路を適切に求める。
- 辺の長さを正しく推定する。
最短経路については、ダイクストラ法を用いればよさそうな予想がつきます。まだ、実際にダイクストラ法を実装したことがなかったのですが、PAST本を読みながら実装を進めていきます。
もう一つの辺の長さを正しく推測する。については、最後までうまいこと行きませんでした。
ひとまず、ダイクストラ法の実装と、経路復元の関数が出来たところで、提出してみました。
辺の長さについては、通ったことない辺は、なんとなく5,600としました。
また、返ってきた距離から、平均距離を計算して、通った辺の距離を毎回、その平均距離で上書きしていました。
ダイクストラ法を使うための前準備として、1,000回のうちの300回は上下に移動したのちに左右に移動するコードを、600回までは、左右に移動したのち上下に移動するコードを利用し、残りの400回をダイクストラ法で解くようにしています。
得点は、78359133084 / 100000000000 と出て、ダイクストラ法でうまくいっていそうなことがわかります。
この日は、ダイクストラ法の実装と、経路復元のコードが書け、得点も大幅にupして気持ちよく眠りにつきました。
3日目
まずは、昨日うまくいったダイクストラ法の実行回数を増やしてみます。
昨日は400回だったのを700回実施するようにします。今まではPython3で提出していましたが、ダイクストラ法の実行回数が増えたこともあり、PyPy3で提出してみます。
残念ながらPyPy3でもTLEのケースが出ているので、Cythonで提出です。無事Cythonで通りました。
得点は、83622122354 / 100000000000 と出て、これまた大幅な得点アップです。
今回の問題の最短経路に関しては、関数としていつでも使えるようになったということで、次は、もう一つの課題である、辺の長さを正しく推定する部分を考えます。
辺の長さの更新を、今まで、毎回、inputで与えられる値を辺の数で割った平均値としていましたが、これを、既存の値と、inputで与えられる値の平均値との平均を取って更新するようにして提出しました。
得点は、88332930358 / 100000000000 と出ます。
より良い、距離の推定を考えていくことにしていきます。
途中、ダイクラ法の関数が一部間違っていた部分を修正して提出しました。
得点は、89144444402 / 100000000000 となり、90000000000点が見えてきました。
4日目～8日目
この間は、ヴィジュアライザを作っていました。
辺の距離推定のために、いろいろとネットで調べてみたのですが、体系だった知識というのは簡単にネットで探せるものでもなく、また、根本的に数学(線形代数？)力も高いわけではないため、ビジュアライザから何かがわかるかもしれない。という一縷の望みをかけてビジュアライザを作成していきます。
AHC001で自作のビジュアライザ作っている方にあこがれた。Stremlitでデータ可視化が楽しい。というわけでは、・・・あります。
StreamlitとBokehのversionの相性の問題かコードは正しいはずなのに表示されなかったり、といった不具合もありましたが、自作で、ビジュアライザを作ることが出来ました。
公式と似たような、a/bとkの分布を見れるようなヴィジュアライザが出来ました。
自分の提出の中でのハイスコアとの比較がわかるようになっています。黒がハイスコアと同じ、青がハイスコアよりも改善したk、赤がハイスコアから悪くなっているkを示しています。
また、右上がりの曲線は、得点の係数の推移を示しています。kが大きくなるにつれて、係数が大きくなっていることがわかります。
そのほか、seedを変更させたら、自動的に画像が変わったり、ツールチップでpathを表示させたり、seedに対する回答のoutputをコピーできるようにしたりという工夫をしています。
動画はこちら
結論としては、これを見ても、結局わからなかったです。
辺の情報を見に行くために、結局公式のヴィジュアライザサイトを利用していました。
辺の情報を何とか可視化できないかと考えて悩んでいましたが、辺の情報をヒートマップで表せば解決するかも？と思い、ヒートマップを作ってみました。
今までグラフの描画はbokehを使用していたのですが、bokehでヒートマップ作るのは難しかったので、seabornを利用しています。
動画はこちら
ここまできてようやく、行、または列で同じ色が続いていることに気づきました。
たまに途中から色が青から赤に変わったりしています。
入力生成方法をもう一度読み直します。実際には、10回以上読み直しました。ようやく、理解したのが土曜日の午前です。
このヒートマップのヴィジュアライザを見やすくするために、辺の初期値を5000にすると点数が上がるようだったので、提出しました。
得点は、89831509436 / 100000000000 と少し上がっています。
9日目(最終日)
ヒートマップの状況から以下のことがわかりました。
- 大体あってる。
- 辺の情報が正しかったのを崩す更新がある。(下図参照)
更新するときに、今の辺の情報とかけ離れた値の場合は、その辺の情報を更新するのをやめ、使用した他の辺に余った分を分配することにしました。
そのほか、単純なパスでの探索が終わった後に、辺の更新が0回で、更新されている辺に挟まれている場合は、更新が0回だった辺を、平均値で更新するようにしました。
得点は、89870631290 / 100000000000 です。
これの提出を持って、時間切れとなりました。
感想
今回のAHC003ですが、今までとはまた違った問題で楽しかったです。
楽しかったですが、悔しい思いのほうが強かったですね。
線形代数をもっとしっかり理解したいです。
今回のAHC003で、いろいろなことが学べました。大きなものとしては次の3つです。
- ダイクストラ法を経路復元を含めて実装出来た。
- 関数を利用して、コードが汚くなりにくかった。
- データの可視化ツールを自作できたこと。
ダイクストラ法は、アルゴリズムの概念自体は理解していましたが、初めて自分で実装出来ました。PAST本のおかげもありますが、経路復元は自分で実装出来ました。
経路復元に関しては、AHC002の復習でいろいろ考えて実装していったのが大きいですね。AHC002の復習をやってなかったら、今回スムーズには実装出来ていなかったと思います。
長期間のコンテストは、自分が書いたコードと長い間付き合っていくので、適切に関数を作成、利用しないとどんどん可読性も、バグの温床にもなりかねないことがAHC001やCodinGameSpringChallenge2021で理解したので、比較的初めから間違いなく利用する部分は関数として定義していくことが出来ました。
データの可視化は、少し前にWebアプリを作って、PythonでもWebブラウザで可視化できることがわかったので、Streamlitを利用しました。Bokehやseabornなどのライブラリは公式の情報やQuiita, StackOverfolow の情報を見て解決して行けて、よかったです。
pandasや、sqliteの操作も随分と慣れました。
次回のAHCも楽しみにしています。
コメント