結果

問題 No.2918 Divide Applicants Fairly
ユーザー aketijyuuzou
提出日時 2024-10-08 20:22:23
言語 C#
(.NET 8.0.404)
結果
TLE  
実行時間 -
コード長 5,896 bytes
コンパイル時間 16,504 ms
コンパイル使用メモリ 170,828 KB
実行使用メモリ 33,664 KB
最終ジャッジ日時 2024-10-08 20:22:46
合計ジャッジ時間 20,780 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 60
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (103 ms)。
MSBuild のバージョン 17.9.6+a4ecab324 (.NET)
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

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

// https://yukicoder.me/problems/no/2918
class Program
{
    static string InputPattern = "InputX";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("4");
            WillReturn.Add("1050 1100 1300 1370");
            //20
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("6");
            WillReturn.Add("0 1 2 4 8 16");
            //1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("5");
            WillReturn.Add("1694 491 835 1875 1343");
            //7
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] RArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();

        // 半分全探索で解く
        var OddList = new List<long>();
        var EvenList = new List<long>();

        for (long I = 0; I <= RArr.GetUpperBound(0); I++) {
            if (I % 2 == 0) EvenList.Add(RArr[I]);
            if (I % 2 == 1) OddList.Add(RArr[I]);
        }

        List<JyoutaiDef> DFSResult1 = ExecDFS(EvenList.ToArray());
        List<JyoutaiDef> DFSResult2 = ExecDFS(OddList.ToArray());

        var AnswerList = new List<long>();
        //Console.WriteLine("EvenのDFS結果");
        //foreach (JyoutaiDef EachJyoutai in DFSResult1) {
        //    if (EachJyoutai.Level >= 2) {
        //        Console.WriteLine("Sum1={0},Sum2={1}", EachJyoutai.Sum1, EachJyoutai.Sum2);
        //        AnswerList.Add(EachJyoutai.Sum1 - EachJyoutai.Sum2);
        //    }
        //}
        //Console.WriteLine("OddのDFS結果");
        //foreach (JyoutaiDef EachJyoutai in DFSResult2) {
        //    if (EachJyoutai.Level >= 2) {
        //        Console.WriteLine("Sum1={0},Sum2={1}", EachJyoutai.Sum1, EachJyoutai.Sum2);
        //        AnswerList.Add(EachJyoutai.Sum1 - EachJyoutai.Sum2);
        //    }
        //}

        var DiffList1 = new List<long>();
        DFSResult1.ForEach(pX => DiffList1.Add(pX.Sum1 - pX.Sum2));

        var DiffList2 = new List<long>();
        DFSResult2.ForEach(pX => DiffList2.Add(pX.Sum1 - pX.Sum2));

        DiffList2.Sort();

        foreach (long EachLong in DiffList1) {
            long Shikii = EachLong * (-1);

            int Result1 = ExecNibunhou_LowerBound(Shikii, DiffList2);
            if (Result1 > -1) {
                AnswerList.Add(EachLong + DiffList2[Result1]);
            }

            int Result2 = ExecNibunhou_LowerOrEqual_Max(Shikii, DiffList2);
            if (Result2 > -1) {
                AnswerList.Add(EachLong + DiffList2[Result2]);
            }
        }

        Console.WriteLine(AnswerList.Min(pX => Math.Abs(pX)));
    }

    // 二分法で、Val以上で最小の値を持つ、添字を返す
    static int ExecNibunhou_LowerBound(long pVal, List<long> pList)
    {
        if (pList.Count == 0) return -1;

        // 最後の要素がVal未満の特殊ケース
        if (pVal > pList.Last()) {
            return -1;
        }
        // 最初の要素がVal以上の特殊ケース
        if (pVal <= pList[0]) {
            return 0;
        }

        int L = 0;
        int R = pList.Count - 1;

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

            if (pList[Mid] >= pVal) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }
        return R;
    }

    // 二分法で、Val以下で最大の値を持つ、添字を返す
    static int ExecNibunhou_LowerOrEqual_Max(long pVal, List<long> pList)
    {
        if (pList.Count == 0) return -1;

        // 最後の要素がVal以下の特殊ケース
        if (pVal >= pList.Last()) {
            return pList.Count - 1;
        }
        // 最初の要素がVal超えの特殊ケース
        if (pVal < pList[0]) {
            return -1;
        }

        int L = 0;
        int R = pList.Count - 1;

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

            if (pList[Mid] <= pVal) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        return L;
    }

    struct JyoutaiDef
    {
        internal long Sum1;
        internal long Sum2;
        internal long CurrInd;
        internal long Level;
    }

    // DFSで考えられる組み合わせを列挙
    static List<JyoutaiDef> ExecDFS(long[] pArr)
    {
        var WillReturn = new List<JyoutaiDef>();

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;

        for (long I = 0; I <= pArr.GetUpperBound(0); I++) {
            WillPush.Sum1 = pArr[I];
            WillPush.Sum2 = 0;
            WillPush.CurrInd = I;
            WillPush.Level = 1;
            Stk.Push(WillPush);

            WillPush.Sum1 = 0;
            WillPush.Sum2 = pArr[I];
            WillPush.CurrInd = I;
            WillPush.Level = 1;
            Stk.Push(WillPush);
        }

        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();
            WillReturn.Add(Popped);

            for (long I = Popped.CurrInd + 1; I <= pArr.GetUpperBound(0); I++) {
                WillPush.Sum1 = Popped.Sum1 + pArr[I];
                WillPush.Sum2 = Popped.Sum2;
                WillPush.CurrInd = I;
                WillPush.Level = Popped.Level + 1;
                Stk.Push(WillPush);

                WillPush.Sum1 = Popped.Sum1;
                WillPush.Sum2 = Popped.Sum2 + pArr[I];
                WillPush.CurrInd = I;
                Stk.Push(WillPush);
            }
        }
        return WillReturn;
    }
}
0