ABC-043-D アンバランス

■■■問題■■■

文字列tについて、tの長さが2以上であり、かつ
tの中の文字のうち過半数が同じ文字であるとき、
tをアンバランスであると呼ぶことにします。

例えば、'voodoo'や'melee'はアンバランスであり、
'noon'や'a'はアンバランスではありません。

小文字のアルファベットからなる文字列sが与えられます。
sにアンバランスな (連続する)部分文字列が存在するか判定してください。
存在する場合は、sの中でそのような部分文字列が存在する位置を一つ示してください。

■■■入力■■■

s

●2 <= |s| <= 10の5乗
●sは小文字のアルファベットのみからなる

■■■出力■■■

sにアンバランスな部分文字列が存在しない場合は、'-1 -1' と出力せよ。

sにアンバランスな部分文字列が存在する場合は、そのような部分文字列の一つを
sasa+1 ・・・ sb (1 <= a<b <= |s|)として、'a b' と出力せよ。
そのような部分文字列が複数存在する場合は、いずれも正解とみなされる。

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("needed");
            //2 5
            //文字列 s2s3s4s5 = 'eede' はアンバランスな文字列です。
            //他にもアンバランスな部分文字列は存在し、
            //例えば '2 6'と出力しても正解となります。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("atcoder");
            //-1 -1
            //文字列 'atcoder' はアンバランスな部分文字列を持ちません
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        string S = InputList[0];

        //始点のループ
        int UB = S.Length - 1;
        for (int I = 0; I <= UB; I++) {
            char StaChar = S[I];

            int Ind1 = I + 1;
            int Ind2 = I + 2;
            if (Ind1 <= UB && S[Ind1] == StaChar) {
                Console.WriteLine("{0} {1}", I + 1, Ind1 + 1);
                return;
            }
            if (Ind2 <= UB && S[Ind2] == StaChar) {
                Console.WriteLine("{0} {1}", I + 1, Ind2 + 1);
                return;
            }
        }
        Console.WriteLine("-1 -1");
    }
}

解説

始点をループさせつつ、
始点の文字をA、A以外の文字をXとして
下記の3通りに場合分けしてます。

場合1 AA
場合2 AXA
場合3 AXX

場合1と場合2は、解となることが確定します。

場合3は、
Aが1文字、A以外の文字が2文字で、
文字列の中にA以外の文字のほうが多いので、
これ以上終点を右に移動させるよりも、
4文字目を始点としたほうが、Aが半分超えとなる文字列を見つけやすいので、
(AXXを含んでも、Aが過半数な文字列ならば、AXXを含まなくてもAが過半数な文字列なため)
1文字目を始点とした処理を中止できます。