アンバランス [ARC059 : D]

問題

http://arc059.contest.atcoder.jp/tasks/arc059_b

文字列tの連続する部分文字列のうち、アンバランスな文字列があるか判定する。
あるなら、その部分文字列を（要素番号で）示せ

アンバランスな文字列とは以下の条件を満たす文字列

• 長さが2以上
• 文字のうち過半数が同じ文字

2 <= |s| <= 10^5

考察

1. 部分点に騙された感ある
2. 部分点は愚直解として、全ての連続する文字列を列挙して、判定すれば通る
3. この方針で考えると、満点は取れない

4. まだ400点問題なので、何らかの簡単な実装がありそう
5. 実験をすると重要な考察が得られる
6. 「同じ文字が2つ連続していればそれがアンバランスな部分文字列」
7. 「1つ飛びで同じ文字が連続していればそれがアンバランスな部分文字列」
8. 証明できないけど、反例もなさそう

実装

http://arc059.contest.atcoder.jp/submissions/839363

string s;
//-----------------------------------------------------------------
pair<int, int> solve() {
	int n = s.length();
 
	rep(i, 1, n) if (s[i - 1] == s[i]) {
		return make_pair(i, i + 1);
	}
 
	rep(i, 2, n) if (s[i - 2] == s[i]) {
		return make_pair(i - 1, i + 1);
	}
 
	return make_pair(-1, -1);
}
//-----------------------------------------------------------------
int main() {
	cin >> s;
	auto p = solve();
	cout << p.first << " " << p.second << endl;
}