速度自体はそこまで悪くないけど、ミスが多すぎてだいぶ順位を落としてしまった。
http://arc059.contest.atcoder.jp/tasks/arc059_b
問題
文字列Tがアンバランスであるとは、T中である1種類の文字が過半数ある状態を示す。
文字列Sが与えられるので、Sの部分文字列でアンバランスであるものが存在すればそれを示せ。
解法
文字列がアンバランスであるならば、以下の何れかを満たす。
- 同じ文字が2文字以上続いている箇所がある
- 文字列が奇数長で、1文字おきに同じ文字が来る
前者の判定は容易だろう。
後者はまじめに全部分文字列に対して判定するとO(|S|^2)程度かかるが、よく考えると3文字のケースだけを考えればよいことがわかる。
よって以下を判定すればよい。
- S[i]==S[i+1]となるiが存在するか
- S[i]==S[i+2]となるiが存在するか
string S; int N; void solve() { int i,j,k,l,r,x,y; string s; cin>>S; N=S.size(); FOR(i,N-1) { if(S[i]==S[i+1]) return _P("%d %d\n",i+1,i+2); } FOR(i,N-2) { if(S[i]==S[i+2]) return _P("%d %d\n",i+1,i+3); } _P("-1 -1\n"); }
まとめ
気づけば簡単。