ABC-124-D Handstand

■■■問題■■■

N人の人が左右一列に並んでいます。
0,1からなる長さNの文字列Sと正整数Kが与えられます。

左からi番目の人は、Sのi文字目が0のとき直立し、1のとき逆立ちしています。
あなたはK回まで以下の指示を行います。一度も行わなくても構いません。

指示:
1 <= l <= r <= Nを満たす整数 l,r を選ぶ。
左から l,l+1, ・・・ , r番目の人の状態を反転する。
すなわち、i=l,l+1, ・・・ , r について、
左からi番目の人は直立していれば逆立ちし、逆立ちしていれば直立する。

K回までの指示で、逆立ちした人を連続で最大何人並ばせることができるか求めてください。

■■■入力■■■

N K
S

●Nは 1 <= N <= 10万 を満たす整数である。
●Kは 1 <= K <= 10万 を満たす整数である。
●文字列Sの長さはNである。
●文字列Sの各文字は0または1である。

■■■出力■■■

K回までの指示で、逆立ちした人を連続で最大何人並ばせることができるか出力せよ。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("5 1");
            WillReturn.Add("00010");
            //4
            //以下のように指示を行えば逆立ちした人を連続して4人並ばせることができ、これが最大です。
            //●l=1,r=3 として指示を行う。その結果、左から1,2,3 番目の人の状態が反転する。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("14 2");
            WillReturn.Add("11101010110011");
            //8
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1 1");
            WillReturn.Add("1");
            //1
            //一度も指示を行う必要はありません
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray();
        int K = wkArr[1];

        char[] SArr = InputList[1].ToCharArray();
        int UB = SArr.GetUpperBound(0);

        //ランレングス圧縮を行う
        //添字が偶数なら1のLength、奇数なら0のLengthを持つ、List
        var SeqList = new List<int>();
        int SeqCnt = 1;
        for (int I = 0; I <= UB; I++) {
            if (I == 0 && SArr[I] == '0') {
                SeqList.Add(0); //左端が0なら、番兵として、左端に1を追加する(lengthは0)
            }

            //連続した範囲の最後の場合
            if (I == UB || SArr[I] != SArr[I + 1]) {
                SeqList.Add(SeqCnt);
                SeqCnt = 1;
            }
            else {
                SeqCnt++;
            }

            if (I == UB && SArr[I] == '0') {
                SeqList.Add(0); //右端が0なら、番兵として、右端に1を追加する(lengthは0)
            }
        }

        //尺取法で解く
        int R = 0;
        int CurrSum = SeqList[0];
        int Answer = SeqList[0];
        UB = SeqList.Count - 1;

        //for (int I = 0; I <= UB; I++) Console.WriteLine("SeqList[{0}]={1}", I, SeqList[I]);

        for (int L = 0; L <= UB; L += 2) {
            while (R < UB && (R - L) / 2 < K) {
                CurrSum += SeqList[R + 1];
                CurrSum += SeqList[R + 2];
                R += 2;
            }

            //Console.WriteLine("始点{0},終点{1}での和={2}", L, R, CurrSum);

            Answer = Math.Max(Answer, CurrSum);
            if (L + 2 < UB) {
                CurrSum -= SeqList[L];
                CurrSum -= SeqList[L + 1];
            }
        }
        Console.WriteLine(Answer);
    }
}

解説

端が0の時に備えて、番兵を配置しつつ、ランレングス圧縮し、
1のみを始点と終点の候補にして、尺取法で解いてます。