AHC022 参加記

はじめに

こんにちは、この記事は、先日行われた RECRUIT 日本橋ハーフマラソン 2023夏（AtCoder Heuristic Contest 022） に参加した際に考えたこと、解法の解説などをまとめた記事になります。どちらかというと、なんでそういう発想になったのか、という参加者視点の話が多い、解説というよりは参加記風の記事となります。

まず結果から言うと、総合１０位と僕にしては大健闘で、ヒューリスティック入橙しました！

ヤッタゼ

 

使用言語はPythonです*1。長期ヒューリスティックでは探査量などが点数に直結することが多いので、より高速なRustを使うことが多いのですが、今回はよさげなPythonによるサンプルコードが提供されていたことや、とりあえず探査ゲーではなさそうな雰囲気を感じたことから、より書きやすいPythonで書きました*2。

時系列順に考えたことや試した解法などを書いていきます

 

序盤（初日、二日目）

開始前

まず時差が８時間ありますので*3、日本時間金曜昼１２時始まったこのコンテストは、午前４時にスタートしました。当然起きているはずもなく、始業スレスレに起き、ドタバタする*4という朝のルーチンをキめました。午後に、金曜というのもあり早めに業務が終わり、そういえば今日始まったAHCの問題でも見るか～と開いた瞬間が僕のAHC０２２の始まりです*5。

問題文を読んだ第一感が、「あ、これ僕が好きなタイプの問題だ！」でした。特にビジュアライザの正誤判定の部分やランダムに加えられるノイズなどから、HACK TO THE FUTURE 2023 予選（AtCoder Heuristic Contest 016） - AtCoder と同じ系統の問題*6なのでは？と感じ、AHC016でAHC長期コンとしては過去最高順位*7を半年前に取っていた身としてはかなり興味をそそられました。ただし、その次の一週間若干プライベートが忙しいことが決まっていたため十分な時間が取れる自信がなく、ふと上司に、「なんか今日始まった競プロのコンテストの問題がめっちゃ面白そうなんですよね、来週ちょっと有給取るかもしれないです」と言ったら、「おーいいね、がんばれ！ちなみに今回はどういう問題なの？」とOKしてくれました*8。

FirstSub

無事プレイ時間を確保できた僕は、まずベイズ推定パートに取り掛かりました。とは言っても僕は数学科卒ではありますが統計は専門外で、お気持ちベイズしかできません。が、各inを独立として考える場合は直感的な遷移*9で事足りるのは分かったので、とりあえずそれを実装しました。Python normal distribution CDF*10で検索すると、numpyやscipyを使う例しか出てこなかったので、とりあえずscipyのnorm関数を使いました*11。各inを順番に調べていき、あるoutである確率が0.99を超えたらそれを答えとして、それ以降のinでのそのoutである確率は0でスタートする、ただしＳ＞200だったらこれだと10000ターン以内に間に合わないので確率0.5以上でＯＫとする（あきらめ半分）をしました

最初の解のコード。サンプルコードをベースにしてるのでまだ比較的綺麗

とりあえず投げたかったので、温度設定*12やロボットの動かし方*13はかなり適当にやりましたが、この時点で小さなSの場合結構いい確率で完答できることが分かり、とりあえず推定パートが作動していることは確認できました。

FirstSubｖｓシード０。S=36なので、こんなに適当でも正解できる

Sが大きい時はほぼ全滅という具合でしたが、とりあえず提出してみると53位とまずまずな感じでした。

Sub 2 - Sub5

熱中してやってたため、ふと気づいたら終業時間をすぎていたので*14、そそくさと帰宅して食べ物を注文し、続行しました。まず、温度配置を本来やりたかった形にし、

２サブ目。隣どうしを判別するための境界線が欲しかったので、真ん中の線は寒くしている

次にロボットの動かす先を工夫したくて、各Inにつき、一番確率が高いOut二つを一番区別できる＝そこから動かしたときにたどり着く２部屋の間の温度差が一番激しい動かし方が、一番良いと考えました。が、各ターンごとにL＾２通りすべてのロボットの動かし方を試す方法を実装して提出すると、TLEとなりました。ここでpypyに乗り移る必要性を感じ、どうにかして正規分布のCDFをNumpy,Scipyなしで計算する方法がないか調べた結果、mathライブラリにerf関数があることを知り、それを使って正規分布のCDFを手作りしました。

また、各アウトのペアにつき温度が決まった時点で上の最善の動きができることから、前計算でいいじゃん、となり前計算にしたところ２０００ｍｓで間に合うようになりました。

