THIRDプログラミングコンテスト2022(AHC017)日記編

1/29週は自由時間の大半を「THIRDプログラミングコンテスト2022(AHC017)」に注いだのでその日記になります。

問題の概要や提出解法は「参加記」を参照いただくことにしてここではどう過ごしたのか？（どうもがき苦しんだのか？）を時系列でまとめたいと思います。

AHC017開始前(1/26～27)

前回、AHCの時だけ使っているマシンを使おうとしたらネットにつながらず時間をロスしたので事前に確認。

ちなみに通常使いしているPCが古くなったのでAHC兼用で買い替えようとしたのですがダラダラしていたら注文が遅れ間に合いませんでした。

前日はOzyさんがまとめられた「Psyhoさんによるヒューリスティック・ボットコンテストのための無料Tips」を眺めてました。

Psyhoさんのアドバイスはどれもそうだよなぁと思うのですが1つだけ

「バージョン管理は悪だがテストを実行するときは別」

はテストより細かい頻度でcommitしたい時もありどうなんだろう？という気がしています。（もっと細かくテストをしろという話なのかもしれません。）

私の場合はバージョン管理で助けられたことが多いので今回も行います。時代遅れも甚だしいのですがGithubの無料アカウントでPrivateレポジトリを作れることを最近まで知らなくて今回からはGitHubにしました。

1/28(Sat)

12時にコンテストスタート。お昼ご飯を作りながら問題文を眺めます。

辺を通行止めにした時の距離の増加を最小化する問題でシンプルな問題に見えます。

スケジュール問題風ですがスコアは日に依存しないので辺集合の分割問題ですね。連結していれば不満度は[math]10^6[/math]くらいですが、非連結になると[math]10^9[/math]になるので連結性を保って工事をやりきるのが第一目標でしょう。

ぱっと思いつくのは平面グラフなので「遠い」辺を選べば連結性は保てそう…というくらいで特に思いつかず10,000ケースをダウンロードしてテストセットを作成します。

まず全点ダイクストラで不満度を出すところを実装。ここが非常に重くて1秒近くかかるので制限時間6秒だと数～数十回やるのが限界です。なるほど

正確な不満度計算をせずに良い工事計画を作る

のがポイントになりそうです。

いったんスコアが合っているか確認します。…合いません。Dで割るのを忘れていたりN(N-1)で割るタイミングで微妙にずれたりしてデバッグ。ようやくVisualizerと合うようになりました。今日はここまでで終了。

1/29(Sun)

遠くの辺を選べば連結は保てるだろうと

• 未工事の辺のうちその日に工事予定の辺との最小距離が最大の辺を選択

としてみます。とりあえず回ってスコアも正しそう。

ここで高速化として

• 辺集合をBitsetで持つ
• 初期グラフで各点の最短路木を保持し辺の削除時に影響があれば再計算

を実装して11%くらい高速化。これをsubmitして平均不満度が73.5Mくらい。

次は辺[math]e[/math]を工事した時の迂回路を出しておき、迂回路をさらに工事しないようにします。

これをsubmitすると平均不満度は46.6Mまで下がりますが相対スコアはほぼ変わらず。

上位陣は連結性を保つのはみんなやっていてて、そこから経路増加の最小化勝負になっているんだろうなぁと想像して連結性を維持するやり方を考えます。

[math]D[/math]個の全域木を用意して[math]d[/math]日目に全域木[math]T_d[/math]は工事しないとすれば連結性は保証され、全域木以外の辺の和集合[math]\bigcup_d E\backslash T_d[/math]が辺集合[math]E[/math]になれば工事計画はできそうです。

これを焼きなまし法で実装。コーディングを優先して高速化は後まわし。これで工事計画を組むとついに非連結な成分なくなった！

Submitし平均不満度19.2Mで相対スコア25.5Gとあまり変わっていないですが順位は一気に72位まで上がります。連結性を維持できるかでグループが分かれているのでしょう。

こうやってアイディアを形にして改善が目に見えると楽しいですね。ヒューリスティックコンの醍醐味です。

この日は改善アイディアを書き出して終了。

1/30(Mon)

