第一回日本最強プログラマー学生選手権決勝 A Equal Weight

問題へのリンク

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 4");
            WillReturn.Add("1 2 4");
            WillReturn.Add("3 6 10 15");
            //0 1 2 0
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 3");
            WillReturn.Add("3 2 1");
            WillReturn.Add("30 20 10");
            //-1
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct IndPairDef
    {
        internal int AInd;
        internal int BInd;
    }

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

        // IndのペアのList[和]なDict
        var IndPairListDict = new Dictionary<int, List<IndPairDef>>();

        for (int I = 0; I <= AArr.GetUpperBound(0); I++) {
            for (int J = 0; J <= BArr.GetUpperBound(0); J++) {
                int SumVal = AArr[I] + BArr[J];
                IndPairDef WillAdd;
                WillAdd.AInd = I;
                WillAdd.BInd = J;

                if (IndPairListDict.ContainsKey(SumVal) == false) {
                    IndPairListDict[SumVal] = new List<IndPairDef>();
                }
                IndPairListDict[SumVal].Add(WillAdd);

                if (IndPairListDict[SumVal].Count == 2) {
                    List<IndPairDef> CurrList = IndPairListDict[SumVal];
                    int Ind1 = CurrList[0].AInd;
                    int Ind2 = CurrList[0].BInd;
                    int Ind3 = CurrList[1].AInd;
                    int Ind4 = CurrList[1].BInd;
                    Console.WriteLine("{0} {1} {2} {3}", Ind1, Ind2, Ind3, Ind4);
                    return;
                }
            }
        }
        Console.WriteLine(-1);
    }
}

解説

Aの値は1以上100万以下
Bの値も1以上100万以下
AもBも重複値は無し

なので、
A+Bは2以上200万以下
Aを固定した場合、A+Bに重複値は無し
と分かります。

よって、
鳩ノ巣原理を使って
IndのペアのList[和]なDict
を更新していって、
解が見つかったら処理を打ち切れば、間に合います。