D - Wide Flip AtCoder Regular Contest 088 日本語

D - Wide Flip

問題概略

0と1からなる文字列sが与えられる。長さK以上の区間を何回か反転して全てを0にしたい。最大のKを求めよ

制約

• $1\le |S|\le {10}^5$
• $S_i(1\le i\le N)$ は 0 または 1 である

解法

K個とK+1個の反転を利用して、左からK+1個目以降のものを自由にイジれる

右も同じ。

具体的な文字列でなく、抽象的なものに対して考えるべきだった。

public static void main(String[] args)
    {
        //longを忘れるなオーバーフローするぞ
        s = sc.next();
        N = s.length();
        K = N / 2;
        if (N == 1)
        {
            System.out.println("1");
            return;
        }
        int l = N / 2 - 1;
        int r = N / 2;
        if (N % 2 == 1)
        {
            r++;
            K++;
        }
        while (s.charAt(l) == s.charAt(r) && s.charAt(l) == s.charAt(N / 2))
        {
            K++;
            l--;
            r++;
            if (l < 0) break;
        }
        System.out.println(K);

    }