ARC151-A Equal Hamming Distances

問題へのリンク

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");
            WillReturn.Add("00100");
            WillReturn.Add("10011");
            //00001
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1");
            WillReturn.Add("0");
            WillReturn.Add("1");
            //-1
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        int UB = S.Length - 1;

        int DiffS = 0;
        int DiffT = 0;

        for (int I = 0; I <= UB; I++) {
            if (S[I] == '1') DiffS++;
            if (T[I] == '1') DiffT++;
        }

        if (DiffS == DiffT) {
            Console.WriteLine(new string('0', UB + 1));
            return;
        }

        if (DiffS > DiffT) {
            int tmp = DiffS;
            DiffS = DiffT;
            DiffT = tmp;

            string tmpS = S;
            S = T;
            T = tmpS;
        }

        char[] AnswerArr = new string('0', UB + 1).ToCharArray();

        if (DiffS == DiffT) {
            Console.WriteLine(new string(AnswerArr));
            return;
        }

        for (int I = UB; 0 <= I; I--) {
            if (S[I] != T[I] && S[I] == '0') {
                AnswerArr[I] = '1';
                DiffS++;
                DiffT--;
            }
            if (DiffS == DiffT) {
                Console.WriteLine(new string(AnswerArr));
                return;
            }
        }
        Console.WriteLine(-1);
    }
}

解説

ダイソーのオセロセットで考察すると、
下記で解けると分かります。

5桁なら00000をUの初期値とする。

SとU、TとUのハミング距離を求め
前者のほうが小さいように、SとTを必要なら交換。

後は、ハミング距離が一致するまで、下位ビットから
Sが0で、Tが1なら、Uを1にする。