AHC032お疲れ様でした！11,845,290,951,426点で2位（perf. 3279）を取ることができました。今回も解説記事を書いていきます。

問題概要

グリッドにスタンプを押して $\mathrm{mod}\ 998244353$ の総和を最大化してね。

解法

概要

一度に複数のマスの値を $998244352$ に近付けるのは難しそうなので、できるだけ1マスずつ順番に揃えていくことを考えました。

一気に複数マス揃えるのは難しくても、1マスだけであれば20個あるスタンプのどれかを押せばある程度良い感じの値になりそうです。~~スタンプが20個あると考えると、ざっくり計算で端以外は平均誤差を2.5%くらいに収められそうな気分になります。~~*1 端の方はどうしても一気に揃える必要があるので、そこは諦めて頑張ることにします。

この考え方をもとに、確定させたマスの値だけをスコアとして考えたビームサーチをしました。動画にするとこんな感じです。

ビジュアライザ動画版 (seed=0, score=78,951,229,205点)

貪欲について

ビームサーチに手を付ける前に、まず貪欲について考えましょう。

盤面全体のスコアではなく、確定したマスの値だけをスコアとするのが大事です。入力は一様ランダムなので、確定していないマスを全く考慮せずにスタンプを押しても明確に悪くなるということはなく、あとで辻褄合わせをすれば良いので割と何とかなりそうです。こうすることでほとんどのターンで以下の問題を解けば良いことになり、問題がかなり簡単になります。

整数 $a_{i,j}$ と数列 $s_{m,0,0}\ (0\le m\le M-1)$ が与えられる。 $(a_{i,j}+s_{m,0,0})\ \mathrm{mod}\ 998244353$ が最大となるような $m$ を求めよ。

これはあり得るスタンプの押し方を全探索すれば求めることができます。同じ場所にスタンプを複数回押すことができる（スタンプを $k$ 回押す方法は重複組合せを考えると ${}_{20}H_k$ 通り）ことに注意してください。

端の部分については3個または9個同時に決める必要があるため難易度が上がりますが、結局やることは全探索です。*2 この貪欲を実装すると、以下の動画のようになりました。

貪欲解法のビジュアライザ (seed=0, score=73,539,605,477)

ビームサーチ

上記の貪欲を素直にビームサーチ化します。 $t$ マス目まで確定させた状態をビームサーチの $t$ ターン目（ $0\le t\le 49$ ）とし、確定したマスの値の総和をスコアとしました。

確定させる順番は以下の図の通りです。青は一度に1マスだけ確定する箇所、緑は一度に3マス確定する箇所、赤は一度に9マス確定する箇所です。なぜ縦→横→縦→横と交互にやっているかについては後述します。

ここで、マスごとにスタンプを押せる回数に以下のように制限をかけました。

端以外のマス（青いマス）であれば最大 $2$ 回
下端・右端のマス（緑のマス）であれば最大 $3$ 回
右下端のマス（赤いマス）であれば最大 $4$ 回

加えて、 $t$ ターン目までにスタンプを押した累積回数が $\lceil L_t \rceil$ 回を超えないように制限をかけました。ここで、 $L_t$ はターンごとに以下のように増えていくものとします。

端以外のマス（青いマス）であれば $+1.5$
下端・右端のマス（緑のマス）であれば $+2$
右下端のマス（赤いマス）であれば $+3$

上記のお気持ちとしては、「緑マス3つや赤マス9つを一気に揃えるのは難しいので、できるだけ手数を温存しておきたい。ただし、青マスでも2回押したくなるときがたまにあるので、回数が余っていれば2回押しても良い」といったものです。

余っている手数に応じてボーナスをスコアに加算している方もいましたが、私は特に行いませんでした。

細かな工夫

値を確定させていく順番を縦→横→縦→横と交互にしました。これは、3マス揃えが成功する確率がかなり低く、ここで大きくビームの多様性が損なわれてしまうためです。*3 これについては公式のAHCラジオの解説がかなり詳しいので、そちらをご覧頂けると良いかなと思います。
スタンプを同じ場所に $k$ 回押す方法は重複組合せを考えると ${}_{20}H_k$ 通りあるので、それを前計算してスタンプ $k$ 個が重なった1個の仮想的なスタンプと考えました。こうすると少し高速化ができ、後々の実装も少し楽になります。
ビームサーチの手法はいくつかありますが、今回はいわゆる木上のビームサーチ *4 *5 を採用しました。これは高速化目的というよりは、ライブラリ化して慣れているので短期コンでバグりにくいだろうということを期待して使っています。ビーム幅は最終的に3000くらいになりました。
これはコンテスト中には気付かなかったのですが、Shun_PIさんの発言を見て枝刈りを入れるようにしたらスコアがかなり伸びました。高速化勝負ではかなり有効なようです。

コンテスト中の立ち回り

今回は序盤で解法を絞れず迷走したのですが、上手く立て直して最終的に2位まで持って行くことができました。立ち回りについては何かしら参考になるところもあるかもしれないので、できる限り再現してみます。

問題の理解と諸々の準備（～0h10m）

問題を読みつつ、ローカルでテストケースを回す初期設定をしておきました。めんどくさいのですがこれを先にやっておくと後々解法ごとのスコアの比較がやりやすくて便利です。

0 とだけ出力するコードを書いてビジュアライザを見てふむふむします。提出すると6.108T点でした。

とりあえず貪欲（～0h30m）

ふむふむしましたが、よく分からないので貪欲をします。「マス $(i, j)$ にスタンプ $m$ を押す」ことを考え、押したあとの全体のスコアが最大となるような $(i, j, m)$ の組を全探索します。押してもスコアが上がらなくなったらそこで打ち切ります。