朝から腰と右手首が痛いです。今までコンテスト中に痛くなったことはなくて不惑の年を前に体力低下を感じずにはいられません。

お昼に散歩しながら平方分割っぽく

みたいに分割して計算量を省くとか

1辺ずつ工事した時の不満度が下限になるので下限を達成する計画を作る

のはどうかな？と考えてました。特に下限は達成できてしまえば終わりなので「月曜だけど意外と早く終わっちゃう？」とか呑気に考えてました。

仕事が終わってから迂回路を工事しなければ1辺ずつ工事した時の不満度が実現できるので迂回路中の工事を極力減らすようにします。手元のケースだと下限に対して平均1.12倍の不満度まで来ているのでsubmitします。

ところが相対スコアは25Gくらいです。あれ？下限の1.12倍まで来ているはずなのに上位陣はその半分くらいの不満度を実現できていることになります。うーむ。なんでだ？

小さいサンプルで全探索してみます。

上の例だと1辺ずつ5日で工事するより2+2+1辺の3日間の方が不満度が小さくなります。

おおぉ、そうなのか。下限と思っていたのは実は目標の目安ぐらいでしかなくて工夫するともっと減らせる…というわけか。

とはいえ他に良いアイデアもないので下限改め「目標の目安」を目指します。

焼きなまし法で迂回路中の工事を別の日どかします。ここの実装で改めて気づいたのですが正確な不満度計算が激重で秒単位でかかります。うまく代替指標が決まれば正確な不満度計算は省いた方がいいかもしれません。

1/31(Tue)

Psyhoさんがすべてのサンプルで1位になりスコア50Gをたたき出してました。理論上ありえるとはいえ強者集まるこの場でそれを実現するとは…。

この日は開始できたのが遅めで昨日の続きの実装＆デバッグをして終了。

2/1(Wed)

迂回路を極力工事しないロジックがようやく出来てsubmit。平均不満度は18.0Gまで改善しましたが相対スコアは23.5Gでそろそろ伸び悩んできそうです。

ちらっとTwitterをみたらかえでさん^[1]ヒューリスティックコンによく参加されている方で仕事、家事をしながら競プロにのめり込む様子を綴った参加記が面白いです。がAtCoder社に転職したというツイートが飛び込んできてびっくり。思わず転職記を読み入ってました。

さてAHCに戻ります。アイデアもないので工事する2辺を全部試して不満度の変化を可視化してみます。不満度が増えるのはやはり迂回路をさらに工事して非連結になったり大幅に迂回路が大きくなるケースです。

面白いのが不満度が下がるケースで

図で220-200, 200-244の辺(赤点線)を同時に工事すると最短路が200-281, 281-85(赤実線)に変わります。各辺の迂回路が共通してて別々の日に工事するよりまとめたほうがお得という構図になっています。

今まで工事する辺を離す方向でしか考えてなかったですがお互いの迂回路が共通している場合はむしろ一緒に工事した方がいいというわけですね。さらに最短路によく使われる辺でこれができると大幅に不満度が下がりそうです。

この日はこの考察に満足して終了。

2/2(Thr)

「最短路に何回も含まれる辺」って概念がどこかにあったよな…と通勤中に探してみます。コミュニティ抽出(参考論文)でのEdge betweennessですね。オジさん勢はこういった知識をうまく活かしていきたいところです。

Edge betweennessを計算して可視化すると

目の網膜？っぽい結果になります。昨日見ていた不満度の下がる辺でのEdge betweennessを見てみると

と確かにEdge betweennessの高い辺を同時に工事するのがよさそうです。

これをどうロジックに落とし込もうかと考えますが、疲れがたまってて頭が回りません。「Cycle」を「Sycle」とか書き始める始末でこの状態で考えても下手の考え～になると思いこの日は早めに就寝。

2/3(Fri)

やりたいことは

• 辺を工事しても連結性を保証できる
• 辺を工事した時の迂回路の大きさ抑えられる
• Edge betweennessの大きい辺を同時に工事する

です。図を書いていると閉路を列挙しつつうまく閉路のグループを作っていくイメージですが面倒そうです。

