AtCoder ARC #059 : D - アンバランス / Unbalanced

速度自体はそこまで悪くないけど、ミスが多すぎてだいぶ順位を落としてしまった。
http://arc059.contest.atcoder.jp/tasks/arc059_b

問題

文字列Tがアンバランスであるとは、T中である１種類の文字が過半数ある状態を示す。
文字列Sが与えられるので、Sの部分文字列でアンバランスであるものが存在すればそれを示せ。

解法

文字列がアンバランスであるならば、以下の何れかを満たす。

• 同じ文字が2文字以上続いている箇所がある
• 文字列が奇数長で、1文字おきに同じ文字が来る

前者の判定は容易だろう。
後者はまじめに全部分文字列に対して判定するとO(|S|^2)程度かかるが、よく考えると３文字のケースだけを考えればよいことがわかる。

よって以下を判定すればよい。

• 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");
}

まとめ

気づけば簡単。