ABC-123-D Cake 123

■■■問題■■■

AtCoder洋菓子店は数字の形をしたキャンドルがついたケーキを販売しています。
ここには 1,2,3 の形をしたキャンドルがついたケーキがそれぞれ X種類、Y種類、Z種類あります。
それぞれのケーキには「美味しさ」という整数の値が以下のように割り当てられています。

●1の形のキャンドルがついたケーキの美味しさはそれぞれ A1,A2, ・・・ , AX
●2の形のキャンドルがついたケーキの美味しさはそれぞれ B1,B2, ・・・ , BY
●3の形のキャンドルがついたケーキの美味しさはそれぞれ C1,C2, ・・・ , CZ

高橋君はABC123を記念するために、1,2,3の形のキャンドルがついたケーキを1つずつ買うことにしました。
そのようにケーキを買う方法は X*Y*Z通りあります。

これらの選び方を3つのケーキの美味しさの合計が大きい順に並べたとき、
1,2, ・・・ , K番目の選び方でのケーキの美味しさの合計をそれぞれ出力してください。

■■■入力■■■

X Y Z K
A1 A2 A3 ・・・ AX
B1 B2 B3 ・・・ BY
C1 C2 C3 ・・・ CZ

●1 <= X <= 1000
●1 <= Y <= 1000
●1 <= Z <= 1000
●1 <= K <= min(3000 , X*Y*Z)
●1 <= Ai <= 100億
●1 <= Bi <= 100億
●1 <= Ci <= 100億
●入力は全て整数である

■■■出力■■■

i行目に、問題文中のi番目の値を出力せよ。

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("2 2 2 8");
            WillReturn.Add("4 6");
            WillReturn.Add("1 5");
            WillReturn.Add("3 8");
            //19
            //17
            //15
            //14
            //13
            //12
            //10
            //8
            //3つのケーキの選び方は 2×2×2=8通りあり、
            //それらをケーキの美味しさの合計が大きい順に並べると以下の通りです。
            //●(A2,B2,C2): 6+5+8=19
            //●(A1,B2,C2): 4+5+8=17
            //●(A2,B1,C2): 6+1+8=15
            //●(A2,B2,C1): 6+5+3=14
            //●(A1,B1,C2): 4+1+8=13
            //●(A1,B2,C1): 4+5+3=12
            //●(A2,B1,C1): 6+1+3=10
            //●(A1,B1,C1): 4+1+3= 8
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 3 3 5");
            WillReturn.Add("1 10 100");
            WillReturn.Add("2 20 200");
            WillReturn.Add("1 10 100");
            //400
            //310
            //310
            //301
            //301
            //美味しさの合計が同じになる組み合わせが複数ある可能性もあります。
            //例えば、このテストケースで (A1,B3,C3) を選ぶときと
            //(A3,B3,C1) を選ぶときはともに、美味しさの合計が301となります。
            //しかし、これらは異なる選び方であるため、出力には301が2回出現します。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10 10 10 20");
            WillReturn.Add("7467038376 5724769290 292794712 2843504496 3381970101 8402252870 249131806 6310293640 6690322794 6082257488");
            WillReturn.Add("1873977926 2576529623 1144842195 1379118507 6003234687 4925540914 3902539811 3326692703 484657758 2877436338");
            WillReturn.Add("4975681328 8974383988 2882263257 7690203955 514305523 6679823484 4263279310 585966808 3752282379 620585736");
            //23379871545
            //22444657051
            //22302177772
            //22095691512
            //21667941469
            //21366963278
            //21287912315
            //21279176669
            //21160477018
            //21085311041
            //21059876163
            //21017997739
            //20703329561
            //20702387965
            //20590247696
            //20383761436
            //20343962175
            //20254073196
            //20210218542
            //20150096547
            //入力・出力は32ビット整数に収まらない可能性があることに注意してください。
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long X = wkArr[0];
        long Y = wkArr[1];
        long Z = wkArr[2];
        int K = (int)wkArr[3];

        long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long[] BArr = InputList[2].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long[] CArr = InputList[3].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        Array.Sort(AArr, (A, B) => B.CompareTo(A));
        Array.Sort(BArr, (A, B) => B.CompareTo(A));
        Array.Sort(CArr, (A, B) => B.CompareTo(A));

        int UB_A = AArr.GetUpperBound(0);
        int UB_B = BArr.GetUpperBound(0);
        int UB_C = CArr.GetUpperBound(0);

        var SumAB = new List<long>();
        for (int I = 0; I <= UB_A; I++) {
            for (int J = 0; J <= UB_B; J++) {
                if ((I + 1) * (J + 1) > K) break;
                SumAB.Add(AArr[I] + BArr[J]);
            }
        }
        SumAB.Sort((A, B) => B.CompareTo(A));

        var SumABC = new List<long>();
        for (int I = 0; I <= Math.Min(SumAB.Count, K) - 1; I++) {
            for (int J = 0; J <= UB_C; J++) {
                if ((I + 1) * (J + 1) > K) break;
                SumABC.Add(SumAB[I] + CArr[J]);
            }
        }
        SumABC.Sort((A, B) => B.CompareTo(A));
        var sb = new System.Text.StringBuilder();
        for (int I = 0; I <= Math.Min(SumABC.Count, K) - 1; I++) {
            sb.AppendLine(SumABC[I].ToString());
        }
        Console.Write(sb.ToString());
    }
}

解説

AとBのみの和で、3000位まで求めた後、
Cも含めた和で、3000位まで求めてます。

Aの1位との和は、Bの3000位までとしか求めない。
Aの2位との和は、Bの1500位までとしか求めない。
Aの3位との和は、Bの1000位までとしか求めない。
Aの4位との和は、Bの 750位までとしか求めない。
Aの5位との和は、Bの 600位までとしか求めない。
Aの6位との和は、Bの 500位までとしか求めない。
といった枝切りも行ってます。