【AHC030】緑コーダーの競プロ参加記録 #4

今回はAtCoder Heuristic Contest 030です。
ヒューリスティックでも緑コーダーなのでタイトルそのままです。

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

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

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

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

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

問題概要

A - Polyomino Mining

---

• $${N \times N}$$のグリッド内に$${M}$$個の油田が隠されている。

• 各油田の位置は不明だが、形状は与えられる。

• 操作 1: マス$${(i, j)}$$ を採掘し、そのマスの石油埋蔵量が判明する。

• 操作 2: 好きなマスを好きなだけ占う。

• 操作 3: すべての油田の位置を解答する。

• $${2N^2}$$ターン以内にすべての油田の位置を特定してね。

---

操作 1、操作 3をするとコストが +1 され、総コストが小さいほど良い順位が得られます。操作 2の占いを駆使して効率化していくのが大事そうです。

さて占いの内容は・・・

図1. 占いの内容

？？？？？？？？？

まるで分からないので占いを利用しない方向でいきます。

なお本記事では「なにも手をつけていないマス（図の白マス）」を「空きマス」、「石油埋蔵量が 0 で確定したマス（図の黒マス）」を「壁」と呼びます。

Step 0. サンプルコードを見る

この問題にはサンプルコードが用意されており、その戦略は「すべてのマスを採掘し、その後に石油が出たマスを解答する」というものです。コストは必ず$${N^2}$$になりますね。

絶対スコア（暫定テスト）：12,696,000,000点。
コスト（Seed 4）：256.000000

図2. サンプルコードの動き(seed 4: N=16) 
黒マス: 石油埋蔵量 = 0（採掘済み）
黄マス: 石油埋蔵量 > 0（採掘済み）

このgifアニメーションは公式が用意しているWeb版ビジュアライザの機能を使って生成しています。

Step 1. サンプルコードを少し改善

初日に問題文を読み、どう取り組めばいいのか分からなかったのでこの時点で1週間経っています。
とりあえずサンプルコードをちょっとでも超えるため直感的で手間のかからない改善を目指しました。

制約で各油田の大きさが4マス以上であることが保証されています。
つまり「壁」に囲まれた領域内のマスの個数が3マス以下ならその領域は全て「壁」であることが確定しますが、より簡単に、ある空きマス$${(i, j)}$$について上下左右の4マス全てが「壁」ならばマス$${(i, j)}$$も「壁」であることを利用します。

1マス飛ばしで採掘するコードは簡単に書くことができ、サンプルコードよりコストが増えることはないので一旦これを採用します。その後は残ったマスをすべて採掘します。

for i in range(N):
    for j in range(N):
        if i % 2 != j % 2:
            drill(i, j)

今回は低いスコアの方が優秀です。

絶対スコア（暫定テスト）：9,399,000,000点
コスト（Seed 4）：210.000000

図3. Step 1 のコードの動き(seed 4: N = 16)
黒マス: 石油埋蔵量 = 0（採掘済み）
黄マス: 石油埋蔵量 > 0（採掘済み）
灰マス: 石油埋蔵量 = 0 （配置不可能）

Step 2. 油田を配置可能なマスを全探索

「壁」が増えていくにつれて各油田の配置できるマスが限られていきます。ある油田が配置可能なマスを全探索し、配置方法が1パターンしかなければその油田はその位置で確定です。

油田の形状は「座標の集合」として与えられるので、油田の一部のマス$${(si, sj)}$$がマス$${(i, j)}$$と重なるよう油田を平行移動させたときに全ての油田マスを「壁」以外のマスに配置できるかを判定します。

dx = i - self.si
dy = j - self.sj
for x, y in self.X:
    yield x + dx, y + dy

絶対スコア（暫定テスト）：8,665,000,000点
コスト（Seed 4）：179.000000

図3. Step 2 のコードの動き(seed 4: N = 16)
黒マス: 石油埋蔵量 = 0（採掘済み）
黄マス: 石油埋蔵量 > 0（採掘済み）
灰マス: 石油埋蔵量 = 0 （配置不可能）
紫マス: 石油埋蔵量 = 0 （初手配置不可能）
緑マス: 石油埋蔵量 = 不明（配置確定）

Step 3. 油田を配置不可能なマスを全探索

ある油田の配置可能なマスを全探索するなら、どの油田も配置不可能であるマスも全探索するとよさそうです。

Step 1では周囲が「壁」に囲まれている1マスしか調べられませんでしたが、全探索するので空きマスの大きさが関係なくなりました。それに伴い採掘ローラーするマスも少しだけスキマを開けて削減します。

絶対スコア（暫定テスト）：7,341,000,000点
コスト（Seed 4）：157.000000

図4. Step 3 のコードの動き(seed 4: N = 16)
黒マス: 石油埋蔵量 = 0（採掘済み）
黄マス: 石油埋蔵量 > 0（採掘済み）
灰マス: 石油埋蔵量 = 0 （配置不可能）
紫マス: 石油埋蔵量 = 0 （初手配置不可能）
緑マス: 石油埋蔵量 = 不明（配置確定）

Step 4. これまでの方針をブラッシュアップ

方向性は同じままパフォーマンスを高めました。

• 配置可能・不可能マスを毎ターン全探索

• 「配置が確定した油田マスのうち石油埋蔵量が 1 で確定しているマス」は他の油田から見た配置不可能マス

• 配置パターンが2つ以上4つ以下の場合、その中から未採掘マスを1つ選んで採掘する（次に配置確定しやすくする）

• 終盤に一度だけ運ゲーをする

絶対スコア（暫定テスト）：6,263,000,000点
コスト（Seed 4）：124.000000

サンプルコードの絶対スコア12,696,000,000点、コスト256.000000に比べると半分近く効率良くなりました。

図5. Step 4 のコードの動き(seed 4: N = 16)
黒マス: 石油埋蔵量 = 0（採掘済み）
黄マス: 石油埋蔵量 > 0（採掘済み）
灰マス: 石油埋蔵量 = 0 （配置不可能）
紫マス: 石油埋蔵量 = 0 （初手配置不可能）
緑マス: 石油埋蔵量 = 不明（配置確定）

ローカルテストのスコアはかなり良くなったのですが、コンテスト終了直前に700ケースを試してWAが1つ出てしまいました。残り2分で気付いてバグの修正をする時間もなかったので「$${\large \frac{1}{700}}$$ならまぁ・・・」と思ってこれを最終提出しました。
暫定テストはACで466位、システムテストはWAで412位でした。

提出コード
https://atcoder.jp/contests/ahc030/submissions/50451060

あとがき

目標だった500位を超えて嬉しい反面、システムテストでWAを7つ出してしまったのはちょっと悔しいです。

順位表を見るにサンプルコードを提出すると728位でperf 814、サンプルを1点でも越した727位はperf 988でした。

図6. 順位とperf
上: igasu_7、中: 727位
下: 728位 (サンプルコード)

特にすごいことをしなくても緑コーダー目線でまぁまぁ良い順位が取れるので「ちょっとサンプルコード超えとくか」くらいの気持ちで、気が向いたらぜひ参加してみてください。

ではまた～。

Contest Result - AtCoder