chacoderのブログ

競技プログラミングそのほか

第11回日本情報オリンピック 本選(オンライン) JJOOII

提出コード

問題文のとおり実装するだけなのですがだいぶ手間取りました。
なんとかAC.

#include <bits/stdc++.h>
using namespace std;

int main(){
  string S;
  cin>>S;
  int len=S.length();
  int flag=0;
  int cnt=0;
  int level=0;
  int maxlevel=0;
  
  for(int i=0;i<len;i++){
    if(flag==0 && S.at(i)=='J'){
      flag=1;
      cnt=1;
      continue;
    }
    if(flag==0 && S.at(i)=='O') continue;
    if(flag==0 && S.at(i)=='I') continue;    
    
    if(flag==1 && S.at(i)=='J'){
      cnt++;
      continue;
    }
    if(flag==1 && S.at(i) == 'O'){
      level=cnt;
      cnt=1;
      flag=2;
      continue;
    }   
    if(flag==1 && S.at(i) == 'I'){
      cnt=0;
      flag=0;
      continue;
    }   
    if(flag==2 && S.at(i) == 'J'){
      cnt=1;
      flag=1;
      continue;
    }        
    if(flag==2 && S.at(i) == 'O'){
      cnt++;
      continue;
    }
    if(flag==2 && S.at(i) =='I'){
      if(cnt>level){
        flag=0;
        level=0;
        cnt=0;
        continue;
      }
      level=cnt;
      cnt=1;
      flag=3;
      continue;
    }
    if(flag==3 && S.at(i)=='J'){
      if(cnt<level){
        flag=1;
        level=0;
        cnt=1;
        continue;
      }       
      //level=min(level,cnt);
      maxlevel=max(level,maxlevel);
      flag=1;
      cnt=1;
      continue;
    }
    if(flag==3 && S.at(i)=='O'){
      if(cnt<level){
        flag=0;
        level=0;
        cnt=0;
        continue;
      }           
      //level=cnt;
      maxlevel=max(level,maxlevel);
      flag=0;
      cnt=0;
      continue;
    }    
    if(flag==3 && S.at(i)=='I'){
      cnt++;
    }
  }
  if(flag==3){
    if(cnt<level){
      level=0;
    }
    else{
      //level=min(level,cnt);
      maxlevel=max(level,maxlevel);
    }
  }
  cout<<maxlevel<<endl;
  return 0;
}

解答例

解説を見ると初めて見た技が使われていました。
(Kazuhiro Hosakaさんのコードを一部アレンジ)

このfor文回しが何をやっているのか、見ただけではよくわかりません。

途中にcout文を挟んで変数をみると、どうも連続するJ O Iを数えているようです。

if (i1 - i0 >= i2 - i1 && i2 - i1 <= i3 - i2)

この部分はi1-i0が’J'の連続数、i2-i1が’O'の連続数、i3-i2が'I'の連続数ですね。
Oが最小になっていればJOI文字列を作ることができます。

シンプルにすっきりとしたコードで驚きました。

#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000010

int N;
string S;

int main() {
	int i0, i1, i2, i3;
	
	cin>>S;
	N = S.length();
	
	int ans = 0;
	for (i0 = 0; i0 < N; i0 = i3) {
		for (i1 = i0; S[i1] == 'J'; ++i1);
		for (i2 = i1; S[i2] == 'O'; ++i2);
		for (i3 = i2; S[i3] == 'I'; ++i3);
         cout<<i0<<" "<<i1<<" "<<i2<<" "<<i3<<endl;//チェック用
		if (i1 - i0 >= i2 - i1 && i2 - i1 <= i3 - i2) {
			if (ans < i2 - i1) {
				ans = i2 - i1;
			}
		}
	}
	cout<<ans<<endl;
	
	return 0;
}