５サブ目（AC3回目）。各outの対につき、そのOut二つから出たロボットが計測する２つの部屋の気温の差が激しくなるようなロボットの動かし方を前計算しておく。

このころの順位は覚えてないですが、たしか２０位台後半とかじゃなかったかな

Sub 7~

この「ペアの行き先の温度差を最大化する」、という考えの延長線上で、「そもそもすべてのペアの行き先の温度差がめっちゃデカいような動かし方があることが保証された温度配置にしたいな」と考えたところ*15、L/2正方形の暑いエリアがあったらどの二つのoutでも片方が暑いエリア、もう片方が寒いエリアになるように移動できるな、と気づきました。

Sub 7　Seed0。左上が暑くてそれ以外寒い。温度はSによって変える

これをテストしてみると点数が一気に数倍に伸び、興奮して提出したところ一気に２位になりました

今年の目標だと思っていたAHC入橙がいきなり近づき入橙ラインを強く意識するようになりました。

音楽を聴きながら実装してたんですが、ちょうどその日にGYARIさんが３年ぶりにボカロ・ボイロ新曲を出してて、めっちゃノリノリにずんだしながら実装してました。(4) ずんだもん「チャンネル登録よろしくお願いします」 - YouTube。単純な性格をしているので、このだいぶ嬉しい時間にめっちゃ聞いた曲ということで僕の中でだいぶ好きな曲というか動画になりました。*16

ここらへんでテストを一個一個手動で回すのがめんどくさくなったので、テストのコマンドを実行して結果を集める雑スクリプトを書きました。

雑スクリプト。点数集計＋MeasurementとPlacementのスコアの割合、別の解との比較などができる

実はAHC016の反省からクラウド実行環境をAzure上に作っておいてはいたのですが、Azure Container Instancesの制約や使えるクレジットの上限の低さ*17から、あまり使いたい気分になれず結局一回も使わず終わりました。ローカルでシングルスレッドで回してたのですが、せめてローカルでマルチスレッドできるようになったらもうちょっといいのかも？次までに調べておきます。

ここから数サブミットはパラメータ調整をしました。さっきまであきらめていたS＞２００なども太刀打ちできるようになっていたので諦めモードの範囲や挙動などを変え、また止める精度も0.99から0.999に変えたりしました。本来序盤でパラメータ調整をするのはあまり良くないのですが、目の前の一位を取りに行ってしまいました。まあ、なんというか、心理戦（？）を仕掛けにいったというわけです（？）。無事、一位に躍り出ることに成功しました。

最後に、ロボットの動かし方の前計算で、同じ差の動かし方の中だと一番距離が短い動かし方を選ぶようにするとスコアがグーンと上り相対スコア４５B（９０％）に達しました。この温度がとる値が二つしかない温度配置だと、効果的な改善だったのかなと思います

過去の経験から、こっから一気に抜かれるんだよな～と思いながら寝ました。

Sub13～

起きたら抜かされるというのが、今までの常だったため、起きたときまだ抜かされてなくてびっくりしました*18。

「すべてのペアの行き先の温度差がめっちゃデカいような動かし方があることが保証された温度配置にしたいな」というとっかかりを得てこの考え方の一定の正しさを確信した僕は、もっと低Placementコストでこの条件を達成できないかを考えました。よくよく考えると、左上と右下の正方形さえあれば、すべてのoutペアの移動先が存在することに気づきました*19。残りのエリアは手作りで傾斜になるようにして*20、提出したところ点数が２０％ほど伸びました。

Sub１４　Seed0。右上と左下は手作り

Sub15Seed0。縦横並び用の赤マスは１マスで足りることに気づき、配置コストをさらに下げる。

手作りで緩衝材を作るのではまだまだ無駄があると感じたのですが、配置コストを最小化する厳密解が求まるかを考えたところ、ややこしすぎる＋境界条件に影響を受けすぎて頭が爆発したので、†コンピューターのパワー†を使ってどうにかできないか考えました。

最適解は自明に存在するので最適だった場合のことを考えると、各マスにつきその周りとのコストを最小限にするようになるはずなので、隣のマスΣ(Xの隣のマスの温度-Xの温度)^2を微分すると、最適が周りのマスの平均であるときだということが分かります。ということで欲しいのは各マスにつきそのマスの温度が周りのマスの平均になる分布に持っていく方法ですが、ここで、温度を確率として捉えるとグリッド上のランダムウォークのStationary Distributionの式を満たすことが分かります。高温・赤固定マスからは確率１で動き、低温・白固定マスには吸収される境界条件を持ったランダムウォークは、Recurrentであることが知られており、かつδMixingTimeがO(log(頂点数))なので*21、「各マスごとに周りの平均を取る*22」というのをすべてのマスにlogL*logT回ずつやるだけでほしい分布に収束することが分かりました*23。これを実装すると、予想通りお気持ち緩衝材より効率的に配置コストを削減でき、スコアが数パーセント伸びました

