2023/02/18(土)12:00 ~ 02/26(日)19:00 の約1週間，RECRUIT日本橋ハーフマラソン2023冬(AtCoder Heuristic Contest 018) が行われました。
AHC参加3回目，レート帯は茶色(Algorithmは水色)の私は暫定177位，最終188位(パフォ1771)でした。自分の中では3回目にしては好成績だと思ったのと，せっかく1週間頑張ったので参加記を書きました。
参加記は2本あります。
この記事はコンテスト期間中に何をしていたかの説明です。
最終的な戦略や成績に興味のある方は，【最終提出編】AHC018 参加記 (RECRUIT 日本橋ハーフマラソン 2023冬) へどうぞ！
目次
- 0. AHC参加の動機(ポエム)
- 1. 1日目(土)
- 2. 2日目(日)
- 3. 3日目(月)
- 4. 4日目(火)
- 5. 5日目(水)
- 6. 6日目(木)，7日目(金)
- 7. 8日目(土)
- 8. 最終日(日)
- 9. 反省
0. AHC参加の動機(ポエム)
初のAHC参加記なのでポエムります。ご容赦ください。
私がAHCをやってみようと思ったきっかけは，「技育祭」(2022春/2022秋)というイベントでchokudaiさんが1時間，爆速でAHCの問題を解いているのを見たからです。
「技育祭」は株式会社サポーターズが運営する，日本最大の学生向けテックカンファレンスです。赤Coderが競プロの問題を解く様子をリアルタイムで見れるということで参加しました。
自分の中では「競プロ=ABC/ARC/AGC」だったのでそれを解いている姿を期待していました。しかし実際覗いてみるとAHC…。「AHCかー…ちょっと期待と外れたけど，爆速コーディングは見れるから見よー」と思いつつ見ていると……
chokudaiさん「問題文が長い！！！！まとめるとこんな事をして欲しいって言ってるよーｺﾞﾆｮｺﾞﾆｮ~」
ch「とりあえずサンプルコードそのまま提出してみよっか！はい正の得点！」
ch「これだけじゃちょっと面白くないから，次は1回乱択するコードを書いてみよう！」
ch「これじゃ運ゲーだね！次は何回か乱択して一番良いものを出力しよう！お！だいぶ良くなった！！」
(ビジュアライザーを見る)
ch「これだとこのへんに無駄がありそうだね！ｺﾞﾆｮｺﾞﾆｮ~」
私(え…AHCってもっと難しいことしてるイメージだったけどこんなのでいいの……？)
ch「え！！みんな難しいことやってると思った！？そんなことないよ！！これで十分戦えるよ！！！！！！」
ｸﾞｻｱｱｱｱｱｱｱｱｱｱｱｱｱｱｱｱ!!!!!!!!(心臓に鋭い何かが刺さる音)
この一言で私の心は射抜かれました。これで十分戦える…だと…！？
考察→改善→フィードバックのサイクルでどんどん良くなるの，楽しそう。
よし，ちょっとやってみるか。
で，やってみました。
1. 1日目(土)
AHCの初動は「技育祭」の時のchokudaiさんを真似て固定しています。
①サンプルコードがあればとりあえずそのまま提出
②1回乱択解法を提出
③複数回乱択解法を提出(最高点の答えを出力するコード)
この中では③④が最も高得点が期待できそうですが，あえて①②をやっています。ビジュアライザーを比較することで，どういうときに得点が良くなるか/悪くなるか，それは予想に反していないか，予想外の改良は起きていないかなどを確認します。
また，これらの点数を基準にしてこれからの解法を評価していきます。
あと，提出する度に得点が上がるのを見ると「これだよこれ！！」とモチベが上がります。
今回はサンプルコードがあったので，とりあえず①で正の得点を得ました。素点27M点(低い方が良い)。
しかし「すべての家に水が流れる」という条件を満たさないとプログラムが終了できないため，「ランダムに掘る」という乱択解法は明らかに効率が悪い解法です(盤面のほとんどすべてを掘ることになりそう)。あまりやる意味が見出せないので，②③はやりませんでした。
そして次のフェイズへ。
④汚くても良いから思いつく解法をどんどん提出
サンプルコードは「一つ目の水源まで最短経路でまっすぐに掘削を行う」というものでした。「最も近い水源に行く方が良いだろ～」ということで，各家について最も近い水源へ縦→横の順で掘るのを提出しました。
ちょっと点数は良くなりました。素点20M点。
バグ取りに時間がかかったので，この日はこれで終了。
2. 2日目(日)
予定があったので手を付けていません。移動中に考察をしていました。
3. 3日目(月)
1日目の提出は，家と水源の位置関係のみに基づいており，岩盤の硬さは考慮していませんでした。「硬いところは掘りたくないよな～」ということで，20×20の代表点を試し掘りして単純化し，400頂点のグラフでダイクストラしました。
水が流れている代表点に最も近い家から順に繋いでいきます。
代表点はpower=200で壊れるまで掘り，消費した総HP(C+power)をメモ。
各代表点からは周囲8点に辺を張ります。
辺の重みは，(両端の代表点のメモした総HPの和)*(2点間のマンハッタン距離)/2です。これは横軸に距離，縦軸に総HPをとったときの台形の面積にあたります。
家からパスの掘り方はpower=50で固定し，累計powerが2400以上になっても壊れなければ累計powerが5000になるように掘って確実に壊すことにしました。パスの決め方と掘り方は切り離して考えているので，掘り方を詰めるのは後回しです。
ビジュアライザーの結果がこちら。
お！！めっちゃ良いパスじゃん！
提出，提出～♪
素点27M点。
え…？サンプルコードと同じ…？
家-水流マス(水が流れているマス)までの経路は良くなりましたが，試し掘りのコストが大きかったようです。実際，seed=0では総コストの約71%を試し掘りが占めていました。
試し掘りは「経路を掘るコストの前借り」なので，ある程度のコストを要するのは仕方がないです。ただ大きすぎる気がします。
そこで試行錯誤の末，この日は以下の工夫を行うと良いことが分かりました。
- 代表点の試し掘りに上限を設定。
- power=50で最大5回まで掘る。
- 先の解法で通るパスは概ね硬さ250以下だった。それより大きい硬さの程度はほぼ通らないので硬いことが分かれば十分。
- それでも壊れなければその地点の硬さ推定値は5000(最大)としてなるべく通らないようにする。
- 代表点の重みの付け方を変更。
- 消費した総HPからpowerの総計に。
- この変更は特に得点変化に繋がらないが，重みを「硬さの推定値」と定義づけた。
- 代表点の数はそのまま20×20
- 前はとりあえず20×20で固定していた。
- 試し掘りに上限を定めた結果，盤面によっては壊れる岩盤が少なくなる思われる。情報が少ないと思うので30×30に増やしてみたが，素点が増加したためやっぱり20×20が良いことが分かった。
- 使わない水源は代表点と繋がない
- 最初に各水源とその近くの代表点を掘って繋げる処理をしていた。
- よく考えると，それが使わない水源ならその掘るコストは無駄である。
- 仮想的に繋げたことにしておき，使う水源だけ代表点まで掘る。
- 短いパスの削減なので，得点が少し下がるだけ。
ビジュアライザーの結果がこちら。
seed=0のコストが628422→191412と大幅に減少しました。作戦成功です。
柔らかさ250以下の場所が分かれば概ね良いパスで掘れる，というのも新たな知見です。
提出すると素点は10M点でした。
夜，おふとんの中でふと思いました。
「代表点の個数を増やしてみるのは試したけど，減らす方は試してなくない？ま，情報量が減るので当然点数は悪くなるだろうけど」
4. 4日目(火)
おふとんの仮説検証から始まりました。
代表点を20×20から15×15に変更。
流石に情報量が減るので，堀り方はpower=50から100に増やし，上限も250から1000に上げました。今これを書いて思ったのですが，対照実験をするならば興味のある変数以外は同じものにするべきですね。(中学校で習ったはずなのに…)
やるまでもないだろう，と思っていましたが結果は……素点11M点。
やはりか。
でも代表点を175個減らして上限解放した割にはあまり増えていないような気がします。パラメータ調整をしてもうちょっと様子を見てみよう。
15×15のまま試し掘り上限を1000から300に下方修正すると…素点8.4M点!!
え！20×20は多かったの！？予想外……
情報量が減ったのはそうですが，元々が多すぎたようです。
これからは15×15に決めました。
試し掘り上限は手元でいくつかのケースを試すと，300(固定power値の3倍)が最も良かったです。細かい倍率の調整は後回しです。
そしてビジュアライザーを見て三つ，改良の余地がありそうだと感じました。
- 最大限活用していない盤面
- これまでは盤面を15×15の区画に分け，各区画の中心を代表点としていた。
- この時点で四隅の代表点を結んだ四角形の内側でしか考えていないことになる。
- 盤面によっては，端がその辺りで一番柔らかかったりするので，代表点は縦(横)を14個の区間に分けるように15個とる。
- 代表点間のパス
- 今はまっすぐ掘っているが，ある程度柔らかさが推定できれば良いルートで掘れるはず。特に斜めのパスを掘るとき，縦と横を交互に掘っているが移動順を適切に入れ替えることで掘削マス数は変わらずにコストを抑えられるのではないか。
- 柔らかさの推定する方法を考えたい。
- 利用していない情報
- Cのこと。
- Cが大きいときは固定powerの値を大きくし，クエリ数を抑えた方が良いのではないか。
- 例えば硬さ100の岩盤をpower=50で2回削って壊すとする。C=1なら消費HPは(1+50)+(1+50)=102なのに対し，C=128なら(128+50)+(128+50)=356と大きい。
5. 5日目(水)
あまり時間が取れない日だったので，パラメータをいじって今の戦略がどこまで改善するか調べつつ，考察の材料を集めました。
- 試し掘りpowerを100→90と下げ，上限も300→270と下げる。
- 僅かに良くなることを期待したのと，このpower設定の影響力を調べた。
- 素点8.5M点。僅かに悪化。
- そこまで大きな影響力は無いが，最後に詰める必要はありそう。
- 試し掘りpowerを，C<=16なら50，C>16なら300とする。
- powerをCの簡単な関数にしてみた。
- 素点8.8M点。
- これもそこまで大きな影響力は無いが，最後に詰める必要はありそう。
素点が大きく減少することは起こらなかったものの，試し掘りのpowerの設定はそこまで大きな影響力は無いことが分かった(あくまでこのパラメータのみ変化させただけなので，他の何かと相乗効果があるのかもしれないが見出せなかった)。
ここを詰めるのは後回しで良いことが分かったのがこの日の成果でした。
6. 6日目(木)，7日目(金)
現時点の戦略では良くても素点8M点が限界だと感じたため，別の戦略を考えることにしました。
とりあえず「代表点をとって大まかな岩盤の分布を把握する」という方針をベースにします。代表点は上限までしか試し掘りをしないので，「上限まで掘ったけど壊れなかった」ような代表点の硬さは一律5000(最大)にしていました。コンピュータ視点に立ってみると，これでは周囲8点がすべて硬さ5000(最大)に見えるような孤立点や，家と水流マスの間が硬さ5000(最大)の代表点たちで分断されている場合にはただ最短経路で掘り進めることになってしまっています。いくつかの盤面を観察すると，迂回した方が低コストに抑えられるのに直進していることがあります。この問題や，先述した「代表間のパス」問題を踏まえると，結局，
- 家-水流マス間のパス採掘時にうまく柔らかい岩盤を通るようにできないか
という問題に行き着きます。
そこでパッと思いつきました。
代表点でのグラフによる経路は大雑把なルートとして，実際に掘るときは掘りながらその硬さを基に周囲のマスの硬さを推定し，オンラインで更新する。
マス(y, x)の評定値f(y, x)は次のように決めます。
- f(y, x) = w1*(水流マスとの近さ) + w2*(パス上の代表点との近さ) + w3*(硬さの推定値)
wは重み付けで，w1>w2>w3の順で重くします。最初は水流代表点をシグナルとして掘り進め，ゴールに近くなったら水流代表点ではなく水流マスの方へ進むイメージです。
案としては面白そうです。
ですが，結局断念しました。理由は以下の三つです。
- 掘り進める中で，今掘ったマスの硬さから先の硬さを予測できない。
- そうなると硬さの推定値は機能しないので，結局，パス上の代表点を最短距離で掘るだけになりそう。
- 適切な重み付けを見つけるのに時間がかかる。これは，手元で大量のサンプルケースを一瞬で試す環境にないため。
実現可能な良い案が出ないまま，この2日間は時間だけが過ぎていきました。
半ば諦めた気持ちで寝ました。
7. 8日目(土)
さて，最終日前日。このまま終わってしまうのでしょうか。
やっぱり最後まで諦められません。考察を続けます。
代表点ではなくマス目単位でできるだけ柔らかいパスを見つけるには，マス単位での硬さ推定が必要です。それができれば，代表点で行ったダイクストラをマス単位で行えば上手くいきそうな気がします。ただ全マスを頂点とするグラフだとTLEになりそうなので，代表点で大雑把なルートを決めてからその近くのマスだけを取り出せば計算量は抑えられそうです。もちろん，家と水源が盤面の対角線の両端にある最悪ケースが考えられますが，その場合はダイクストラをやる回数が少ないので良さそうです。また他に家があるならば，先にその家と水源のパスを決める，小さな範囲で考える可能性が高いです。
よし。名付けて，「マクロミクロダイクストラ作戦」です(記事用ではなく本当に名付けていました)。
作戦内容はこうです。
①代表点を試し掘りする。
②代表点からなるグラフでダイクストラして家-水流代表点間の大雑把な"良い"パスを見つける(マクロなダイクストラ)。
③パス上の代表点が全て入るような長方形でマスを取り出す。
④取り出したマス上で硬さ推定値を基にダイクストラして実際に掘るパスを決める(ミクロなダイクストラ)。
⑤パスを掘る。
硬さの推定は，各代表点について，その代表点の硬さ情報をユークリッド距離での円内のマスに反映させて行います。代表点から遠いほど信頼性が下がるので重み付けを小さくします。各マスの推定値は硬さ情報の重み付け平均値です。
よし，やってみよう！の前に，ここで一旦立ち止まります。
最終日前日なのでそろそろ提出回数を意識しないと行けません。あまり無駄な提出はしたくないです。
「マクロダイクストラする必要，本当にある？」
計算量を意識して取り入れていましたが，実際にTLEになるかは確認していません。もしTLEにならないならば，この1ステップによりミクロダイクストラの範囲が制限され，無駄な制約を課していることになってしまいます。
試しに，最初から全マスを対象にしたミクロダイクストラを行ってしまいましょう。
提出すると……素点10M点，実行時間394ms!!
余裕で間に合いました。マクロダイクストラ不要論が支持されました。
パスはほとんど変わっていませんが，これはパラメータ次第な気がします。
パラメータをいじってどこまで良くなるか調べてみます。
先ほどの提出では一辺の代表点の数a=15でした。
また，試し掘りの仕方は一定のpowerで掘るのではなく累計powerが32, 64, 128, 256, 512と指数関数的に増加する方式にし，上限Limit=512でした。
半径や重みはあまりパス探索に影響しないことが分かったので，良さそうな半径(N/a)*√2，重み=(代表点とのユークリッド距離)*(27/100) にしました。
a, Limit に絞って適当に提出を繰り返しました。まずはLimitを固定してaを変化させます。
- a=16, Limit=256 → 素点7.2M点 (いきなり良い)
- a=17, Limit=256 → 素点7.3M点 (aを増やすのはダメそう)
- a=15, Limit=256 → 素点7.0M点 (お！)
- a=14, Limit=256 → 素点6.5M点 (おお！)
- a=13, Limit=256 → 素点6.4M点 (おおおおお！？！？)
- a=12, Limit=256 → 素点6.5M点 (さすがにここまでかな？)
ここに来て格段に良くなりました！！！！代表点は不必要に多かったようです。
次にLimitも変化させて，a×Limitの効果を調べてみましょう。
- a=12, Limit=1024 → 素点6.9M点
- a=13, Limit=128 → 素点6.1M点
- a=12, Limit=128 → 素点6.6M点
- a=14, Limit=128 → 素点6.3M点
- a=16, Limit=128 → 素点6.6M点
a=13, Limit=128 が最も良さそうです！
こう見てみると右下の辺りなんかはがっつり硬い場所を突っ切っていますが，サンプルケース全体で見ると今までより良い解法みたいです。
ただ，山登り(素点の大きさで言うと谷下り？)で試しているので局所最適の可能性があります。本当はもっと多くのパターンを試したかったのですが，「手元で大量のサンプルケースを一瞬で試す環境にない」ので提出して試すしかなく，時間的制約によりこれだけにしました。
8. 最終日(日)
最後まで諦めず考えます。
- 壊れた代表点の割合が一定より低ければ，もう一段階掘ってみる
- 柔らかい岩盤を辿って行ける家どうしを一つの連結成分と考え，それらと水源の間の岩盤をもう一段階掘ってみる
- パスを掘る際のpowerを推定値に依存して掘ってみる
など，思いつく限りのことをやってみました。しかし，どれも結果は振るいませんでした。
素点6.1M点に並ぶ別解法は見つかりましたが，パラメータ調整ができなかったので，僅差で素点の良かった昨日の「a=13, Limit=128の全マスダイクストラ」を最終提出にしてAHC018は終了しました！
順位は暫定177位から最終188位に下がってしまいました。
これは解法の安定性に由来するんだと思います。最後はサンプルケースを大量に回しまくって，提出しなかった方の素点6.1M点の解法と比べてどちらの方が安定して良い得点が取れるか，確かめられれば良かったです。
9. 反省
- 既存のアルゴリズムを使うだけで十分戦えた(青パフォが出た)。
- 今回はそういう問題だっただけかもしれない。 次回以降も参加して，どこまで行けるか試してみたい。
- もちろん使える武器は多い方が良いので勉強もしていきたい。
- 考察→改善→フィードバックのプロセスを回して，いろいろ試せたのは良かった。
- 机上の空論にならないよう，トライアンドエラーを繰り返した方が良い。
- 予想に反して良い結果が得られることもある。
- 逆に悪い結果の時もある。
- (実はこの記事に書いた内容以上にトライアンドエラーをしている)
- ローカルで大量のサンプルケースを一瞬で試せるような環境を構築した方が良い。
- サンプルケースの統計をとって考察に使えるかもしれない
- 効率よくパラメータ調整ができる。
- 解法の評価・比較検討ができる。
ひょんなことからAHCに参加してみましたが，解法が点数でフィードバックされ，それを改善するためにああでもないこうでもないと試行錯誤するのが面白かったです。
また，AHCは思っていたほどハードルは高くないと思いました。
今回の反省を踏まえて，次回も頑張ろうと思います！
それでは！
