A - JJOOII (JJOOII) ～文字列のランレングス（文字情報あり）～

Quiz

https://atcoder.jp/contests/joi2012ho/tasks/joi2012ho1

AC code

https://atcoder.jp/contests/joi2012ho/submissions/10256473

解法

• Oの連続数に注目する
• 例えばOOOがあったとき（連続したOが3個でその隣は違う文字）、レベル3しか作りえない
  • レベル4はもちろんだが、レベル2も作れない
• 文字ごとにランレングス圧縮し、Oに注目して左がJ, 右がIであり、かつJとIの長さがO以上あれば作れる

例題

OJJOOIIOJOI

ランレングス圧縮すると
O1 J2 O2 I2 O1 J1 O1 I1

Oに注目すると
J2 O2 I2の箇所でLV2が作れる
J1 O1 I1の箇所でLV1が作れる

それらのmaxを取って答えは2

code 抜粋

using P = pair<char, ll>;
// どの文字が長さいくつ
// のvectorで返す
vector<P> run_length(string& s){
  vector<P> ret;
  ll N = s.size();
  if(N==0) return ret;
  char cur=s[0];
  ll cnt=1;
  FOR(i, 1, N){
    if(s[i]==cur){
      cnt++;
    }else{
      ret.push_back(MP(cur, cnt));
      cur = s[i];
      cnt = 1;
    }
  }
  ret.push_back(MP(cur, cnt));  
  return ret;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    string s;cin>>s;

    stringstream ss;
    ss << 'z';
    ss << s;
    ss << 'z';

    string t = ss.str();
    vector<P> V = run_length(t);

    ll ma = 0;
    ll N = V.size();
    FOR(i, 1, N-1){
      if(V[i].first=='O'){
        ll len = V[i].second;
        // 左右見る
        if(V[i-1].first=='J' && V[i-1].second >= len && V[i+1].first=='I' && V[i+1].second >= len){
          chmax(ma, len);
        }
      }
    }
    p(ma);
    return 0;
}

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～