ARC150-A Continuous 1

問題へのリンク

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("4");
            WillReturn.Add("3 2");
            WillReturn.Add("1??");
            WillReturn.Add("4 2");
            WillReturn.Add("?1?0");
            WillReturn.Add("6 3");
            WillReturn.Add("011?1?");
            WillReturn.Add("10 5");
            WillReturn.Add("00?1???10?");
            //Yes
            //No
            //No
            //Yes
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int T = int.Parse(InputList[0]);

        var sb = new System.Text.StringBuilder();
        for (int I = 1; I <= InputList.Count - 1; I += 2) {
            int[] wkArr = InputList[I].Split(' ').Select(pX => int.Parse(pX)).ToArray();
            int K = wkArr[1];
            string S = InputList[I + 1];
            S = S.Replace("?", "X");
            string Result = Solve(K, S);
            sb.AppendLine(Result);
        }
        Console.Write(sb.ToString());
    }

    static string Solve(int pK, string pS)
    {
        char[] SArr = pS.ToCharArray();
        int UB = pS.Length - 1;

        // 1がない場合
        if (SArr.Contains('1') == false) {
            int KouhoCnt = 0;
            List<RunLen.RunLenInfo> RunLenList = RunLen.DeriveRunLenInfoList(pS);
            foreach (RunLen.RunLenInfo EachRunLen in RunLenList) {
                if (EachRunLen.AppearChar == 'X') {
                    if (EachRunLen.RunLen == pK) {
                        KouhoCnt++;
                    }
                    if (EachRunLen.RunLen > pK) {
                        return "No";
                    }
                }
            }
            if (KouhoCnt == 1) return "Yes";
            else return "No";
        }

        // 処理01 左端の1と右端の1を求める
        int LeftOne = -1;
        int RightOne = -1;

        for (int I = 0; I <= UB; I++) {
            if (SArr[I] == '1') {
                LeftOne = I;
                break;
            }
        }
        for (int I = UB; 0 <= I; I--) {
            if (SArr[I] == '1') {
                RightOne = I;
                break;
            }
        }

        // 処理02 間に0があったらNG
        for (int I = LeftOne; I <= RightOne; I++) {
            if (SArr[I] == '0') return "No";
        }

        int RangeCnt = RightOne - LeftOne + 1;

        // 処理03 連続した1の数を見る
        if (RangeCnt > pK) {
            return "No";
        }

        if (RangeCnt == pK) {
            return "Yes";
        }

        // 調整可能なXの数
        int LeftX = 0;
        for (int I = LeftOne; 0 <= I; I--) {
            if (SArr[I] == 'X') LeftX++;
            if (SArr[I] == '0') break;
        }

        int RightX = 0;
        for (int I = RightOne; I <= UB; I++) {
            if (SArr[I] == 'X') RightX++;
            if (SArr[I] == '0') break;
        }

        if (LeftX == 0 && RangeCnt + RightX >= pK) {
            return "Yes";
        }
        if (RightX == 0 && RangeCnt + LeftX >= pK) {
            return "Yes";
        }

        if (RangeCnt + LeftX + RightX < pK) {
            return "No";
        }

        if (RangeCnt + LeftX + RightX == pK) {
            return "Yes";
        }

        if (RangeCnt + LeftX + RightX > pK) {
            return "No";
        }

        return "No";
    }
}

#region RunLen
// ランレングス圧縮
internal class RunLen
{
    // ランレングス圧縮情報
    internal struct RunLenInfo
    {
        internal char AppearChar;
        internal int RunLen;
    }

    // ランレングス圧縮結果を返す
    internal static List<RunLenInfo> DeriveRunLenInfoList(string pBaseStr)
    {
        var WillReturn = new List<RunLenInfo>();

        int StrUB = pBaseStr.Length - 1;
        char PrevChar = pBaseStr[0];
        int StrLen = 0;
        for (int I = 0; I <= StrUB; I++) {
            if (pBaseStr[I] != PrevChar) {
                RunLenInfo WillAdd;
                WillAdd.AppearChar = PrevChar;
                WillAdd.RunLen = StrLen;
                WillReturn.Add(WillAdd);
                StrLen = 0;
                PrevChar = pBaseStr[I];
            }
            StrLen++;

            if (I == StrUB) {
                RunLenInfo WillAdd;
                WillAdd.AppearChar = pBaseStr[I];
                WillAdd.RunLen = StrLen;
                WillReturn.Add(WillAdd);
            }
        }
        return WillReturn;
    }
}
#endregion

解説

最初に1の有無で場合分けし、
1がなかった場合、
ランレングス圧縮し、
長さK超えの?があったらNo
長さKの?が1個だけならYes

1があった場合、
左端1と右端1を求め、間に0があったらNo
後は、左端1の左の連続?と、右端1の右の連続?で判定してます。

別解として、
0の個数のフェニック木と
1の個数のフェニック木を作って
連続1の開始区間が何通りあるかを調べると、実装が楽です。