【AHC032】緑コーダーの競プロ参加記録 #12
今回はAtCoder Heuristic Contest 032です。
ヒューリスティックは水コーダーですがタイトルそのままです。
結果は508位、perf 1263でした。
AHCに敷居の高さを感じている方に「こんなもんでこれくらいの順位なんだ」と知ってもらえれば幸いです。
ヒューリスティックコンテストに参加しよう！
「AHCはレートが下がらないので参加するだけ得！」
コンテストによってはサンプルコードが与えられることもあります。それをそのまま提出するだけで緑perfが出たりしますし、サンプルから1点でも改善すればperfに200くらい差が出たりもします。
アルゴリズム部門のレートはあまり関係ありません。コンテストによっては開催期間が2週間くらいあったりするので気軽に参加してみましょう。
問題概要
$${N \times N}$$の大きさの盤面がある。
盤面の各マス$${(i, j)}$$には整数$${a_{i,j}}$$が書かれている。$${(\mathrm{mod} 998244353)}$$
$${3 \times 3}$$の大きさのスタンプが$${M}$$個ある。
$${m}$$番目のスタンプの各マス$${(i, j)}$$には整数$${s_{m,i,j}}$$が書かれている。
スタンプを押すごとに、盤面の数字にスタンプの数字を加算する。
$${K}$$回まで操作して、最終的な盤面の数の総和を最大化してね。
$${N = 9, M = 20, K = 81}$$で固定です。
4時間の短期コンテストだったのでサンプルコードはありませんでした。
Step 1. スコアが最も向上する位置を探す
$${(m, i, j)}$$を全探索し、マス$${(i, j)}$$に$${m}$$番目のスタンプを押したときのスコアを計算します。
このときスコアが最大となった$${(m, i, j)}$$を採用します。
これをスコア更新できなくなるまで行います。
スコア：9,476,069,706,445 点 (732位)
提出コード
https://atcoder.jp/contests/ahc032/submissions/52149428
Step 2. たまにスコアを下げてみる
1回ランダムでスタンプを押してから、Step 1の方法で8回スタンプを押してみます。
最大$${K=81}$$回スタンプを押せるので、これを9回繰り返します。
「焼きなまし法」の小指の先っちょみたいな方法。
この方法を時間の限り試行して、最もスコアが高いパターンを採用します。
スコア：10,286,002,020,457 点 (508位)
提出コード
https://atcoder.jp/contests/ahc032/submissions/52156067
これが最終提出になりました。
Step 3. もう少し粘ってみる
コンテスト終了後に4行ほどコードを追加しました。
Step 2では「Step 1 の方法で8回スタンプを押す」としていますが、Step 1ではスコア更新がない時点で処理を打ち切っているため、必ずしも8回スタンプを押しません。
これによって、Step 2では実際には 30 回程度しかスタンプを押していなかったので、なるべく81回に近くなるようにしました。
スコア：10,583,657,847,023 点 (380位)
提出コード
https://atcoder.jp/contests/ahc032/submissions/52157809
あとがき
短期コンは難しい。
今回は貪欲法が強かったらしいです。
ではまた～。
