ARC 088 D Wide Flip
考えるとっかかりがつかめなくてすごぷろさんに教えてもらった問題
忘れないうちにメモ...
- 作者: 柊ゆたか
- 出版社/メーカー: KADOKAWA / アスキー・メディアワークス
- 発売日: 2018/03/24
- メディア: Kindle版
- この商品を含むブログ (2件) を見る
問題概要
0と1からなる文字列sが与えられる
ある自然数Kに対して、sの長さK以上の連続部分列の01を反転できる(0を1に、1を0にできる)。
このとき、文字列sを全て0にできるような最小のKを求めよ
解説
Nを文字列sの長さとする。
まず、sが全て1なら全体を反転することで全て0にできるので、「文字列sを全て同じ文字にする」ことを目的としてよい。
長さKの部分文字列を反転させることができるとき、後ろから長さN-Kの部分文字列を全て同じ文字にできる。
これは例えば前からK-1文字が?、K文字目が0、K+1文字目が1、それ以降が?である文字列"?....?01?...?"について考える。後ろN-K文字を0にする場合、まず前K個を反転する("?'...?'11?...?"になる。ここで?'は?の反転)。そして前からK+1個を反転すると"?...?00?...?"になる。これを繰り返せば、後ろから長さK以上の部分文字列を反転できる場合、後ろからN-K文字を全て同じ文字にできる。同様にして前からN-K文字を同じ文字にすることができる。
これを考えると、前から前からN-K文字、後ろからN-K文字を取り除いた文字列が全て同じ文字ならば文字列sは全て同じ文字にできる。
このような最大のKを求めれば良い。
int main(){ string s; cin >> s; int N = s.size(); int l,r; int ans = (N+1)/2; if(N%2){ int l = N/2; while(l>=0 and s[l] == s[N/2]){ l--; } int r = N/2; while(r<N and s[r] == s[N/2]){ r++; } ans += min(N/2-l,r-N/2)-1; }else{ const int L = N/2-1; const int R = N/2; int l = L; int r = R; if(s[L] == s[R]){ while(l>=0 and s[l] == s[L]){ l--; } while(r<N and s[r] == s[R]){ r++; } ans += min(L-l,r-R); } } cout << ans << endl; }
実装方針が悪い。。。
中心から見るのではなく前と後ろから定数個除いた場合の合計を見たほうがいい....