競プロ日記012: AHC017の解法解説
AHC017 最終50位(暫定49位: 40.3G / 50.0G)の解法
THIRDプログラミングコンテスト2022(AHC017)の解法と，約一週間のコンテスト期間のアプローチについて解説(というか記録)しておきます．ヒューリスティック系コンテストの初心者・中級者や未来の自分の役に少しでも役立てばと思います．
問題の概要
N地点と，各地点を結ぶM個の道があります．この道のいくつかを補修工事するのに通行止めする必要がありますが，そうなると移動が不便になり，不満度が上がります．不満度はある地点から他の地点を移動する際の移動距離が増えるほど大きくなります．工事を行う日数Dと，一日に工事できる(通行止めできる)道の数の上限Kが与えられるので，これらの制約の中で可能な限り不満度を小さくするような工事計画を立てるという問題でした．
最初と2番目のアプローチ
まず最初にやったことは，1 1 1 ... 2 2 2 ... 3 3 3 ...のように適当に出力するコードの提出です．一度提出しておくと実際のスコアが得られるので，それを基準にローカルでのテスト環境を作ります．これをしておくと何度も提出してスコアの確認をする必要がなくなるので，基本的にやっておいた方が良いと思います．単にスコアボードを見て，似たような解答だろうなーという人のスコアを参考にするのも良いのですが，今回は同じ得点が何パターンかあったので，より正確に把握するために提出しました．
次にやったことはテスタの自作です．通常は付属のテスタをそのまま使うのですが，スコア計算の速度が遅すぎてストレスになることが目に見えていたからです．どうせ自分の解答プログラムを作るときにスコア計算を実装しなければならないですから，ここで慌てずある程度高速で正確にスコアが出せるように実装しました．高速とは言っても，まずは特別なことをせず愚直に実装します．
公式のテスタと同じスコアが出力できるようになったことを確認したらひとまずヨシとします．この時点では公式テスタと大して速度差はありませんが，問題本体のアイデアに詰まったときに気分転換として高速化をしていこうと決めました．
今回の自分ルール
本格的にマラソンマッチを始めて1年近く経ち，なんとなく心構えのようなものができてきたということもあり，今年は安定して結果を残すということを基本的な目標にしています．途中でくじけないように，簡単なルールを決めました．
- スコアが満点に対して7割程度になるまでは貪欲解法を中心に
- 高速化は煮詰まったときの気分転換としてやる作業とする
- 直感に反することでも必ず試す
- 最後まで諦めない
最初のアイデア
最初の時点でスコア計算に1秒近くかかっている状態だったので，まずは少ない計算量で良い計画／悪い計画を調べる必要がありました．いきなり躓いたので速い気分転換ということで，あまり頭を使わない高速化(2次元配列を1次元にとか)をちまちまと行いながら，「とりあえず到達不能な経路を作らないようにしよう」ということだけ目指すようにしました．
そう考えると割と簡単な話で，どこか1地点にだけ着目すればよいことになります．1地点からそれ以外の点に全て到達可能なら，他の点は調べなくてもちゃんと到達可能だとわかるからです．ではどんな点を選ぶべきかと考えました．少なくとも最初に1回，全ての点からの最短経路を求めているので，ついでに各点までの距離の合計も計算しておくことにしました．そして，距離の合計が最も小さい地点はおそらく盤面上の重心近くだろうという結論に至りました．
次の図はseed386を使って，この記事のために作成したものです．＋は全ての点の重心で，★はその地点から他の点への最短距離合計が最も小さくなる点です．思った通り重心近くになっていました．
この考え方を元に，最初の解答プログラムを作成しました．Dが小さい(5とか)の場合に上手くいかないこともありましたが，あまり気にせずに100ケース程実行してみます．そうすると，最初の解より2～3倍スコアが良くなったので，この方針で大丈夫だろうと判断しました．提出すると，26G程度のスコアが出ましたが，実行時間は4秒くらいかかっていました．
いきなり詰まる
最初の解法ですでに4秒も消費しているのと，正直ノーアイデアに近かったので，早速高速化タイムに突入しました．方針としては，
- この数日で次のアイデアが何か出るだろう
- もしそれが上手くいけば，次のステップ(おそらく山登り)に進める
- いろいろ準備をしておこう
です．つまり，高速化をして初期解を得るまでの時間を短くし，後半の山登り(道を入れ替えてスコア算出を繰り返す)をできるだけたくさんできるようにしておこうと考えました．とはいえこの時点では差分計算まで考えていなくて，小手先の高速化(queueをやめて固定長配列を使う等のチマチマしたもの)で，初期解を2秒くらいで得られるようにしました．さらに入れ替え山登りフェーズも追加して動かしてみると，到達できない点が現れるケースが無くなり，この時点で推定30G程度のスコアになりました．推定というのは，実際に提出せずにスコアボードの状況と自分のローカルテスト環境の結果を比較して算出したということです．
観測地点を複数にしたい
この辺りから実行時間を延長してみるということを試しました．スコアが上がれば単に高速化すればよいことがわかります．実際にやってみると，確かにスコアは上がりましたが少し物足りません．要するに，1点からの距離だけで考えると改善の見込みが無くなってしまうからです．そこで，今後も何らかの高速化によって実行時間を確保するという前提で基準にする点を増やしてみることにしました．ランダムな点も悪くはなかったですが，最終的に重心から同心円状に配置することにしました．次の図は3点を置いた場合と5点置いた場合です．重心からの距離は，半径の70％としました．
5つ置いた場合が最もスコアが良くなりましたが，制限時間の6秒では収まらなくなってしまいました．
苦し紛れの噓ヒープ - Liekstra's algorithm
本来ならここできちんと経路復元して差分計算を行うべきだったのですが，「早く完成品を仕上げたい」という誘惑にまけて小手先の高速化に徹してしまいました．今振り返って，失敗したと感じたのはこの点ですが，それなりに高速化されたので一応記録として残しておきます．通常のダイクストラ法はpriority_queueを使いますが，私は最初から普通のqueueを使っていました．普通のqueueだとNが大きいときに遅くなってしまうため，取り出す点の優先度は欲しい，しかしpriority_queueは遅い…ということで，妥協案として次のような操作を行いました．
- 要素を普通にpush
- 先頭の要素と末尾の要素を比較する
- 末尾の値の方が先頭の値より小さければswap
割と単純な操作ですが，できるだけシンプルなコードにして実行回数を増やすことで強引に速度アップさせました．ちゃんと差分計算したものよりは圧倒的に遅いですが，これで何とか制限時間の6秒に収まるようになりました．この時点で推定35Gくらいです．
停滞期
噓ヒープを選択することによりアルゴリズム的な工夫をする意欲が無くなってしまい，長い停滞期に入ることになりました．細かい調整をして37～38G程度までは上がりました．順位的にも100位以内に入れそうだし，このままゴールしても良いかな…と一瞬思ったのですが，最初のルール『最後まで諦めない』に違反していると思い直して粘ることにしました．でも焼きなまし的な何かをしようとは思いませんでした．速度の問題で山を登り切れていない状態で焼きなまそうとしても無駄だからです．ここでもう一度最初のルールを思い出します．『スコアが満点に対して7割程度になるまでは貪欲解法を中心に』これに徹するべきだと思いなおしました．
初期解の改善
この時点で締め切りまで3時間程度になっていました．「まだ工夫していないことは何か？」をよく考えた結果，計画に追加する道の順番がずっとランダムな状態のままだったことに気付きました．こういうのはまばらに設置した方が大体良いと思い込んでいましたが，『直感に反することでも必ず試す』というルールに乗っ取って，地点ベースで優先度を与えることにしてみました．
- 適当に1地点選ぶ
- そこに接続しているすべて道を日程に組み込む
- すべての道が組み込まれるまで繰り返す
これで少しだけスコアが上がりました(1.5%くらい)．なるほど，では地点の選び方も順序を決めて，起点(とりあえずランダム)の道を全て選んだら，その道に接続する点を次の候補としてさらに道を追加する，つまりBFS的な順序で道を追加していく方針にすると，さらにスコアが上がりました．では起点はどこか？一番最初のアイデアに戻りました．1点だけ選んだ点は，「そこから各地点までの距離の総和が最小になる点」でした．
しかしスコアは上がりませんでした．良さそうなのに…．しかしよく考えると，選ぶ道をかなり偏らせてスコアが上がったのだから，起点も距離の総和が最小なのではなく最大になる点を選べば良いのでは？と思いなおし，そのような点(つまり移動に最も不便な点)を起点にすると，最終的に5%くらいスコアが上がり40Gに到達しました．次の図は最終提出の解法で選んだ道の優先順位です．★が起点で，明るい(黄色い)辺を優先的に計画に組み込んでいきます．
反省と感想
やはり差分計算をサボったことが悔やまれます．後から実行時間を10倍にして1000ケーステストしたところ，スコアは8.6%程度増えました．ちゃんと高速化していればもう少し良い結果になったでしょうし，そこまでくるといよいよ焼きなましが使える段階になります．そこまで行きたかったというのが正直な感想ですが，今の自分の実力なら上出来だとも思います．とにかく安定して結果を残せるように，しばらくは今回のルールに加えて
- アルゴリズム的な高速化は優先的に行う
を基本的に守ってコンテストに参加していこうと思います．次の目標はランキング1ページ目！
