結果

問題 No.130 XOR Minimax
コンテスト
ユーザー tes
提出日時 2016-02-08 18:01:59
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 4,203 bytes
コンパイル時間 1,305 ms
コンパイル使用メモリ 109,568 KB
実行使用メモリ 38,400 KB
最終ジャッジ日時 2024-09-21 21:49:16
合計ジャッジ時間 14,492 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff #
raw source code 

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

//No.130 XOR Minimax
//http://yukicoder.me/problems/282
class Program
{
    static string InputPattern = "InputX";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("1");
            WillReturn.Add("1");
            //0
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2");
            WillReturn.Add("2 3");
            //1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3");
            WillReturn.Add("0 4 0");
            //4
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct JyoutaiDef
    {
        internal int Level;
        internal int BitVal;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] AArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray();
        int MaxA = AArr.Max();

        int UB = 0;
        int wkJyousuu = 1;
        while (wkJyousuu < MaxA) {
            wkJyousuu *= 2;
            UB++;
        }

        Dictionary<int, int> KakuteiBitDict = DeriveKakuteiBitDict(UB, AArr);

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.Level = 0;
        WillPush.BitVal = 0;
        stk.Push(WillPush);

        int AnswerMaxXOR = int.MaxValue;
        int AnswerBitVal = 0;
        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();

            //クリア判定
            if (Popped.Level > UB) {
                int wkMaxXOR = DeriveMaxXOR(Popped, AArr);
                if (wkMaxXOR < AnswerMaxXOR) {
                    AnswerMaxXOR = wkMaxXOR;
                    AnswerBitVal = Popped.BitVal;
                    //Console.WriteLine("{0}とXORをとる、解候補{1}を発見",
                    //    AnswerBitVal, AnswerMaxXOR);
                }
                continue;
            }

            Action<bool> PushSyori = pBitOn =>
            {
                //ビットを1にする経路
                if (pBitOn) {
                    WillPush.Level = Popped.Level + 1;
                    WillPush.BitVal = DeriveOmomi(Popped.Level, UB);
                    stk.Push(WillPush);
                }
                //ビットを0にする経路
                else {
                    WillPush.Level = Popped.Level + 1;
                    WillPush.BitVal = Popped.BitVal;
                    stk.Push(WillPush);
                }
            };

            if (KakuteiBitDict.ContainsKey(Popped.Level)) {
                PushSyori(KakuteiBitDict[Popped.Level] == 1);
            }
            else {
                PushSyori(false);
                PushSyori(true);
            }
        }
        Console.WriteLine(AnswerMaxXOR);
    }

    //確定するビットのDictを返す
    static Dictionary<int, int> DeriveKakuteiBitDict(int pUB, int[] pAArr)
    {
        var WillReturn = new Dictionary<int, int>();
        for (int I = 0; I <= pUB; I++) {
            int Omomi = DeriveOmomi(I, pUB);

            //全ビット1の場合
            if (Array.TrueForAll(pAArr, X => (X & Omomi) == 1)) {
                WillReturn.Add(I, 1);
            }
            //全ビット0の場合
            else if (Array.TrueForAll(pAArr, X => (X & Omomi) == 0)) {
                WillReturn.Add(I, 0);
            }
        }
        return WillReturn;
    }

    //状態を引数として、最大のXORの値を返す
    static int DeriveMaxXOR(JyoutaiDef pJyoutai, int[] pAArr)
    {
        return pAArr.Max(X => (X ^ pJyoutai.BitVal));
    }

    //添え字に対応した2進数での桁の重みを返す
    static int DeriveOmomi(int pInd, int pUB)
    {
        return DeriveBekijyou2(pUB - pInd);
    }

    //2のべき乗を返す
    static int DeriveBekijyou2(int pJyousuu)
    {
        int WillReturn = 1;
        for (int I = 1; I <= pJyousuu; I++) {
            WillReturn *= 2;
        }
        return WillReturn;
    }
}
0