2024/04/07 19:00 - 23:00 に開催された AHC 032 に参加した。 この記事では今回の参加について振り返る。
問題概要
N x N (N = 9) のグリッド上に数字が書かれている。 グリッド上の 3 x 3 領域を選んでスタンプを押すことで、スタンプに書かれている数字をグリッド上の数字に足すことができる。 最終的に、グリッド上の各マスの数字の mod 998244353 の和を最大化したい。
結果
最終 87 位 (パフォーマンス 2130)
前回 (AHC 031) に続いて 2 桁順位。 短期コンでは今までで一番の成績になった。
解法
基本で貪欲左上から合わせていく。 左上の 6 x 6 はスタンプの左上位置を合わせて押したあとの mod が最大となるように 1 回だけ押す。 右上の 6 x 3 ブロックは、各行あたりスタンプを 3 回ずつ使って mod の和を最大化。左下 3 x 6 も同様。 最後に残る右下 3 x 3 ブロックはスタンプ 6 回使って mod の和を最大化。
この配分だと 3 回分スタンプが余るので、余った分は左上ブロックに適当に配分。 余りの分配先のマス集合を変化させて山登りで時間いっぱい回す。
提出コード
https://atcoder.jp/contests/ahc032/submissions/52152178
経過
まずは適当なランダム解法とスコア計算を実装。 最初問題文を読み間違えて mod の和ではなく 和の mod の最大化だと勘違いしていて、スコア計算が合わないことで気づいた。
焼きなましできなくはなさそうだが、1 回の操作の影響範囲が大きいので焼きなましだと近傍つくるのが難しそう。 焼くにしても、とりあえずある程度良い初期解をつくっといたほうが良さそうだと思ったので、とりあえず貪欲で良さげな解をつくる。
一回合わせた場所は後から触らないようにすることで、左上から 1 マスずつ合わせていくことができるので、その方針で実装。 まずは右下の L 字領域は無視して左上 7 x 7 マスで 1 回ずつスタンプ押して合わせていく方法で実装。 さらに、右下の L 字について 3 列ずつや、3 x 3 ずつ各スタンプ 1 回で最大化する実装を書く。 スコアは 10.70T。 ここまでで 59 分。
だいぶ実装がコピペで膨らんでいたりしたので一回リファクタリングをはさむ。 まだこの時点では、まとめて最大化している部分で赤に近いスコア低いマスが目立っていたので、こちらに余りのスタンプ回数を使いたい。 そこで、同じ場所に複数回スタンプを押す際のパターンを全列挙して一番良いパターンを選択する実装を書いた。 スタンプの回数の配分などが概ね落ちついた時点でスコア 11.49T。 ここまでで 133 分。
この時点では実行が 48 ms でだいぶ余っているので、左上ブロックでスタンプを 2 回消費してるマスを適当に変えて複数パターン試してみることにする。 最初単純に乱択にしていたが、後から少し工夫してマス集合を 1 箇所ずつだけ変化させる山登りにしてみる。 貪欲パートがまあまあ重く、山登りの繰り返し回数はあまり多くならないので焼きなましまではしなくてもいいかなという判断。これでスコア 11.59T。 ここまでで 179 分。
最後の 1 時間はスコア計測スクリプトを書いてパラメータ調整を主にしていたが、結局スコア上昇はなし。 終盤は同じような提出を複数回やってもスコアが下っているような気が...。終盤は駆け込みで提出が増えて重いのか、繰り返し回数が減ったりしてるんじゃないかという気がしなくもない。
おわりに
今回は短期 AHC ではじめてある程度良い成績が出たので嬉しいです。 上位陣とおおまかには近い方針を引けている気がするけれど、一方でまだ超えられない壁があるようにも感じます。 細かい点を含めて他の解法などを読んでみて、差が出る場所を考えてみたいと思います。
