ABC408 D問題Flip to Gather
初めに
せっかくブログ構築し直したし、ICPCでるしということでしばらくABCで解けなかった問題について書こうかなと。ネタがないなんてことは決してないんですがね。
万が一、筆者をよく知らずにこの記事を読む人がいると悪いの一応注意喚起しますが当方茶コーダーにつき正確性は保証しません。一応ACできるコードであることは保証しますが、それ以上でもそれ以下でもありません。
言いましたよ!言いましたからね!!
問題
この回はCまで解けました。Dからそこそこの壁ありません？私はそう感じましたが果たして
てなわけで問題概要。詳細は↓ https://atcoder.jp/contests/abc408/tasks/abc408_d
- 長さSの0,1で構成された文字列が与えられる
- 任意の回数Siを選び0,1を反転できる
- Sに含まれる1の区間を高々1個にする
制約はT:テストケース, N:文字列サイズ
です。全探索はもちろん無理
問題の意図としては任意の文字列
S=0101011000
が与えられたとき、任意の場所を反転し
S=001111000
となるようにする最小回数を求めればよいわけです。
アプローチ
執筆時点でいくつかの解放が紹介されています。―が、DP以外わかりそうになかったのでDPでやります。気力があれば公式解説の方も理解したいですね。
DPによる解放
主にAngrySadEightさんの解法を参考にしました。 https://atcoder.jp/contests/abc408/editorial/13174
Sを1の区間を高々1個にするとSは最終的に
S = <0:0個以上><1:0個以上><0:0個以上>
という形になります。左から順に状態0,状態1,状態2とします。左側<0:0個以上>と右側<0:0個以上>は別状態としてカウントします。
DPを次のような形でもちます。
dp[i][j] = i文字目まで書き換えた時点で状態jに属すとき、書き換える必要のある文字列の最小値
あたりまえですが、制約と状態の数より
です。
遷移を考えましょう。(isdiff(S,C)はのとき0, のとき1を返す)
//i文字時点で状態0, 状態0は他状態から遷移を持たないので
dp[i][0] = dp[i-1][0] + isdif(S[i],'0')
//i文字時点で状態1,状態0または状態1からの遷移をもつ。より小さい方を採用
dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + isdiff(S[i], '1');
//i文字時点で状態2,状態1または状態2からの遷移をもつ。より小さい方を採用
dp[i][2] = min(dp[i-1][1], dp[i-1][2]) + isdiff(S[i], '0');
↑この問題上が全て
一応丁寧に最後までやるとこのままではdp[0]の状態が定まっていないので
if(S[0] == '1')
{
dp[0][0] = 1;
dp[0][1] = 0;
dp[0][2] = 0;
}
else{
dp[0][0] = 0;
dp[0][1] = 1;
dp[0][2] = 0;
}
こんな塩梅でいいじゃないでしょうか？vector<int>は初期化するときデフォルトで0なので
if(S[0] == '1')
dp[0][0] = 1;
else
dp[0][1] = 1;
これで無問題なはずです。ansはDP最後尾のいずれかの状態なので
ans = min(
dp[N-1][0],
dp[N-1][1],
dp[N-1][2]
)
でよいですね。
おわりに
ABC408 D問題をDPで解く鍵は
S = <0:0個以上><1:0個以上><0:0個以上>
と
//i文字時点で状態0, 状態0は他状態から遷移を持たないので
dp[i][0] = dp[i-1][0] + isdif(S[i],'0')
//i文字時点で状態1,状態0または状態1からの遷移をもつ。より小さい方を採用
dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + isdiff(S[i], '1');
//i文字時点で状態2,状態1または状態2からの遷移をもつ。より小さい方を採用
dp[i][2] = min(dp[i-1][1], dp[i-1][2]) + isdiff(S[i], '0');
でした。これだけ見ると簡単そうなんですがね。というか実際難しくはないのですが、本番では解けないものです。
コード例
#include <bits/stdc++.h>
#include <cmath>
#include "atcoder/all"
#define ll long long
#define rep(i, n) for(ll i=0;i<n;i++)
using namespace std;
using namespace atcoder;
int isDiff(char c, char x)
{
return c != x ? 1 : 0;
}
int main()
{
ll T;
cin >> T;
rep(t, T)
{
ll N;
string S;
cin >> N;
cin >> S;
vector<vector<ll>> dp(N, vector<ll>(3, 0));
if(S[0] == '1')
{
dp[0][0] = 1;
dp[0][1] = 0;
dp[0][2] = 0;
}
else{
dp[0][0] = 0;
dp[0][1] = 1;
dp[0][2] = 0;
}
for(ll i=1;i<N;i++)
{
dp[i][0] = dp[i-1][0] + isDiff(S[i], '0');
dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + isDiff(S[i], '1');
dp[i][2] = min(dp[i-1][1], dp[i-1][2]) + isDiff(S[i], '0');
}
cout << min(dp[N-1][0], min(dp[N-1][1], dp[N-1][2])) << endl;
}
}
以上