グダグダで落とすはずだったAが通ってしまい、謎の良順位で赤復帰。これでいいのか…。
http://codeforces.com/contest/603/problem/A
問題
01で構成されたN文字の文字列Sがある。
このSに対し、1か所だけ連続する部分文字列を01反転できるとする。
(不連続でいいので)Sの部分文字列のうち01が交互に続く最長部分文字列長を求めよ。
解法
まずとっつきやすい方法としては簡単なDPがある。
文字列の先頭から、[反転をまだ行ってない・反転中・反転後もとに戻った]の3つの状態と、条件を満たす部分文字列の末尾の文字[0,1]で3*2の状態に対し、それぞれ最長の部分文字列長を更新していくと良い。
自分は本番そう通した。
もっと簡単な解法として、以下のように読み替えることができる。
ある地点より後ろを全部01反転する、という処理を2回まで行える。
まず反転を無視して、貪欲に01交互に何文字取れるか数えよう。
これは単純に直前の文字と違う文字の数を数えるだけである。
ここから、最大2回まで、同じ文字が連続する箇所を反転により異なる文字にすることで題意を満たす文字列長をmin(2,同じ文字の連続数)だけ増やせることがわかる。
こう考えると反転回数が2回以上何回でもO(N)で解けるね。
int N; string S; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>S; int ret=1,same=0; for(i=1;i<N;i++) { if(S[i]!=S[i-1]) ret++; else same++; } cout<<ret+min(2,same)<<endl; }
まとめ
本番配列長間違えたのに、運よくSEGVも値の不本意な上書きも防いで通ってしまった。
