問題

$n \times n$ のマス目に $1 \sim 9$ の数を書き込む。 横か縦一列に見て和が $B_1, B_2, B_3$ のいずれかな区間があれば $B_i$ 点貰える。 点数を最大化せよ。

解法

ふつうに焼きなまし。 適当 1 点更新が強く、近傍の改善もしたけどはあまり有効でなかった。 スコア差分の計算はしゃくとりぽくやる。 試行回数は $2 \times 10^6$ ぐらい。

他の人の解法を見るに、ひたすら高速化するだけの勝負だったぽい。 「$1$ 回の試行」の定義にもよるがとりあえず $10^7$ 回に乗せる必要はありそう。 $8$ 時間や $1$ 週間あれば天才が生えてくる可能性はあるが $2$ 時間だと初手愚直をひたすら定数倍が最適ムーブとなる。

リンク

他の人の解法

ats5515 さん: 1652578 点 1 位

提出コードを借りてきて見てみると $2 \times 10^7$ 回試行があるので、彼の勝因は高速化ぽい？

math さん: 1631928 点 2 位

tanzaku さん: 1625536 点 3 位

gasin さん: 1609480 点 4 位

試行回数は $5 \times 10^6$ らしい

sumoooru さん: 1605376 点 5 位

同じことやってる。温度調節での 1 万点は誤差な気がするが

koyumeishi さん: 1591239 点 6 位

ビームサーチを 6 位に乗せれるのガチプロって感じがする。すごい

hos_lyric さん: 1587092 点 7 位

betrue12 さん: 1586162 点 8 位

tomerun さん: 1581564 点 9 位

キャッシュのために $90$ 度回転かしこいけど、 $30 \times 30$ なので $900$ byte だし気にする必要なさそうに見える？ これ見て「そういえば盤面を int で持ってたけど char にしたら速くなるかな」と思ってやってみたけどほぼ変わらなかった。

zaki_ さん: 1573465 点 10 位

EvbCFfp1XB さん: 1557634 点 16 位

$2$ 時間コンでビジュアライザ書いて本体も間に合わせるのえらい

snuke さん: 1512698 点 28 位

ビジュアライズで時間溶かしてたでしょ感ある