THIRD プログラミングコンテスト 2022 （AtCoder Heuristic Contest 017）参加記
THIRD プログラミングコンテスト 2022 （AtCoder Heuristic Contest 017
今回意識したいこと
- 記録をとる
- どう考えたか、どう改善したか、その結果どうなったかなどを記録するようにする。
- ちゃんと記録を取っていた回（AHC014）はわりと成績が良かった。
- 参加記を書く時にも役立つ
- よく観察する
- 高度な知識がなくても、よくデータを観察すれば有用な気づきを得られることもあるはず。
- そのために、いろいろな情報を出力するようにする。
- 自作ビジュアライザが理想だけれど、難しいので、テキストファイルに出力したり、それを表計算ソフトで処理したりしてみる。
ルールの確認
まずはルールを見ながら思ったことをメモしていきます。
- 平面無向グラフで表現される道路網の工事計画を立てる。
- 工事で道路が使用できなくなることによる不満度を抑えることを目指す。
- 500 <= N <= 1000 であるので、ワーシャルフロイド法によって全点対最短路を求めることができない。
- 1回もできないので、工事前の全点対最短距離を求めることさえできない。
- ダイクストラ法なら1回くらいならできそう？
- ABCでよく見るグラフと違い、頂点に座標が存在する（平面グラフと言うらしい）。
- 得点は、すべての組み合わせの2点の、工事による最短距離の増加量によって算出される。
- 到達できない場合は10^9として扱われる。
- 頂点が半径500の円内に収まっていて、辺の重みが頂点間のユークリッド距離×1000であることを考えると、10^9というのは相当大きい。
- 可能な限り、グラフが非連結になることは避けたほうがよさそう。
- 到達できない場合は10^9として扱われる。
- すべての道路を一度ずつ工事しなければいけないので、「どの道路とどの道路を同時に工事するとよくないか」を考える問題と言える？
正の得点を得る
改善の目安にするために、まずはランダムに工事を行うコードを提出します。
一日ごとの工事数が均等になるようにして、あとはランダムに工事する日を割り振りました。
不満度（低いほど良い）は37,538,194,005（≒37.5G）でした。
得点計算関数を作る
入出力を与えると、得点（不満度）を返す関数を作ります。 ワーシャルフロイド法だと、seed=0 (N=791, M=2277) で35秒かかりました。 ダイクストラ法で書き直すと、3.5秒になりました。 公式ビジュアライザと比較して、正しく不満度を計算できていることを確認しました。
改善はじめ
さあ、ここからが本番です。 改善方針として真っ先に思い浮かんだのが、グラフを連結にする、というものです。
本当に連結にすることが重要かどうか確認するために実験をしてみました。
ランダムに工事計画を立てた時の、各日ごとの連結成分の個数と不満度を計算し、集計しました(seed=0-99)。
やはり、連結成分が複数になると不満度が桁違いに上昇しています（縦軸は対数目盛）。 工事全体の不満度は各日の不満度の平均から計算されるので、1日でも非連結になる日があると、そのテストケースの点数は非常に低くなるでしょう。
連結になるか、時間が足りなくなるまで、工事計画をランダムにシャッフルし続けるプログラムを作成しました。
結果は、不満度7.72Gと、かなり良くなりました。 連結状態に注目するのは良さそうです。
連結させる
非連結になったグラフを見てみると、一つの頂点に接続している辺すべてが工事中になることで、非連結になってしまっているようです。
頂点を共有する辺を同日に工事する計画になっていたら、別の日に割り当てるようにしました。
結構ばらけているように見えます。しかしこれでも、テストケース100個中7個で非連結になってしまいました。 頂点数３～５個程度の連結成分ができてしまうことがあるみたいです。
提出してみると、不満度は6.43Gで若干よくなりました。
確実に連結させる
辺を一つずつ見ていき、その辺の工事日に辺の両端が別の連結成分に属している場合、工事を別の日に割り当てることで連結させていきます。この処理によって新たに非連結になる日ができる可能性があるので、時間いっぱい処理を繰り返します。
100テストケースすべてで連結にすることができました。 提出すると、不満度は1.01G、かなり減っています！
しかし順位はあまり変わっていない気がします。 相対スコアは、テストケースごとに独立して不満度に反比例するので、極端に悪いケース（非連結だったケース）が並まで改善されても、あまり相対スコアに影響しないのかもしれません。
工事による他の辺への影響を調べる
一つの辺を工事中にしたときに、最短経路がどのように変化するか調べてみます。 すべての頂点対の最短経路を調べ、工事前と工事中の最短経路として使われる回数の変化を調べます。
ビジュアライザを自作して、結果を表示してみました。
- 緑：工事する辺
- 赤：工事中に最短経路として使われることが増える辺
- 青：工事中に最短経路として使われることが減る辺
緑の辺を工事するときには、赤い辺が代わりに最短経路として使われることになるので、同時に工事しないほうが良いといえそうです。
青い辺は、緑の辺からあまり角度を変化させずに伸ばしていった辺、
赤い辺は、青い辺と平行に並んだ辺、
という感じでしょうか。
平行な辺は「バイパス」として機能するので、直感とも一致します。
バイパスを確保する
ある辺について、その辺との角度の差が小さく、ユークリッド距離が小さく、延長線上にないものを、バイパス辺とします。
まずランダムに工事日を割り当て、そのあと辺を一つずつ見ていき、バイパス辺を同じ日に工事することになっていたら別の日に変更する、という処理を繰り返します。 最後にグラフ全体が連結になるように工事日を変更します。
提出結果は、不満度977Mでした。手間がかかった割にあまり変わりませんでした……。
1つの面の周りで同時に工事しない
辺によって分割された領域を「面」というそうです。 面を挟んだ反対側に移動したいとき、面の外周に沿って回り込む経路が最短経路になりやすそうです。また、右回りが最短経路なら、左回りが二番目に短い経路ということもよくあると思います。 そこで、1つの面を囲む辺を同じ日に複数工事しないようにします。面を囲む辺の数が工事日数Ｄより大きいときには、できるだけ分散させるようにします。
テストケース100個で実験してみたところ、 (辺の数M / 頂点の数N) が小さいときには、バイパスを確保するアルゴリズムよりもいい成績が出やすくなりました。
M/Nが2以下のときにはこのアルゴリズム、そうでないときにはバイパス保護を採用するようにしました。
提出結果は905Mでした。そろそろ時間なのでこれを最終提出とします。
感想と反省
- 連結することが超重要（というより大前提？）だということに気づけた。
- 実験して確かめられたのがよかった。
- ちょっとしたビジュアライザを作れた。
- 静的な画像を出力するだけなら結構簡単だった。
- アルゴリズムをちゃんと実装できているかどうか確認するのに役立った。
- 面を列挙するアルゴリズムの実装が難しかった。
- 山登り法ができなかった。
- ごく少数の頂点を選んで評価したら、真の評価値とはかけ離れたものになると思い込んでしまった。
- 試してみればよかった。
- ごく少数の頂点を選んで評価したら、真の評価値とはかけ離れたものになると思い込んでしまった。
- 公式ビジュアライザの使い方をよく読むべきだった！！
結果
暫定262位です。難しかった～。