Sub 16 seed 0。配置コストがさらに下がってる

なんか大学で学んだことをちょっと使った気がして嬉しくなりながら、もう少し考えを進めてみると、そもそも一辺L/2の正方形まるまるなくても、「すべてのペアの行き先が赤白になるような動かし方があること」は満たせることに気づきました。具体的には、片方L/4L/2の長方形でいいし、

Sub17Seed0。点数はなんか落ちてますが。。。

さらによくよく場合分けしながら考えると、両方長方形でも成り立つことが分かりました。*24

Sub18Seed0。実はこれでもすべての点のペアが片方赤片方白になるようにできる。

配置コストをかなり下げた結果、観測コストとのバランスが崩れ、調整して点数を上げるためにまたパラメータチューニングをしました*25。Shun_PIさんと一位と二位で抜いたり*26抜かれたり*27抜きなおしたり*28と非常に忙楽しい週末を過ごしました。日本在住勢と生活リズムがずれている分、ターン制バトルみを感じれて面白かったです。

中盤（３日目～８日目）

中盤（平日）では、大枠がすでに決まってしまったコードに小技を詰め込みまくるゲームをしていました。大きく引き離されることがなかったため、大枠から考え直す理由が特になく、周りの上位も同じようなゲームをしている可能性が高いと思っていました。また、一位を目指すなら独創的なことをしないといけないと思いますが、入橙がとにかく一番大事だったので、より安全に地道に点数を伸ばしていく作戦を取りました。

この期間に入れた小技を分野別に分けて紹介します。

配置

Sがかなり小さい時は、ｘ＝０ｙ＝０でほぼ判断できるようにすることによってできないかと考えました。具体的には、各outの温度が離れていると、そもそもロボットを動かさずにかなりの精度で判別ができます。温度のコストを最小限にするために、一番外に近いOutマスからi番目のOutマスについて、温度をi*Sに固定し、残りは最小になるように動かす、をしました。

結果的に、S＜＝９の時はこのような配置をするようにしました。手元で動かした際、S＜＝９において数十％の得点増になっていたし、最終的なスコアでもS=1とS=4においてはスコアが全体２位だったらしいので、この配置がかなり良かったんじゃないかなと思います。

最終提出Ｓｅｅｄ１０（Ｓ＝１）。かなりなだらかな傾斜だが、各Ｏｕｔにつき差は少なくとも１ある（ほとんどの場合それ以上）になっているためすごく低コストに観測できる

Ｓ＞＝９以上の時は、まず赤のマスと白のマスを完全に同じ熱さにするのは効率が悪いと考えました。というのも、ペナルティーは温度の傾斜の二乗に比例するので、赤長方形と白長方形が全部同じ熱さである状態から、そのなかですごくゆるい傾斜がついている状態にすることは実質無料なのですが、少しつけることにより赤長方形内にあるＯｕｔマス２つをより低コストで判別できるようにできるからです。ただし白長方形と赤長方形が角で接する点での激しい傾斜は保たないといけないので、赤長方形と白長方形の温度も、周りとの平均を取る、ただし赤長方形に入っていたらＸ以上、白長方形に入っていたらＹ以下になるように強制する、という遷移を取り、温度が固定の「めっちゃ赤いマス」「めっちゃ白いマス」を一個ずつ指定し、そこから傾斜を最小コストになるようにつけることでスコアを１％ほどのばしました。

また、ＳとＬの組み合わせにより、赤マスと白マスが角で接してる、という状態がなくてもかなり効率的に判別できる場合がありました。この接してる角マスを強制Ｘ以上・Ｙ以下から取り除くことにより配置コストはかなり下がるので、パラメータをいろいろ変えながら実験して一部のパラメータでは赤と白の間に一行緩衝材を開ける、などをしました。

また、トーラス状の世界で初期配置を「左上」「右下」に固定するのは特に意味を持たないので、一番温度差が激しい赤と白の境界地点により多くのＯｕｔマスが来るように初期温度ずらしました。これも１％ぐらい伸びた気がします。

