AtCoderの企業コンテスト    次の企業コンテストの問題へ    前の企業コンテストの問題へ

ZONeエナジー C MAD TEAM


問題へのリンク


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("3");
            WillReturn.Add("3 9 6 4 6");
            WillReturn.Add("6 9 3 1 1");
            WillReturn.Add("8 8 9 3 7");
            //4
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5");
            WillReturn.Add("6 13 6 19 11");
            WillReturn.Add("4 4 12 11 18");
            WillReturn.Add("20 7 19 2 5");
            WillReturn.Add("15 5 12 20 7");
            WillReturn.Add("8 7 6 18 5");
            //13
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10");
            WillReturn.Add("6 7 5 18 2");
            WillReturn.Add("3 8 1 6 3");
            WillReturn.Add("7 2 8 7 7");
            WillReturn.Add("6 3 3 4 7");
            WillReturn.Add("12 8 9 15 9");
            WillReturn.Add("9 8 6 1 10");
            WillReturn.Add("12 9 7 8 2");
            WillReturn.Add("10 3 17 4 10");
            WillReturn.Add("3 1 3 19 3");
            WillReturn.Add("3 14 7 13 1");
            //10
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct ABCDEInfoDef
    {
        internal long A;
        internal long B;
        internal long C;
        internal long D;
        internal long E;
    }
    static List<ABCDEInfoDef> mABCDEInfoList = new List<ABCDEInfoDef>();

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

        long[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            ABCDEInfoDef WillAdd;
            WillAdd.A = wkArr[0];
            WillAdd.B = wkArr[1];
            WillAdd.C = wkArr[2];
            WillAdd.D = wkArr[3];
            WillAdd.E = wkArr[4];
            mABCDEInfoList.Add(WillAdd);
        }
        ExecNibunhou();
    }

    // 2分法で解を求める
    static void ExecNibunhou()
    {
        long L = 0;
        long R = mABCDEInfoList.Max(pX => pX.A + 1);

        while (L + 1 < R) {
            long Mid = (L + R) / 2;

            if (CanAchieve(Mid)) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        Console.WriteLine(L);
    }

    // チームの総合力Kを達成可能かを返す
    static bool CanAchieve(long pK)
    {
        var BitSet = new HashSet<int>();
        foreach (ABCDEInfoDef EachABCDEInfo in mABCDEInfoList) {
            int CurrBit = 0;
            if (EachABCDEInfo.A >= pK) CurrBit += 1;
            if (EachABCDEInfo.B >= pK) CurrBit += 2;
            if (EachABCDEInfo.C >= pK) CurrBit += 4;
            if (EachABCDEInfo.D >= pK) CurrBit += 8;
            if (EachABCDEInfo.E >= pK) CurrBit += 16;
            BitSet.Add(CurrBit);
        }

        foreach (int EachInt1 in BitSet) {
            foreach (int EachInt2 in BitSet) {
                foreach (int EachInt3 in BitSet) {
                    if ((EachInt1 | EachInt2 | EachInt3) == 1 + 2 + 4 + 8 + 16) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}


解説

二分法で解いてます。