分身 [第四回 アルゴリズム実技検定 D]

https://atcoder.jp/contests/past202010-open/tasks/past202010_d

前提知識

• （あったらいいレベルだが）imos法

解説

https://atcoder.jp/contests/past202010-open/submissions/21467860

慣れていないと問題を見たときに面食らうと思うが、1つずつ問題を解決していこう。

操作についての考察

色々な操作を考えると、AABとやってもABAとやってもBAAとやっても最終的な結果は同じとなる。
つまり、操作は順序を考える必要はなく、タイプAを何回、タイプBを何回やったかということだけを考えればいいことになる。
少し操作の状態をまとめることができた。
これで全状態について考えてみよう。

タイプAを49回、タイプBを49回やれば必ずすべてのマスに忍者を配置できるため、タイプA,Bの最大回数は49回ということになる。
そのため、全状態はタイプA,Bの回数をどうするかということになるので、49²通りとなる。
これは余裕で全探索が可能である。

x,yを固定したとき

状態は全探索できるので、問題はその状態ですべてのマスに忍者がいる状態となるかを判定することである。
ある忍者がiにいるとき、タイプAをx回、タイプBをy回すると、[i-x,i+y]の範囲にその忍者が分身する。
全ての忍者についてこの範囲に分身したと考えたときに、全部の領域に忍者がいる状態であるかを判定すればいい。
全ての領域を配列で考えることにすると、これは各忍者について[i-x,i+y]の範囲を塗りつぶして、全部が塗られているかを確認することになる。
この範囲の塗りつぶしをimos法を使って実現しよう。
（今回は制約が小さいので普通にループを使って塗りつぶしても問題ない）

注意点としては、塗りつぶしの範囲が配列外にならないようにmax,minをうまく使って塗りつぶす範囲を決めることと、
x+yが最小になるようなx,yを求めるので、最小値とともにその最小値を作るようなx,yも同時に保持しておく必要がある。
これはよくある要求なので実装練習をしておこう。

int N;
string S;
//---------------------------------------------------------------------------------------------------
int imos[101];
void _main() {
    cin >> N >> S;

    int mi = inf, ans1, ans2;
    rep(x, 0, N) rep(y, 0, N) {
        rep(i, 0, N) imos[i] = 0;
        rep(i, 0, N) if(S[i] == '#') {
            int L = max(0, i - x);
            int R = min(N - 1, i + y);
            imos[L]++;
            imos[R + 1]--;
        }
        rep(i, 1, N) imos[i] += imos[i - 1];
        bool ok = true;
        rep(i, 0, N) if (imos[i] == 0) ok = false;
        if (ok && x + y < mi) {
            mi = x + y;
            ans1 = x;
            ans2 = y;
        }
    }

    printf("%d %d\n", ans1, ans2);
}