最終提出Seed０うっすらと平行移動した赤い長方形と白い長方形が見え、はっきりとめっちゃ赤いマスめっちゃ白いマスが見える。

Inの選択

各Inを独立としてみる作戦は非効率と考え、各Inが各Outである確率を全部書いた表をもって遷移するようになりました。ただし、ベイズ論をちゃんと勉強したことがないことが災いし、条件付き確率があまりにも複雑と思い、かなり雑な遷移を最終的に採用しました。

雑な遷移。正規化する方向とか工夫できていないし、そもそも確率ではなくなっている（各行の和が１にならない）

本当は、「InA１がOutB1に行き、InA2がOutB2に行く確率」などをもって遷移したかったのですが、計算量が爆発し、また上の正規化を縦横何回か繰り返すとかもやってみたのですがなぜかスコアが落ちたので採用しませんでした。

ロボットの動かし方

「Out２つにつきどこに行きたいか前計算しておく」という基本戦術は結局変わりませんでしたが、一番確率が高いOut2つが一番いいと思ってるものを毎回採用するのはあまり効率が良くないと考え、各ペアにつき、ほぼ一番いい動かし方（一番いい動かし方の1.2分の１以上）のリストを全部持って置き、さらに一番確率の高いOutのペアではなく、一番高いOut１と、２番目以降のすべてのOut２のそれぞれのペアにつき、票数をOut2の確率で重みづけした投票制にしました。これにより二つだけ判別するのではなく一気に複数のOutの可能性を判別していく形になり、数パーセントスコアが伸びました

投票パートのコード

各Outペアについてのロボットの動きを評価するにあたり、だいたいlog(正規分布のPDF)＝温度差^2ぐらいの嬉しさがある*29気がするので、温度差＾２/測定コストで評価してましたが、ふと温度差^1.5/コストにすると点が伸びたのでそちらを採用しました。なんでそっちの方がよかったのかは謎です。

打ち切るタイミング

各Inごとに順番にやるわけではなく、確率の表全体をもって遷移するようになったので、打ち切るタイミングも工夫できるようになりました。特に、間違えるとしたら基本的に二つをスワップする間違え方をする、ということに着目し、「スワップできる確率が十分低ければOK」ということにしました。

具体的には、まず各行の最大確率が０．９以上になるまで、最大確率が一番低いInを選んで回します。そして、各行のペアにつき、最大が逆になる確率が十分あったら（in1の最大がout1でin2の最大がout2の場合、p[in1][out2],p[in2][out1]が両方十分に大きければ）、そのInを選んで続行、すべてのInのペアで逆になる確率が十分小さかったら打ち切り、としました*30。

仕事の合間もAHC、仕事から帰ったらAHCという具合に微改善をたくさん積み重ねていった結果、最後の週末前でまだ３、４位、さらに１位と数％差、という僕としては非常に良いポジションにつけることができました。

終盤（８～１０日目）

終盤にJirotechさんが一気にスコアにして１０，２０％飛びぬけました。

 

過去数日間１位から１，２％差で争ってた自分はすっかり、みんな同じゲームをしていると思っており、１％でも伸ばす微改善、パラメータチューニングをやっていたので、かなりびっくりしました。しかし時すでに遅し、ここから大きな方向転換をするわけにもいかず、最後の数日はパラメータチューニングをぶん回していました。特に、打ち切りのタイミングをどこにするかはかなり非自明でスコアに大きく響くわりに試行回数が大量に必要なので*31、夜回しっぱなしにして寝る、などをして調整しました。最終日となると皆さんが鬼のように追い上げてきて、かなり怖い思いをしながらせっせとテストを回して数字をちょっと変える、を繰り返しました。有給まで取って、ここで入橙を逃したらかなり後悔する、という気持ちもあり、最後に暫定８位になりほぼ入橙確実になった時は、とにかくほっとした気持ちが一番強かったです。

終了後

もし日本在住だったら、１０位以内に入るかで入賞*32が決まるので、かなりドキドキだったと思うのですが、僕はいずれにせよ賞金対象じゃないため割と気楽にいれました*33。皆さんの解法を見て、ベイズ推定パートを除きかなり別ゲーをしていたことにかなり驚きました。特に一点だけ熱くする、という手法をJirotechさん含みかなりたくさんの方がやってて、L/4長方形作戦がほかに一人も見つからなかったのはかなり驚きました*34。

