第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; }