ARC088 D - Wide Flip (500)

• 問題

問題概要

ビット列Sが与えられる。K以上の範囲を選んでその区間のSを反転させることができる時、最大のKを求めよ。
1<= |S| <= 10⁵

解法

k文字目のみを変えようとした時、[0,k-1]->[0,k]を反転させることで変えることができる。
同様に[k+1,N]->[k,N]でも変えることができる。
これを使うとS[k]!=S[k+1]の時、前半を使えばk、後半を使えばN-kでS[k]=S[k+1]にできる。
この時、max(k,N-k)が大きい順から(つまり中心に近い方から)どちらかの1文字だけ変化させていくと、Sの全てを揃えることができる。
必要十分なKはS[k]!=S[k+1]なるkのmax(k,N-k)の最小値(K'とする)であることがわかる。
なぜなら、K > K'であればmax(k,N-k)が最小となるS[k],S[k+1]を揃えることができないし、
K<=K'であれば前述のようにSを全て揃えることができるからである。
よって答えはmin_(S[k]!=S[k+1])(max(k,N-k))で求められる。

メモ

解説放送のKによって真ん中が自由に変えられなくなる〜みたいな解釈の方がわかりやすい気がした。

コード

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>
#include<stack>
#include<tuple>
#include<numeric>
#include<cassert>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<int,ll>;
using Pd = pair<double,double>;
using T = tuple<double,double,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N = 100005;
const ll lmod = 1e9+7;

string S; int N;

int main(){
  cin >> S ; N = S.length();
  int ans = INF;
  rep(i,N-1){
    if(S[i]!=S[i+1]) ans = min(ans,max(i+1,N-i-1));
  }
  if(ans==INF) ans = N;
  cout << ans << endl;
  return 0;
}