よく考えると平面グラフの面を列挙できればよいので双対グラフを作ればよいです。意外と双対グラフを求めるライブラリが見つからずこちらを参考にしました。

やりたいことをまとめると

• 双対グラフから面を列挙する
• 面のEdge betweennessが最大のものから隣接する面を一定の大きさまでつなげる
• 面の集合から同時に工事できる辺を求めEdge betweennessが大きいものを同時に工事する

です。うーん、残り時間で実装できるかな…。

双対グラフの作成、面/面集合を管理するクラスを書いた時点で日付を回ったので明日以降の影響を考えて終了。

2/4(Sat)

順位表を見たらPsyhoさんの50Gが崩れてbowwowforeachさんが一位に。スゴイ！

可視化した結果と突合しながら実装＆デバッグを進めます。

なんとか動き出したのが夕方ですが、なぜか非連結な成分ができることも。小手先感満載ですが全域木を作って固定するロジックと組合せてお茶を濁します。

これでそこそこ良い初期解ができているはず。正確な不満度は激重なのでEdge betweennessを元にした評価関数で焼きなましをします。

ただEdge betweennessを使った評価関数と不満度があまり連動していません。ヘタすると逆方向になり何もしない方がましという結果で水曜の結果にすら負けます。

うわぁぁ…マジかー。うーー、このタイミングでこれは辛い。ちょっとショックが大きくて下手に動くと傷が深くなりそう。落ち着くために日付が変わったくらいで就寝。

2/5(Sun)

朝起きてもショックが残っています。水曜の提出を越えられなくてそのまま終わる可能性もありそうです。

一度落ち着いて実験をします。昼までに分かったのは

• Edge betweennessで初期解を作るのは良さそう(不満度が下がる)
• 焼きなましはEdge betweennessではなく別の評価を使った方がよさそう
• 全域木で決め打つと不満度の減少が限定的

です。

全域木を残している以上、水曜の結果を越えられそうにないので全域木でお茶を濁さずちゃんと連結になるようにします。

もう一度やりたいことを紙に書き出しロジックの2/3くらいを書きなおします。可視化した結果を見ながらデバッグしてようやく夕方ごろに期待した動きになります。

ただ、[math]K[/math]がシビアなとき([math]\lceil M/D \rceil[/math]に近い時)は工事日を修正した結果、非連結になることがありこの場合だけ全域木を使うことにします。

後は焼きなましで改善します。遷移は辺を選んで別の工事日にします。あと全体の不満度ではなく「変更する辺の2端点を始点とする最短路」に絞って計算します。

これだと数千回は回り、ようやく水曜の結果を上回るようになります。いやぁ本当に間に合ってよかった。

焼きなましのパラメタをチューニングすると結局、山登り法になりました。やはり反復回数が足りてないですね。

高速化は最短路木の差分更新が頭によぎりますがさすがに残り1-2時間でやることじゃないです。不満度を2端点ではなくて4～9点くらい固定でとってその点での評価を試しますが、反復回数固定だと良くなりますが時間固定では悪化したので採用を見送ったところでコンテスト終了！

暫定175位でした。青パフォ圏には入れてそうでAHC青コーダになれるかどうかシステスが気になります。

Tweetを眺めていると上位陣は

• 最短路の差分更新
• 不満度関数はサンプリング評価

に加え、さらに工夫をしていてラスト2時間でたどり着いた世界の先の先でした。

可視化、考察に時間をかけすぎたかな…という気もしますが、平日に働きながらコードを書きまくってテストするのも体力的に厳しいので仕方ないかな…という気持ちです。

お風呂に入ってリフレッシュしてビールを飲みながらAHCラジオを見ます。AtCoder社員となったかえでさんがさっそく登場されてました^[2]すごい時間帯に解説放送をするSnukeさんや、日曜の夜に解説放送するwataさん、かえでさんはどんな雇用契約になっているのか気になります。。この瞬間が一番幸せかもしれません。ビール１本で酔いが回ってきたので疲労感と満足感を感じながら1週間動かし続けたマシンを落としました。

なお、注文したPCは水曜に届きましたが開けることもできず終了日を迎えました。

次回AHC018はこのマシンで参戦します！