A - とあるマダムの宝石整理
問題文
$H$ 行 $W$ 列からなるマス目がある。下から $i$ 行目、左から $j$ 行目のマスをマス $(i, j)$ と表記する（以後、 $i$ 行目という表現は下から数える）。マス目には初期状態では何も置かれていない。このマス目に $1$ から $4$ の数字が刻まれた宝石を置いていく。
$N$ ステップの操作を行う。各ステップでは設置フェーズと整理フェーズを順に行う。 $t$ ステップ目で得られる得点を $V_t$ とする。 $V_t$ の値ははじめ $0$ である。
設置フェーズ
まず、数字 $A_t$ が刻まれた宝石を受け取る。その後、以下の $2$ つの行動のうちどちらかを行う。
- 受け取った宝石を空いているマスから $1$ つ選んで置く。ただし、空いているマスが存在しない場合はこの行動を選択することはできない。
- 受け取った宝石をマス目に置かずに捨て、 $V_t$ に $100$ を加える。
整理フェーズ
まず、整理を行うかを選択する。整理を行わない場合はそのまま整理フェーズを終了する。整理を行う場合は、次の手順に従って操作を行う。
- 手順1: カウンター $c$ を $0$ で初期化する。
- 手順2: $c$ の値を $c + 1$ にする。
- 手順3: 各列について、 $1$ 行目から順に宝石が置かれているかを確認し、もし宝石が置かれていたら、 $1$ 行目または $1$ 行下に宝石が置かれている行に到達するまで列を変えないように宝石を下に動かす。
- 手順4: マス目の宝石を連結成分分解する。ここで、2つの宝石は、同じ数字が刻まれており、かつ、上下左右に同じ数字が刻まれた宝石のみを通って互いに到達可能な場合に、またその場合に限り連結とする。連結成分の大きさが $3$ 以上の宝石を全て取り除き捨てる。
- 手順5: 手順4で取り除いた宝石の数を $T$ と置く。また、取り除いた宝石に刻まれた数字の種類数を $K$ と置く。値 $f$ を次のように定義し、 $V_t$ に加える。
$$ f = T^{2} \left( \mathrm{round} \left( 512 \times \left(1 - 0.99^{2^c} \right) \right) + K^{2} \right)$$
- 手順6: $f = 0$ のとき、整理フェーズを終了する。そうでないとき手順2に戻る。
$N$ ステップに渡る操作が終了したとき、得られる得点の総和をなるべく大きくするような方法を考えてほしい。
得点
各ステップで得られた得点 $V_t$ の総和、つまり以下の値がこの問題のスコアである。
$$\sum_{t=1}^N V_t$$
テストケースは $500$ 個あり、各テストケースの得点の合計が提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定が WA や TLE となる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。
なお、本ページの UI 上で表示されている「100点」という表記は、便宜上のものであり、本問題の得点とは無関係である。
ツール
ビジュアライザは以下の URL から ダウンロードできる。
Zip ファイルを展開後、 readme.md を参考に環境構築をし、実行せよ。
コンテスト終了まで、ビジュアライザやその出力結果に関する言及は禁止されているが、 MCC 競技プログラミング部公式 X にて入出力例のビジュアライズ結果がポストされる場合がある。このポストをリポストすることは特別に許可される。
制約
全てのテストケースについて、次の制約を満たす。
- $N = 200$
- $3 \leq W \leq H \leq 8$
- $A_i \in \lbrace 1, 2, 3, 4 \rbrace \ \ (1 \leq i \leq N)$
入力生成方法
$L$ 以上 $U$ 以下の整数値を一様ランダムに生成する関数を $\mathrm{rand}(L,U)$ とする。
$H, W$ は $3 \leq W \leq H \leq 8$ を満たすまで、$H = \mathrm{rand}(3, 8), W = \mathrm{rand}(3, 8)$ で繰り返し更新し続けることで生成する。
$A_i$ は $\mathrm{rand}(1, 4)$ により生成する。
入力
入力は以下の形式で与えられる。
$N\ \ H\ \ W$
$A_1\ \ A_2\ \ \cdots\ \ A_N$
出力
$t$ ステップ目の操作を $3$ つの整数 $r_t, c_t, z_t$ で表す。
- 設置フェーズでマス $(r_t, c_t)$ に宝石を置く。宝石を捨てる場合は $r_t=c_t=-1$ とせよ。
- 整理フェーズで整理を行う場合は $z_t=1$ とせよ。整理を行わない場合は $z_t=0$ とせよ。
このとき、標準出力に $N$ 行出力せよ。$t$ 行目には $r_t, c_t, z_t$ を空白区切りで出力せよ。
$r_1\ \ c_1\ \ z_1$
$r_2\ \ c_2\ \ z_2$
$\vdots$
$r_N\ \ c_N\ \ z_N$
200 6 6
1 4 4 1 3 1 1 3 2 1 4 2 3 1 2 2 3 4 2 3 1 2 1 1 4 3 2 4 4 4 1 2 3 3 1 2 4 3 1 3 2 4 3 3 1 4 4 2 3 3 1 4 2 4 2 4 1 4 3 2 2 3 3 4 3 2 3 3 1 1 1 3 2 2 3 1 4 1 2 4 3 1 3 2 4 4 2 1 1 3 3 4 2 3 1 1 1 4 2 2 1 2 2 1 1 2 2 3 2 2 3 3 4 4 1 2 4 2 2 1 2 1 2 2 3 2 2 3 3 4 1 3 1 3 3 3 1 2 2 2 3 4 3 1 4 1 3 4 3 1 3 3 2 2 3 1 1 4 4 2 2 4 1 4 3 3 4 4 4 4 2 3 4 4 4 3 4 4 1 1 2 1 3 1 4 2 4 2 2 2 4 3 2 2 2 3 3 1 3 4
1 2 0
4 3 0
6 6 0
3 2 0
6 3 0
3 4 0
2 6 0
1 5 0
3 1 0
4 1 0
4 2 0
3 6 0
4 6 0
5 5 0
1 3 0
5 2 0
5 6 0
6 1 0
1 4 0
6 4 0
1 6 0
5 4 0
6 5 0
4 5 0
3 3 0
2 5 0
1 1 0
6 2 0
5 1 0
3 5 0
4 4 0
2 1 0
5 3 0
2 3 0
2 2 0
2 4 1
5 1 0
2 2 0
6 1 0
6 3 0
4 3 0
6 5 0
5 4 0
4 5 0
4 1 0
4 2 0
5 2 0
3 3 0
3 4 0
2 1 0
2 4 0
6 4 0
6 2 0
3 2 0
3 1 0
4 4 0
5 3 0
5 5 0
2 3 1
5 2 0
4 6 0
5 4 0
1 2 0
5 5 0
4 4 0
5 3 0
6 1 0
4 2 0
3 5 0
4 1 0
2 2 0
5 1 0
3 3 0
1 1 0
6 3 0
2 3 0
6 5 0
3 1 0
4 5 0
3 2 0
2 5 0
4 3 0
2 1 0
6 4 0
5 6 0
6 6 0
6 2 1
6 4 0
4 4 0
6 6 0
5 3 0
3 4 0
5 5 0
6 2 0
5 2 0
3 6 0
4 2 0
4 5 0
5 4 0
4 6 0
6 5 0
6 3 0
4 3 0
5 6 1
5 1 0
4 6 0
6 2 0
4 1 0
4 2 0
6 1 0
3 1 0
5 6 0
5 2 0
6 6 0
6 5 1
6 4 0
6 3 0
4 1 0
6 1 0
6 2 0
6 5 0
5 3 0
5 5 0
5 2 0
3 1 0
5 1 1
6 5 0
4 1 0
5 5 0
5 4 0
5 1 0
6 1 0
6 6 0
6 4 0
4 5 0
6 2 1
6 2 0
4 1 0
6 5 0
4 6 0
6 1 0
5 6 0
6 6 0
4 5 0
5 5 0
6 3 0
6 4 0
5 2 0
3 1 0
5 1 1
5 2 0
6 2 0
6 3 1
6 1 0
6 2 0
5 2 1
6 2 0
5 2 0
6 3 0
6 1 1
6 1 0
5 1 0
4 1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1
-1 -1 1