入力の受け取り処理・スタンプを押す処理・スタンプのロールバック処理・盤面全体のスコアを計算する処理・答えの出力処理を準備して雑に貪欲を書きます。この段階では差分計算などは考えず雑で良いです。

実行してビジュアライザを見てみると、まだかなり赤いところが目立っていてあまり筋が良くないことが分かります。提出すると9.476T点でした。

とりあえず焼きなまし（～0h38m）

スコア計算とスタンプを押す処理・ロールバックする処理が準備できているので、あとは近傍を適当に作れば焼きなましができます。問題をパッと見た印象では焼けそうにも見えるので、さすがに愚直に焼ける問題は出してこないだろうと思いつつ、近傍も滑らかにならないだろうと思いつつ、すぐ書けるので念のため焼いておきます。8分で焼けました。

スコアは10.320T点で、上がりはしたもののまだまだ赤いところが目立っていてやっぱり筋が良くなさそうです。この時点で上位は11Tは取っていたのと、上位でも同点の人がちらほらいたため、やはり筋の良い貪欲があるのだろうという推測を立てます。

色々な貪欲を試す（～1h05m）

良い貪欲が見つかるまでひたすらコードを書いてはビジュアライザとにらめっこします。同じ場所にスタンプを押すのは一度に一回までと制限をかけていたので、その制限を取り払って2～3回まで許可するようにしました。

提出すると10.569T点で、焼きなましよりは筋が良いのですが上位陣には全く届かなさそうです。かなりまずいなという気分になってきて焦ります。

1マスずつ揃える貪欲に辿り着く（～1h20m）

最上位のスコアは1.15Tくらいになっていました。*6 ここから情報を得てみます。

150ケースで1.15Tということは、理想的な盤面の95%くらいにはなっているということです。一度に9マスずつ揃えていってこのスコアを出すのはかなり難しそうに思えました。一方で、1マスずつ95%超えの値にしていくのであればなんとなくできそうな気がします。

ということで、左上7x7マスの領域について1マスずつ揃える貪欲をしてみることにしました。端の方が残ってしまいますが、よく分からないので*7さっきの焼きなましでを流用してお茶を濁します。これを実装すると10.916Tで、さっきよりだいぶ良くなっていそうです。これをベースに改善してみることにします。

1マスずつ揃える貪欲の改善（～1h50m）

スタンプを押す回数が余ってもったいないので、同じマスにスタンプを2回まで押して良いことにしました。

また、端の方のマスもちゃんと3マスずつ揃えることにしました。これを提出すると11.369T点で、悪くなさそうです。

ビームサーチ化（～2h40m）

今は $t$ ターン目の確定済みのマスの値の総和が最大になるような貪欲をしていますが、 $t$ ターン目で多少損しても $t+1$ ターン目でピッタリハマるスタンプが使えるようになるならそちらの選択肢を選びたいです。というわけでビームサーチに発展させることにしました。

事前にライブラリ化していた木上のビームサーチを使いましたが、なんだかんだ実装に1時間程度はかかりました。奇跡的に大きなバグもなく、提出すると11.620T点で良い感じです。

探索順の変更（～2h45m）

この段階では単純に左から右に1マスずつ揃えていましたが、ビジュアライザとにらめっこしたところ終盤に3マス揃えが集中していてかなり嫌な気持ちになりました。そこで、探索方向を縦→横→縦→横に変更してみました。ついでに実行時間にもかなり余裕があるので、ビーム幅を500から1000に変えてみます。

提出すると11.714T点で10位になりました。この方針であればかなり筋が良さそうなので、あとはこれを詰めていくことにしました。

トイレ（～3h00m）

腹痛には抗えませんでした。

諸々調整（～4h00m）

以下の諸々を調整しました。序盤で整備したローカル実行環境が役に立ちました。

各ターンでの最大操作回数の調整
ビーム幅を動的に調整して実行時間を目一杯使うようにする
高速化
高速化
高速化

最終的に11.845T点となり、2位になることができました。

感想

パッと見焼けそうにも見えるのですが、実は焼けなくて強い貪欲があるという点が結構非自明で面白い問題でした。解法が見つかってみればなるほどとなるのですが、そこに辿り着くのがなかなか難しいですね。今回はスタートが出遅れてしまったのですが、巻き返して想像以上の順位になれて嬉しいです。

AHCでビームサーチを見たのは久し振りだったのですが、AHCラジオで紹介された各種テクニックは初めて聞くものばかりでかなり勉強になりました。こういうテクニックを知っているかどうかで最後の一押しができるかどうかが変わってくるので、どんどん手札に加えていきたいですね。

そしてここ最近かなり調子が良くなってきました。昨年末のHTTF2024から6位→353位（は？）→writer→1位→5位→2位と来ていて、GP30的にもかなり良い位置に付けているなと思います。正直昨年の成績からするとAWTFは厳しいかなと思っていたのですが、気付けば手の届く位置に来てしまっているので、この調子で頑張っていきたいです。

最後に、writerのeijirouさん、adminのwataさん、今回も面白い問題をありがとうございました！次回も楽しみにしています！

*1:これは嘘で、誤差の期待値は1/22=4.5%になります。 → https://kiri8128.hatenablog.com/entry/2024/04/08/021208

*2:焼きなましなどもできなくはないですが、全探索に比べて探索効率が上がるわけではないと思います。強い人は枝刈りやバケット化などをして効率化していたようです。

*3:多様性自体はあるのですが、筋の良い状態の種類数がかなり減ってしまいます。

*4:https://qiita.com/rhoo/items/f2be256cde5ad2e62dde

*5:https://eijirou-kyopro.hatenablog.com/entry/2024/02/01/115639

*6:うろ覚え……。

*7:真面目な話、この方法の筋が良いか手っ取り早く確認したかったという側面が強いです。