【ABC408】D問題 - Flip to Gather 考察から実装(c++)まで

AtCoderBeginnerContest408の解説＆感想です。
コンテストリンク

問題一覧

• 【ABC408】A問題 - Timeout　考察から実装(c++)まで
• 【ABC408】B問題 - Compression　考察から実装(c++)まで
• 【ABC408】C問題 - Not All Covered　考察から実装(c++)まで
• 【ABC408】D問題 - Flip to Gather　考察から実装(c++)まで <- イマココ
• 【ABC408】E問題 - Minimum OR Path　考察から実装(c++)まで
• 【ABC408】F問題 - Athletic　考察から実装(c++)まで

D問題 - Flip to Gather

問題リンク

問題概要

長さ$N$の0と1からなる文字列$S$が与えられる。

• 任意の場所の0,1を反転させる

という操作を好きなだけ行い、1が連続する区間を高々1つにしたい時、最小の操作回数を求めよ。
$T$個のテストケースにそれぞれ答えよ。

制約

• $ 1 \le T \le 2 \times 10^4 $
• $ 1 \le N \le 2 \times 10^5 $
• $ 各テストケースのNの総和は2 \times 10^5以下 $

考察

貪欲にやろうと思って、うんうん唸ってたけど全然思いつかず時間を溶かす。
大きい方向転換が必要だと思い、解法ローラーで「DPで行くぞ！」と決めたら割とすぐに思いついた。

$i$番目を0にするか1にするか考えるんだけど、素直に

• $dp[i][j] := i番目まで見て、i番目をjにした時の最小操作回数$

とするとだいたい良さそう。
「だいたい」と言うのは、$i-1$番目が0だったとして、$i$番目を1にするかどうかは、「今までに1の島があったかどうか？」によるから。

$i-1$番目が0だったとしても、今までにすでに1の島があったなら$i$番目を1にはできないし、1の島がまだないなら$i$番目を1にしたっていい。

まとめると、

• $dp[i][j][k] := i番目まで見て、i番目をjにして、$
  • $今までが全て0の時の最小操作回数 \ (k==0) $
  • $すでに1の島があるの時の最小操作回数 \ (k==1)$

とすればいい。

遷移は

• 今見てる場所を1にして、1の島がすでにある状態にするには、今回を最初の1にするか、前回まで続いていた島を引き継ぐかのどちらか。

$ dp[i][1][1] = min(dp[i-1][0][0], dp[i-1][1][1])+(S[i] \ != \ 1) $

• 今見ている場所を0にしてすでに1の島があった状態にするには、一つ前まで続いていた島をちょん切るか、2つ以上前に作った島の時の最小を引き継ぐか。

$ dp[i][0][1] = min(dp[i-1][1][1], dp[i-1][0][1])+(S[i] \ != \ 0) $

• 今見ている場所を0にして、全部0にするには、今までも全部0だったところから来るしかない

$ dp[i][0][0] = dp[i-1][0][0] + (S[i] \ != \ 0) $

実装

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<long long>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;

const ll inf = 1000000000000000000LL;

int solve(){
    //入力
    ll N;
    string S;
    cin>>N>>S;
    
    //はじめは全てクソデカコストで初期化
    vvvll dp(N, vvll(2, vll(2, inf)));
    
    //dp[0]は丁寧に初期化(番兵とか上手く使えばもっと綺麗にできそう)
    if(S[0] == '0'){
        dp[0][0][0] = 0;
        dp[0][1][1] = 1;
    }
    else {
        dp[0][0][0] = 1;
        dp[0][1][1] = 0;
    }
    
    for(int i=1;i<N;i++){
        dp[i][1][1] = min(dp[i-1][0][0], dp[i-1][1][1]) + (S[i] != '1');
        dp[i][0][1] = min(dp[i-1][1][1], dp[i-1][0][1]) + (S[i] != '0');
        dp[i][0][0] = dp[i-1][0][0] + (S[i] != '0');
    }
    
    //N-1番目の状態としてあり得る全パターンの中で最小が答え
    cout<<min({dp[N-1][1][1], dp[N-1][0][1], dp[N-1][0][0]})<<endl;
    return 0;
}

int main(void){
    ll T;
    cin>>T;
    while(T--) solve();
    return 0;
}