【AtCoder】ABC 408 D - Flip to Gather | 緑コーダーが解くAtCoder

atcoder.jp

配点: 400 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 950 / NoviSteps: 1Q

問題概要

長さ の0と1のみからなる文字列 が与えられる。これから、以下の操作を 回以上行うことで、 に含まれる連続した1の区間が高々 個となるようにするとき、必要な操作回数の最小値を求めよ。

• 操作 : を満たす整数 を選び、 が0のときは1に、1のときは0に変更する。

個のテストケースが与えられるので、それぞれについて答えを求めよ。

制約

• 
• 
• 各入力ファイルについて、すべてのテストケースの の総和は 以下である
• は整数

考察

この問題は2通りの方針があるので、それぞれ紹介する。なお、添字は 0-indexed としている。

1の個数の累積和を用いる

に含まれる連続した1の区間が高々 個となるためには、 が以下の2通りのいずれかの状態になればよい。

1. 内の1を全て0にする。
2. ある区間 内の を全て1に、それ以外の文字を全て0にする。

与えられた をそれぞれの状態にするために必要な最小操作回数(特に後者)を求めるために、以下のように定義される累積和テーブルを用意する。

• 半開区間 内の に含まれる1の個数

これを用いると、上述の状態にするための最小操作回数は次のように計算される。

1. 
2. 
   • 区間 を0にする :
   • 区間 を1にする :
   • 区間 を0にする :
   • これらの和を取り、整理する。

したがって、あとは (1番目の状態)を初期値として、 を動かしながら最小値を求めていけばよいことになる。

しかし、愚直に を動かしていたのでは計算量が となって TLE してしまう。

ここで、 を固定したとして、2番目の状態における について注目してみる。この部分を とすれば、累積minの要領でその時点の における を保持することができる。

具体的には、 として、

• 
• 

とすればよい。

こうすることで、 まで増やしていくだけで操作回数の最小値を求めることができる。計算量は だ。

状態DP(耳DP)を用いる

考察1では、最終的な の状態(目標)を2通りに分けたが、よく考えるとこれは1通りで表せる。

• 「 個以上の0」と「 個以上の1」と「 個以上の0」をこの順に連結したもの。

この形には、前から順に3つの段階が存在する。

の各文字について、「その文字をどの段階に入れるか」を考えることで、以下のような DP テーブルを考えることができる。D問題の「D」はDPの「D」！

• までを見て目標を達成する際、 を段階 に入れるとするときの flip すべき文字数の最小値

初期値は 、それ以外の場所が で、遷移は以下のようになる 。ただし、

であるとする。

• 
• 
• 
• 
• 

具体的な遷移は下図のようになる。

サンプルケース1のテストケース1

最終的な答えは である。

計算量は となる。

実装例

考察1

累積和テーブルはpsとしている。

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

template <typename T>
inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }

// ======================================== //

int solve()
{
    int N;
    string S;
    cin >> N >> S;

    vector<int> ps(N + 1, 0);
    rep(i, 0, N) ps[i + 1] = ps[i] + (S[i] - '0');

    int res = ps[N];
    int l_part = 2 * ps[0] - 0;
    rep(r, 0, N)
    {
        chmin(l_part, 2 * ps[r] - r);

        int r_part = -2 * ps[r + 1] + ps[N] + r + 1;
        chmin(res, l_part + r_part);
    }

    return res;
}

int main()
{
    int T;
    cin >> T;

    while (T--)
    {
        cout << solve() << endl;
    }

    return 0;
}

atcoder.jp

考察2

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

constexpr int INF = 1e+9;

template <typename T>
inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }

// ======================================== //

int solve()
{
    int N;
    string S;
    cin >> N >> S;

    vector<vector<int>> dp(N + 1, vector<int>(3, INF));
    dp[0][0] = 0;

    rep(i, 0, N)
    {
        if (S[i] == '0')
        {
            chmin(dp[i + 1][0], dp[i][0] + 0);
            chmin(dp[i + 1][1], dp[i][0] + 1);
            chmin(dp[i + 1][1], dp[i][1] + 1);
            chmin(dp[i + 1][2], dp[i][1] + 0);
            chmin(dp[i + 1][2], dp[i][2] + 0);
        }
        else
        {
            chmin(dp[i + 1][0], dp[i][0] + 1);
            chmin(dp[i + 1][1], dp[i][0] + 0);
            chmin(dp[i + 1][1], dp[i][1] + 0);
            chmin(dp[i + 1][2], dp[i][1] + 1);
            chmin(dp[i + 1][2], dp[i][2] + 1);
        }
    }

    return min({dp[N][0], dp[N][1], dp[N][2]});
}

int main()
{
    int T;
    cin >> T;

    while (T--)
    {
        cout << solve() << endl;
    }

    return 0;
}

atcoder.jp

実装時間: 50分

コメント

考察2のように、「操作の何段階目かという情報を状態に持つDP」のことを状態DP / 耳DPというらしい。

www.mathenachia.blog

DP解法の方が考えることは少なそう。