ARC219-A Similarity

問題へのリンク

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 3");
            WillReturn.Add("000");
            WillReturn.Add("111");
            WillReturn.Add("110");
            WillReturn.Add("100");
            WillReturn.Add("011");
            //Yes
            //101
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 2");
            WillReturn.Add("00");
            WillReturn.Add("01");
            WillReturn.Add("10");
            WillReturn.Add("11");
            //No
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("9 50");
            WillReturn.Add("00001000011111100011111000011111000001000001111100");
            WillReturn.Add("00010100010000010100000100100000100011000010000010");
            WillReturn.Add("00100010010000010100000000000000100101000010000010");
            WillReturn.Add("01000001011111100100000000011111000001000001111110");
            WillReturn.Add("01111111010001000100000000100000000001000000000010");
            WillReturn.Add("01000001010000100100000100100000000001000010000010");
            WillReturn.Add("01000001010000010011111000111111100111110001111100");
            WillReturn.Add("00000000000000000000000000000000000000000000000000");
            WillReturn.Add("11111111111111111111111111111111111111111111111111");
            //Yes
            //10101010101010101010101011010101011010101101010101
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

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

        string[] SArr = InputList.Skip(1).ToArray();
        SArr = SArr.Distinct().ToArray();
        List<string> StrList = SArr.ToList();

        long StrUB = SArr[0].Length - 1;

        var sb = new System.Text.StringBuilder();

        // カレント文字でループ
        for (int I = 0; I <= StrUB; I++) {
            long OneCnt = 0;
            long ZeroCnt = 0;

            foreach (string EachStr in StrList) {
                if (EachStr[I] == '0') ZeroCnt++;
                if (EachStr[I] == '1') OneCnt++;
            }

            bool RemoveZero = (ZeroCnt > OneCnt);
            if (RemoveZero) {
                sb.Append(0);
            }
            else {
                sb.Append(1);
            }

            for (int J = StrList.Count - 1; 0 <= J; J--) {
                if (RemoveZero == true && StrList[J][I] == '0') StrList.RemoveAt(J);
                if (RemoveZero == false && StrList[J][I] == '1') StrList.RemoveAt(J);
            }
        }

        if (StrList.Count == 0) {
            Console.WriteLine("Yes");
            Console.WriteLine(sb.ToString());
        }
        else {
            Console.WriteLine("No");
        }
    }
}

解説

まず、NGなケースを文字列長ごとに考えます。

●文字列長が1文字の場合
0
1
の時にNGです。

●文字列長が2文字の場合
00
01
10
11
の時にNGです。

●文字列長が3文字の場合
000
001
010
011
100
101
110
111
の時にNGです。

以上の考察により、
N文字の場合は、
2のN乗通りの文字があったらNGなことが分かります。

またNGでない場合は、ライアーゲームの少数決のように
多数派を消していくのが、解だと分かります。

具体的には、下記となります。(多数派を消す流れ)
文字列長が3文字で8通りある場合は、8 → 4 → 2 となりNG
文字列長が3文字で7通りある場合は、7 → 3 → 1 としてOK