AtCoder Chokudai Contest 001 高橋君の山崩しゲーム

参加はしていましたが，改めて解いてみた．

問題概要

30x30のグリッドがあり，各マスに自然数が書き込まれている．次の一連の流れを1手とする．手数を最小化せよ．

1. 1つのマスを選ぶ
2. デクリメントする．
3. ４近傍のうち，デクリメント後のマスの数と一致したマスがあれば，そのマスを改めて選び，ステップ2に戻ることができる．

補足

リンク付けはされていないが，公式解説がある．

https://www.slideshare.net/chokudai/chokudai001

自分の解法

走査 544794

https://beta.atcoder.jp/contests/chokudai001/submissions/2743518

左から右へ走査する，1以上なら出力する．

貪欲 707829

https://beta.atcoder.jp/contests/chokudai001/submissions/2743718

1手で減らせるマスの数を最大化する貪欲法．順位表と比較するとスコアあんまり良くないね．

一応解説．グリッドをDAGと見なす．各マスが頂点．隣接するマスの値の差がちょうど1ならば，高い方から低い方へ有向辺を引く．後はこのDAGに対して最長のパスを見つければ良い．動的計画法が有効．

貪欲リベンジ 808284

https://beta.atcoder.jp/contests/chokudai001/submissions/2745921

上の手法では，今打つ手で減らすマスの数を最大化していた．もう少しだけ改良する．

DAGと見なす部分について，隣接するマスの値の差が1以上であっても，高い方から低い方へ有向辺を引くことにする． しかし，DAGに対して最長のパスを見つけたとしても，1ずつ減少する列になっていないので，1ずつ減少する列になるよう部分的に削ってから，パスを辿る手を打つ．

解説見たやつ 836766

https://beta.atcoder.jp/contests/chokudai001/submissions/2750353

解説見た．解説スライド17ページ辺りの．

とても単純なコードでpriority_queueなりstackなり動的計画法なり使った貪欲法を追い抜いてしまった．

このくらい単純．実行中，グリッドはだんだんy方向に沿った斜面状になる．

    void solve() {
        F<int> field = fieldInit; // グリッドの情報

        diterate(i, 100 + N, 0) { // (100+N) downto (1)
            iterate(x, 1, N + 1) { // (1) upto (N)
                iterate(y, 1, N + 1) { // (1) upto (N)
                    if (i - y <= 0) continue;
                    while (i - y <= field(y, x)) echo(y,x), --field(y, x);
                }
            }
        }

    }

局所的に良いものを取ろうとすると，全体のスコアがダメダメになってしまう．

「こういう状態のグリッドが嬉しいよね」形に持っていく事が大切らしい．