これはなに
ぼくのAHC017の参加記録です。147位でした。
問題について
N頂点M辺の重み付き無向グラフが与えられます。D日でM辺すべてを一回ずつ工事します。工事には1日かかり、工事している最中はその辺を通れません。工事しているときとしていないときで2頂点間の最短距離があまり変わらないようにしたいです。そのような工事の予定を考えてください。
つまり
・首都圏に張り巡らされた地下鉄を毎日一部分だけ封鎖するよ
・できるだけ人々に影響がないように封鎖したいよ
・いい感じの封鎖日程を考えてね
という問題です。
グラフは下の図のような感じです。このページから見れる。色付けると綺麗。
解法のまとめ
以下のことをやりました。暫定テスト50ケースで650M程度でした。
- グラフを5×5=25マスのグリッドに分け、中の3×3=9マスから1点ずつ、計9点をランダムに選ぶ。この9点から全頂点への距離の総和を評価関数とする。これを最小化することを考える。
- ある頂点から伸びる辺について、同じ日に1回だけ工事するような予定をつくる（言い換えると、工事する辺ができるだけ連続しないような予定をつくる）。これを250msec行い複数の予定をつくり、評価関数が最小のものを初期予定とする。
- 初期予定からランダムに2辺を選び、その工事する日付を変更することを考える。変更した2日の評価関数の合計について、変更後のほうが良くなる場合、その変更を採択する。これを時間まで繰り返す。
イメージとしては次のような感じになります。
上位勢の多くがやっているようなdijkstra法の差分計算の高速化はやっていなくて、毎回計算しました。ここ高速化できてれば。。。
日記
まえがき
あとは日記です。レポートとかでこの書き方したらボコボコにされるポエミーな文章です。考察とお気持ちが雑に書かれています。
スコアの推移は次のようになりました。
Pythonで初日からコードを書いていましたが、一週間後の土曜日にRustにかえたところが自分のなかの偉いポイント。
1/28（土）
問題文を読む。不満度の平均を最小化したいらしい。最近あった山手線の工事のニュースを思い出す。陸の孤島となった目白駅の住民が「つらいですよ～」というインタビューを受けていた。目白駅から隣の駅まで徒歩20分もかからないらしい。甘えてないで歩け。今回の問題ではそんな甘えた人が多いのか、孤立した頂点をつくるとペナルティが結構重めにつく。目白駅の住民を救いたい。
一日に工事できる辺の上限がKまでだが、不満度を最小にしたいならむしろceil(M/D)におさえたほうがよさそうに感じる(たくさん工事するほど移動しにくくなるので。D-1日で全ての工事をするなら、最後の日を2分割して作業するだけで平均値は下がる気がする)。とりあえずこの事実（Kまで目いっぱい工事するのか、M/Dでやめるのか）を確認するために雑にコードを書いて提出する。辺に1から順に日付を振っていき、Ｋになるか、M/Dになったら日付を+1する方法。前者は143,408,182,139点、後者は45,705,730,935点だった。「あれ、前者のほうが良いのか？」という気持ちになるが、順位表を見てまちがいに気づく。スコアが低いほうが相対スコアが高くなるらしい（つまりこのスコアが低いほうが良いらしい）。罠すぎ。
ちゃんとコードを書き始める。pythonでclassを使い、変数に型ヒントを書くのもだいぶ慣れてきた。とりあえず入出力用のクラスと、スコア計算の関数を書いていく。問題をパッと見た印象だと適当に盤面つくって焼きなましするのが強そうに見える。しかしスコア計算のコードを書いていると「や、これ計算できなくないか？」という気持ちになる。D日すべてについて、全頂点対に対して距離を計算する必要があるが、1日の計算でもワーシャルフロイド：O(N^3)は1000^3、ダイクストラ全頂点：O(NMlogN) =10^6log1000で 10^7ぐらい。N^2とMlogNの比較すると問題の制約では常にダイクストラがはやいことが分かるが、それにしても一回のスコア計算で10^8とか無理すぎて草。
スコア計算はやめてよさげな盤面をつくることを考える。孤立する目白駅をつくると急に苦しくなることから、次数dの頂点について、同じ日にそのd本の辺すべてを工事してはいけないことが分かる。逆に毎日1本だけだったらいい感じなのではという気持ちがしてくる。そのような予定をつくる（実装としては工事した辺につながっている頂点の集合を毎日用意する。辺をdequeにいれる。辺をdequeの左から取り出し、まだ両端の頂点が工事済みの集合に入っていなかったらその辺を工事して、辺の端の頂点を集合に入れる。工事済みの集合に既に入っている場合はdequeに右から入れておく。これをdequeがなくなるまで繰り返す。（実際は辺がdequeで一周してしまうことがあり、その場合は集合をリセットした。））提出。6,139,116,297点。とりあえず正の点数がとれて満足。
1/29（日）
昨日の提出をビジュアライザーで眺めるところからスタート。良い感じに各辺がばらばらに工事されていて、孤島ができにくくなっている。最終日だけはところどころ連結しているが、その割にはスコアが悪くなくて意外（コンテストが終わった今振り返ると、このタイミングで自分の用意した初期盤面があまり良くないことに気づけたのに。。。という気持ちになる）。よく見るとたまにスコアが100~1000倍悪いケースがある。次の図のようなケースだった。
確かに1頂点だけでなくても孤立してしまうケースがあるなという気づかされる。Unionfindで全頂点が連結しているか確認するようにする。連結していなかった場合は辺の並びをランダムにシャッフルして改めてdequeに入れて工事予定をつくる。これを全日程、全頂点が連結するまで繰り返した。大変なケース（Dが小さいケース）でも条件を満たすケースは100msecもかからずにつくることができた。これを提出。1,011,269,879点。前日の6,139,116,297点から大きく下がって嬉しい。
1/30（月）
何をすればよくなるか分からない。めちゃめちゃ焼きたい盤面をしているのにスコア計算が重すぎて焼けない。電車に揺られながらビジュアライザーを眺めていた。よく考えると、別に全頂点の計算をしなくてもいいのではという気持ちになる。新宿から目黒にいくときの不満度と、代々木から目黒にいくときの不満度なんて大して変わらないだろという気持ちになる。（代々木は新宿の隣の駅。）これ思いついたとき自分のこと天才かと思った。はい。
代表点をいくつか取ってそこからの距離の総和を評価関数にすればいいことが分かる。（元の距離との差分とか定数倍は、スコアの大小に影響しないため。）代表点をいくつとるか、どうとるかは大事そうだったため次のようにして調べた。
- まず4頂点で試す。適当に50個予定をつくり、実際のスコア（O(DNMlogN)で10秒ぐらいかけて計算するやつ）と代表点からの距離の総和（O(4DMlogN)で計算できる）の順位相関係数を計算する。以下の3ケース試してみて3のケースが一番高くなった。（r=0.65程度）この方針でやることにする。いま振り返るとここの分布についてはもう少し考えられた気がする。
- 完全ランダム
- 4×4に分割して外側にあるブロックから1個ずつ取る
- 4×4に分割して内側にあるブロックから1個ずつ取る
- 頂点を増やしていく。9頂点、16頂点についても5×5、6×6に分割して中から取っていく。9頂点でr=0.75, 16頂点でr=0.81だった。相関係数0.7あればいいでしょwというガバ思考の下、９頂点にする。(ほぼ2倍の計算時間かけて相関係数が0.06あがるってどんなもんなんだろう、分からず。ここら辺のハイパラの最適化もゆくゆくはやれる人になりたい。）
9頂点だけでもそれなりにいい評価ができることが分かった。もともと盤面が連結したら終わりにしていたところを、時間いっぱいまで工事予定をつくり、そのなかで一番評価がいいものを提出するように変える。973,582,472点。少し改善された。1,011,269,879点からの差分だと大したことないが、予定を評価できるとわかったのがとても大きい。
1/31（火）
忙しくて何もやらなかった。下がり続ける順位表を見ると精神に悪いので何もしないに限る。
2/1（水）
忙しくて何もやらなかった2。
2/2（木）
スコアが評価できることが分かったので、山登りをする。初期盤面から2辺を選んでその工事予定を交換する。そして全日程のスコアを計算する。提出。857,734,487点。
2/3（金）
先輩の修士論文発表会を聞きに行ってた。電車の中でジャンプ+の『怪獣8号』と『ハイパーインフレーション』を読み始めたら面白くてスワイプする手が止まらなくなった。結局帰宅後に全部読んだ。一日が終わった。
2/4（土）
スコア計算の際、辺を交換することで影響があるのは2日分しかないのだからこの2日だけ計算すればいいことが分かる。UnionFindで連結するか管理していたが、連結していないものはスコアが極端に悪いのでスコア評価で簡単にはじける（つまりUnionFindは使わなくていい）。こんな感じで高速化をしていく。提出。802,012,141点。厳しい～～～。
制限時間6秒のところを手元で600秒回すとスコアが改善される。局所解にハマっていそうな雰囲気もなく、まだまだ山登りできそうな雰囲気が出ている。なんとか高速化できないかなぁという気持ちになる。ここで振り返ると自分が10秒かけて行っていた厳密なスコアの計算を、webのビジュアライザーは1秒程度でやっていることに気づく。配布されているRustのスコア評価のコードを見ても、自分のスコア評価と特に変わらない。つまりRustのほうが10倍以上速いのだなという気持ちになる。というわけでPythonで書いていたコードをRustに移植する。(追記: 移植というか、pythonのコードをrustのものに完全に書き換える)
Rustのことは何も分からないので、PythonのコードをchatGPTに投げてRustに変えていってもらう。それを張り付けて、rust analyzerに注意されるところを気合いで直していく。（所有権がらみのものが多かった。＆をつけたり消したりして対応した。）これが最先端のペアプログラミングや！450行あったpythonのコードの不要な部分を捨てつつRustに書き換えていく。400行のRustのコードができあがるまで4時間ぐらいかかった。ううう、つらい。
ところで今回のコンテストを開いてくれた会社THIRDさんがAtCoderのことをAI競技プログラミングと呼んでいた。
コンテスト前にこのページをみて「AtCoderはAIあまり関係ないのでは。。。Kaggleとかsignateのほうがこの呼び方あってそう笑」などと思っていたか謝罪させてほしい。高速化のためにAI(chatGPT)の力を借りる。そうか、、、こういうことだったのか、、、という気持ちになっていた。
AIの力を存分にかりたコードを提出する。653,717,209点。相対スコアでも25Bから30Bに変わる。ループ数もpypyとRustでRustのほうが5倍ぐらい回っていた。Rust最強！！Rust最強！！（AHCをpythonでやるのはとても不利なんだなぁと気持ちになった。まあpythonで速さ求めるときは適当に並列化するし、、、）
2/5（日）
最終日。方針としては次の3つが考えられた。
- 更なる高速化
- いい初期盤面をつくる
- いい状態遷移をする
1.更なる高速化については、何をすればいいか分からなかった。辺の削除、追加により最短距離が変わる頂点は限定的なため、差分計算はもっと高速に行えるよなぁという気持ちがあるが、Algoをさぼっている人間には実装ができない。かなしい。
2,3についてはある程度あてがあった。長時間回してみると最初はばらばらだった辺が連結していった。ぼくの直感には反していたが（毎日ちょっとずつ工事したほうが嬉しいだろと思っていた）、計算機が繋げたほうが良いというのだからそうなんだろう。（これについてはコンテスト後に多くの人が触れていて、説明をみて納得した。直感に頼りすぎてはいけない。）とはいってもどういう風に連結させて初期盤面をつくるのがいいか分からない。
とりあえず厳密に解けるケースでやってみた。辺が少ないときはbit全探索的な感じで厳密に解ける。解いた結果を描いてみると、確かにつながっているものが多い。
最善の盤面ではつながっているものが多いということは、できるだけ辺をばらばらにしている自分の考えとは逆だ。じゃあどうやって良い初期盤面をつくるか？分からない。。。適当につなげて工事すると陸の孤島ができあがってしまう。時間も限られていたため、初期盤面をいじることはあきらめた。
状態遷移は改善できる感じがする。完全ランダムに2辺を交換しているところを、工事する辺が連続するようにランダムに選べばいいんでしょという気持ちになる。実装する。バグる。実装する。バグる。ええ。。。コンテストが終わりました。
終わりに
初期盤面にしても遷移にしても、もっと頑張ることができて、Algoを頑張ってればdijkstraの差分高速もうまく実装できたかも。。。という気持ちです。
それでも147位、過去最高のパフォーマンス1842をとってレートが1075から1294に。うれしい。
おしまい。
