【AHC032】緑コーダーの競プロ参加記録 #12

今回はAtCoder Heuristic Contest 032です。
ヒューリスティックは水コーダーですがタイトルそのままです。

結果は508位、perf 1263でした。
AHCに敷居の高さを感じている方に「こんなもんでこれくらいの順位なんだ」と知ってもらえれば幸いです。

ヒューリスティックコンテストに参加しよう！

「AHCはレートが下がらないので参加するだけ得！」

コンテストによってはサンプルコードが与えられることもあります。それをそのまま提出するだけで緑perfが出たりしますし、サンプルから1点でも改善すればperfに200くらい差が出たりもします。

アルゴリズム部門のレートはあまり関係ありません。コンテストによっては開催期間が2週間くらいあったりするので気軽に参加してみましょう。

問題概要

A - Mod Stamp

---

• $${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)}$$を採用します。

これをスコア更新できなくなるまで行います。

seed 0

スコア：9,476,069,706,445 点 (732位)

提出コード
https://atcoder.jp/contests/ahc032/submissions/52149428

Step 2. たまにスコアを下げてみる

1回ランダムでスタンプを押してから、Step 1の方法で8回スタンプを押してみます。
最大$${K=81}$$回スタンプを押せるので、これを9回繰り返します。

「焼きなまし法」の小指の先っちょみたいな方法。

この方法を時間の限り試行して、最もスコアが高いパターンを採用します。

seed 0

スコア：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回に近くなるようにしました。

seed 0

スコア：10,583,657,847,023 点 (380位)

提出コード
https://atcoder.jp/contests/ahc032/submissions/52157809

あとがき

短期コンは難しい。
今回は貪欲法が強かったらしいです。

ではまた～。