はじめに
AtCoder Heuristic Contest それは「絶対の正解がある問題をなるべく早くなるべく多く解く」勝負であるアルゴリズムコンテストとは毛色が異なり、AtCoder公式の言葉を借りれば「最適解を出すことが難しい問題に対し、出来るだけ良い解を作成する」勝負になります。
上位を目指すにはアルゴコンでは馴染みの無い「焼きなまし法」や「ビームサーチ」などの手法が必要になりますが、残念ながら現時点で私はそれらについて理解できておらず、コンテストで使えるレベルには程遠いです。
いつかはそれらの手法も使いこなせるようになりたいところですが、今回のAHC013（AtCoder Heuristic Contest 013 RECRUIT 日本橋ハーフマラソン 2022夏）にはとりあえず今知っていること・今できることだけで取り組むしかありません。
というわけで、AHCガチ素人のしがないアルゴ茶コーダーが、なけなしの初歩的なアルゴリズム知識だけでAHC013に挑んでみました。
初日
参加登録して問題文を眺めながらビール飲んでました。それ以上のことは何もしていません。まあね、長丁場だからね、初日くらいのんびりしたっていいじゃないか。人間だもの。
2日目 まずは正の得点
とりあえずサンプルコードのPython版を私の愛用言語であるCrystalでそのまま書き直して正の得点を得ました。29579点。
Python版のサンプルコードが用意されていたのは大変ありがたかったですね。C++やRustのコードをCrystalで書き直すのは少々面倒なのですが、Pythonからの移植は容易なので。
そしてビジュアライザを眺めてみました。
まずは最初に表示されているseed = 0から見てみましょう。ゲッ！？何この移動しづらそうな高密度！？......まあ落ち着け、こういうのはとりあえず真ん中を見てみるもんだ。というわけでseed = 50を見てみると空白セルだらけで一安心。その後seed = 100を見た上で他も適当にいくつかチェックした結果、たいていの盤面では空白セルが多いことが分かりました。とりあえずは移動が簡単そうな空白セル多め盤面をメインに考えておけばよさそうです。
3日目〜4日目 停滞期
この時点ではまだ問題についてあまり深く考えていませんでした。
とりあえず、サンプルコードで移動と接続が同じクラスに属してセルの状態を共有していたのが今後の改善の際にバグの温床になりそうだったので、個別の関数にバラしておきました。あとはコンピュータの種数（k）行置きに各コンピュータ専用の行を決めて、深さを5以下に限定して幅が爆発しないように抑えたBFSで移動させる（なおすぐに移動回数を使い果たしてしまい中途半端）などのあまり意味の無い小手先の改造を移動部分に戯れ程度に施しました。接続についてはサンプルコードのまんまで何もイジっていません。
当然、この程度で大きくスコアが伸びることはなく、53471点止まりでした。
この時点でのseed = 50, k = 5でのスコアはわずか510でした...。
5日目 爆発
前夜のABCで（お昼に飲んだ牛乳による腹痛で何度もトイレに駆け込むなど色々トラブルがあったとはいえ）初参戦以来のA1完という凄まじい爆死を喫し、レートを一気に55も下げて、皆様のレートの養分となり"""徳"""を積んだ私に競プロの神様からAHCの天啓が下る！...なんて甘い話があるわけもなく、己のあまり出来のよろしくない脳みそで普通に悩んでいました。
しかしモチベーションは前日までとは比べ物にならないほど高くなっていました。昨夜のABCの屈辱は絶対にAHCで晴らしてやる。今に見てろ。
本気でスコアを上げにいくにはまず問題文を冷静に見ることが先決ですね。初日にビールを飲みながら漫然と眺めていただけの問題文と改めて向き合ってみました。
まずはスコア計算法をよく見てみます。同じクラスタに属する同じコンピュータの組み合わせの数によってスコアが上がるようですね。合計ではなく組み合わせによってスコアが上がるということは、全てのコンピュータを満遍なく繋げるより1種でもいいからなるべくデカいクラスタを作った方が良いっぽいことが分かります。
組み合わせ、そう、すぐに計算量爆発しちゃって世のプログラマーたちを苦しめてきたあの組み合わせです。でも今回はどうも味方にできるっぽいです。組み合わせ問題で計算量が爆発するってコトは、この問題の点数も爆発するってコト...？（ちいかわボイス）
組み合わせといえばnCrです。競プロ始めるまで知らなかった（もしくは高校あたりで習ったとしても覚えていなかった）あのnCrです。ググって出てきたnCr計算サイトに100C2を計算してもらったところ、4950という答えが帰ってきました。1種のコンピュータを全部（100個）繋げることができれば1ケースあたり4950点取れるということです。ほほーーーん。
次に制約を見てみましょう。移動と接続の合計がコンピュータの種数×100回までしかできないとされていますね。同種のコンピュータを100個全部繋げる場合、接続だけで1種につき最小でも99回分消費してしまいます。コンピュータの種数の制約が2以上5以下であることから、めちゃくちゃ効率的に最小限の移動だけで理想の盤面を作れたとしてもせいぜい2種分繋げるのが精一杯っぽいです。
以上をまとめると、この問題の目標は「2種のコンピュータで全域木を作成すること」だと推測できます。
しかし移動回数と接続回数についての厳しい制約の中で全域木を2種分作れるような移動なんて、私にはちょっと難しそうです。でも1種分ならある程度なんとかなる気がします。
というわけで、自分の実力の範囲内で出来そうな現実的な方針として「1種のコンピュータについて可能な限り全域木に近いものを作り、余った接続回数で他種も接続」することにしました。
いざ実装！！まずは全種について専用の行を定めていた移動部分を変更して、全域木ターゲットとなる種だけ専用行を定めることで移動回数を節約しつつ全域木を作りやすくしておき、さらに接続部分をイジってコンピュータを1種だけ可能な限り長く接続するようにしてみました。接続方法自体はとりあえずサンプルコードのまんま、右と下に貪欲に接続する方式です。接続を1種に絞った場合のスコアの伸び具合を確認したいので、余った接続回数については一旦放置しておきます。
出力をビジュアライザに放り込んでみると、さっきまで510点だったseed = 50, k = 5が一気に4187点になりました！！！！文字通り桁が違うぜ！！！！！！！！！これはイケる気がする！！！！！！！！！！
ドキドキしながら提出........結果はなんと142057点！！！！！！さっきまで5万点台だったのが一気に14万点台！！！！！！！！！まさしく爆発！！！！！！！！！！！
この瞬間、私はたぶん夜神月の「計画通り」顔になっていたと思います。（知らない人はググってみてね）
ここ最近では最高クラスの脳汁噴出タイムを味わい大満足...と言いたいところですが、ここで手を緩めれば次々に抜かされていくのが競技プログラミングというものです。なんたって今回のAHC013の別名は「RECRUIT 日本橋ハーフマラソン2022夏」ですからね。常に走り続けなければなりません。
この日の夜までに以下の改善を施し、170719点まで伸ばしました。朝の時点で5万点台だったのが17万点台！！！！！！！約3倍ってマジ！？！？！？！？！？
- 余りの接続回数をターゲット種以外のコンピュータで使う
- ターゲットとなる種をループで入れ替えていき、最もスコアが高くなるものを採用
- 現状の移動方式が通用しない空白セルの少ない盤面については、サンプルコードの乱択方式にスコア計算を加えて、スコアが大きくなる移動のみ採用...あれ？？？これと前項のターゲット種変更作戦を合わせると、実質やってることは「多出発山登り法」じゃね？？？？？この記事の看板「初歩的アルゴ知識だけで戦ってみました」に偽りありじゃね？？？？？（この記事書いてる時に気付きました）まあこまけーこたぁ気にしないでくれ！！
周りに水色と青色が多いのがなんだか嬉しいですね。私、けっこう戦えてんじゃん、えへへ。
お盆休み最終日にしてようやくある程度納得のいく成果を出せました。間に合った........。
6日目 再び停滞
さてお盆休みが終わり、本日から憎き平日です。お仕事のスキマ時間をうまいこと使っていくしかありません。お昼休みをAHCに全betし、仕事仲間との会話や仕事のパフォを上げるためのお昼寝はナシ！！大人として何か間違ってる気がしますが、まあAHC期間中だけは許してくれ。
しかしお昼休みを生贄に捧げたものの、本日はなかなか良いアイデアが浮かんできません。血迷って焼きなまし法についてググりまくった末に「うーーーん、この問題に焼きなましを適用するのは天才じゃなきゃ無理！w」などとしょーもない結論に至っていました...。
この日は点数の向上はナシ。再び迎えた停滞期...。泣いても笑っても明日が最終日なのですが........。焦燥感を抑えながら眠りにつきました。
7日目 最終決戦
来ちゃいましたよ、最終日が...。
もう時間が無いので大幅な方針転換は諦めて、現状の解法をベースに小さな改善を積み重ねて少しでもスコアを上げていくしかないです。
まずは接続方法の見直しから。現状ではサンプルコードのまんま右と下に貪欲に繋いでいく方式なのですが、これでは既に同一クラスタに属しているセルと再接続してしまって貴重な操作回数を浪費したり、何ヶ所か格子状に繋がってしまったり、無駄に長い辺を錬成してしまってターゲット種以外の接続を阻害してしまいます。
なるべく最小限の接続だけで、格子状になるのを避けて、辺の長さもなるべく最小で、ターゲット種の全域木を作成したい。最小限の全域木...最小...全域...最小全域木！！！！！
しかし悲しいかな、私はか弱いアルゴ茶コーダー。最小全域木をパッと作れるほどの能力なぞ持ち合わせておりません。でも大丈夫、この世界にはGoogleがある！！
偉大なる師・マスターGoogleに教えを乞うたところ、最小全域木を作るにはプリム法とクラスカル法という2つの道があるそうな。そういやすっかり忘れてましたが、プリム法についてはPAST本で履修済みですね。じゃあクラスカル法で！！
もう時間が無いのに未履修アルゴリズムを選んだ理由？知らないアルゴリズムでやった方が楽しそうですし、何よりクラスカル法の方がなんとなく名前がカッコいいから！！！！（そろそろ読者の皆様お気づきかもしれませんが、私は結構なバカです）
いざ実装。辺が交差できないというルールに注意が必要です。まずはサンプルコードから拝借した接続ループ中で実際の接続や使用済みセルの登録をしていたのをやめて、辺とコスト（接続するセル間の距離）を配列にぶち込んでいきます。全セル見終わったら辺とコストを入れた配列をコストの昇順にソートし、伝家の宝刀UnionFindにぶちこみながらループを回して、接続セル間の空白セルたちを使用済みセル集合に放り込み、UnionFindを利用して既に同一クラスタに含まれているセル同士の接続はスキップしながら繋いでいきます。ほい完成。様々な縛りの中で作ったので完全な最小全域木ではないものの、ビジュアライザを見比べると明らかに無駄な接続が減っていますね。
まずはビフォー
そしてアフター
これだけではスコアは僅かしか向上しません。無駄な接続を減らしたところで、そもそも接続可能な配置になっているセルが少ないことに変わりはないからです。でも無駄な改善ではありません。接続回数を節約したことで、移動回数に回すことができるからです。
節約した接続回数をk = 4以上の場合は移動用に回すことにします。これまでサンプルコードのまんま移動回数と接続回数を半々に割っていたところ、k = 4なら250回、k = 5なら300回を移動用にします。増やした移動回数を使って、今まで行単位でしか指定していなかったターゲット種の位置をループ二周目で列単位でも指定するように変更しました。
提出してみると183958点！！！！ようやく18万の壁を超えたぜ！！！！！！
気づけばもうタイムリミットが目前。この後はせいぜい乱択移動モードにする基準をいじってローカルテスト100ケースで一番良い成績を出した基準値に変更した程度（なお提出するとさっきより少し下がって183829点、乱択の変異内であまり意味の無い変更だったようです）で、大きな改善を施すことなくコンテスト終了時刻を迎えました。
終了直後の暫定順位はまさかの200位ピッタリ。参加人数から考えてパフォーマンスはおそらく青パフォと水パフォの境目くらいでしょうか。
200位！？え！？このままいけば200位の飛び賞で景品もらえる！？！？などと色めきたちましたが、「国内在住の景品対象者かつ景品希望者のみの順位で受賞者が決まる」仕組み上、ちょっと厳しそうですね.......。
終了後はTwitterでおなじみの感想戦。今回の私の予想外の健闘を褒めてくださる方も何人かおられて、お調子者の私は若干浮かれ気味に終戦後のTLを楽しんだのでした。
終戦翌日
システス後も私の順位は変わらず200位。パフォーマンスは惜しくも青パフォ （1600以上）に届かず、1595で水パフォのほぼ上限スレスレ。
無提出者が多い上にまだ競技としてアルゴほど成熟していない感のあるAHCでは、単純な乱択虚無解を提出するだけで緑パフォが出たりするので、アルゴの同一パフォに比べると価値が低いのかもしれませんが、それでもまあ水と青の境目はかなり頑張ったと言えるのではないでしょうか（ﾄﾞﾔ！！
そしてレートはなんと茶をすっ飛ばして一気に入緑！！！！！！倍以上に増えたぞ！！！！！！
AHCはアルゴとは異なりレートが下がらない仕組みなので、私は永遠にAHCで入茶はできないことになります。なんて嬉しい機会損失。
国内在住者の人数を確認するため順位表検索で日本人に絞ったところ188位。海外在住日本人や国内在住外国人による若干のブレがあるとは思いますが、自分より上位に15人前後景品を希望しない方がおられたら170位の飛び賞はワンチャンあるってことですね。なんとかなれーーーーー！！！！！！
おわりに
今までなんとなく参加しては何もできずただ正の得点を得るだけの虚無解を出して終わっていただけのAHCで、今回は自分でもびっくりするくらい戦えました。ようやくAHCの楽しさがちょっと分かった気がします。これはハマっちゃいそう。
最後に今回のAHCでの良かった点と悪かった点と雑感を挙げて、本記事のシメとします。
良かった点
- スコア計算と制約から適切なゴール設定を導出できた
- 迷走した6日目を除けば現実的に自分でも実装できる範囲の解法を無理なく選択できた
- クラスカル法（もどき）の実装を通して今までぶっちゃけよく知らなかったUnionFindへの理解が深まった
- 「UnionFind？なにそれ食べれゆの？」から「UnionFindおいしい！！」になった
悪かった点
- 各seedの確認が不十分で、木が十分に大きくならないケースへの対応が甘かった
- 密な盤面での多出発山登り法もどきの改善をほとんど行わず、サンプルの重いスコア計算をそのまま使い続けていた
- スコア計算と制約をきちんと見るのが遅すぎた（初日か2日目の時点で適切なゴール設定ができていればもっと伸ばせたはず...）
- 色々やりたいこと・やるべきことが他にあったはずのお盆休みを完膚なきまでに破壊し尽くしてしまった
雑感
- AHC序盤における適切なゴール設定は、制約をよく見てパズル的な思考を働かせるというARCっぽい考え方が必要なのかもしれないと思った
- 今回はたまたま焼きなましなどのテクニックが（上位の神々の争いレベルを除けば）あまり必要ではなく貪欲系なアプローチが有効だったからこそ私でもある程度なんとなかっただけで、今後のことを考えるとやはり焼きなましやビームサーチは学習した方が良さそう
- AHC期間中に他のやりたいこと・やるべきことができると思ったら大間違いだぜ！！！！！事前に済ませような！！！！！！！！！
次回のAHCは9月下旬ですね。次はもっと勝ってやらあ！！！！！！！！！！！
お読み頂いた皆様、ありがとうございました！！ではでは(・ω・)ノシ