クラウド実行を活かせなかった点や、大枠を早めに決めてしまい柔軟に変えていけなかった点*35、実行時間のテストが甘くてシステスで５，６ケース実質TLE*36してた点など反省点は多いですが、問題が非常に面白く、大変楽しいコンテストでした*37。ありがとうございます！

表彰式のグッズも一万円もほしかったし、懇親会に行っていろいろな方のお話をすごく聞きたかったですが、またそういう機会があるように、今後とも頑張っていきたい所存です。

 

*1:新ジャッジ移行前なので、PyPyを選択

*2:まあ必要そうだったらあとでRustに翻訳すればいいか～という気持ちで

*3:当方英国在住勢のため

*4:そして余裕で遅刻

*5:弊社では業務時間の５％を「自己研鑽的ななにか」に使うことが認められていて、競プロもOKということになってます

*6:ベイズ推定チック

*7:１３位

*8:前述のAHC０１６に関するLT Xユーザーのゆうっうっう🛸@ 多次元配列は一次元に直すさん: 「AHC016プレゼンのスライド（上司の許可は取ってます） https://t.co/5643efEHDM」 / X (twitter.com)  などを会社でやっていたのもあり、チームメンバーや上司にはある程度理解してもらえていることに感謝

*9:Xを観測した場合、各outYにつき、X-0.5からX+0.5になる確率を求め（ただし0や1000を観測した場合0.5以下を観測する、999.5以上を観測する確率を求め）、outがYである確率にそれをかけて、確率の和が１になるように正規化する。ここら辺は最終的には上位勢はほとんどみんなやっていたと思いますので詳細は割愛

*10:Cumulative Distribution Function＝確率変数Ｘがｘ以下を取る確率の関数

*11:ジャッジ更新前なので、Pypyでは使えず、とりあえずバニラのPythonで提出しました

*12:真ん中を熱くしてなだらかに外を涼しくする、というのをやりたかったけど、サンプルコードに引っ張られて出口のある温度だけしか設定してない

*13:XとYを順番に１ずつ増やしていく

*14:これで遅刻とチャラ

*15:上の真ん中に近づくと熱い＋十字の白だと近いoutのペアは判別しやすいんですが、遠いoutのペアの間に大きな温度差を作ることができません

*16:海物語でLuckyとかST中の曲が好きになるのと同じやつ。通常時テーマも好きだけど

*17:２日ぐらい持ったまま放置しておくと一か月の無料枠の１５０ポンド分全部使い切られちゃう。。。

*18:お盆休み最初の土曜日の日中ということで、帰省とかで忙しかったのかな

*19:左上右下という関係の場合そのままだし、右上左下という関係の場合盤面の右上の右にある赤マスと盤面内にある白マスを使えばいいので

*20:残りのマスは判別に基本的に使わないので、とにかく配置が安いようにすればいいため

*21:ここら辺ちょっと僕の知識があやふやですが

*22:Transition Matrixを一回かける

*23:物理に詳しい人達はポワソン方程式がなんとか、みたいなことを言ってたので、専門によってはそちらの方がしっくりくるかも？多分連続か分散かという違いで実質同じ考え方

*24:お気持ち手動緩衝材だとこの配置を変えた時にいちいち書き直さないといけなくなっていたと思うので、この時点で自動化できていてよかったです。

*25:こいつの序盤パラメータ調整フェーズ多すぎじゃないか？

*26:

ゆうっうっう🛸@ 多次元配列は一次元に直す on X: "一位ギリ奪還！ふおーーーーーー₍₍ ◝( ˘ω˘ )◟ ⁾⁾ https://t.co/joRxKT4ORd" / X

*27:

ゆうっうっう🛸@ 多次元配列は一次元に直す on X: "https://t.co/S0H5HGDheL" / X

*28:

ゆうっうっう🛸@ 多次元配列は一次元に直す on X: "やったぜ（満身創痍） https://t.co/Q4WymaqD59" / X

*29:エントロピーというそうです。そういえばそういう概念あったかも。。。

*30:Sによりますが0.002程度が実権を回したところ一番スコアの期待値的によさそうでした

*31:誤答する確率を知る必要があるため

*32:１万円もらえる

*33:入橙は絶対にしたかったのですが、ボーダーが２０位ぐらいになることが分かったので、まあまず大丈夫でした

*34:長方形作戦は長方形作戦で、すごいと言ってくれる方が多くてうれしかったです

*35:序盤最上位だったこともあり、正しい大枠を使っているという自信がありすぎました

*36:プレテストだと４秒中３０００ｍｓで終わってたのに。。。

*37:色変したんだし楽しいに決まってる