ホリエモンからの挑戦状

■■■問題■■■

長さの異なった棒がいくつかあります。
たとえば、次のような長さが8,4,10,3,2の5種類の棒



があるとすると、これらの中から3つ選んでつなぎ合わせ、
長さがちょうど15になる棒の長さの組み合わせは(8,4,3)と(10,3,2)の2通りあります。



つなぎ合わせる際の、棒の順番は考慮しません。
つまり、(8,4,3),(8,3,4),(4,8,3), ・・・ のような選び方は、すべて同じ組み合わせと考えます。

また、つなぎ合わせる棒は必ず3本で、1本・2本だけで目的の長さになっていたとしても、
それは組み合わせに含みません。

つなぎ合わせたときの長さLと、
N個 (1 <= N <= 5000) の棒の長さが標準入力から与えられるとき、
N個の棒の中から3つをつなぎ合わせて長さがLになる組み合わせの個数を求めるプログラムを書いてください。

ただし、個々の棒の長さや、つなぎ合わせた長さ(L)は正の整数で、32bit整数で十分扱える範囲です。
また、棒の長さはすべて異なるものとします。

■■■入力■■■

標準入力から、以下の形式で複数の整数値を読み込みます。

L
N
a1
a2
・
・
・
aN

1行目のLは、つなぎ合わせた棒の長さです。
2行目のNは、棒の数です。
3行目以降のN行は個々の棒の長さで、長さは全て異なるものとします。

■■■出力■■■

標準出力に、整数値を1つ出力してください。行末での改行は有無を問いません

C#のソース

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

class Program
{
    static string InputPattern = "Input1";

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

        if (InputPattern == "Input1") { //サンプル入力
            WillReturn.Add("15");
            WillReturn.Add("5");
            WillReturn.Add("8");
            WillReturn.Add("4");
            WillReturn.Add("10");
            WillReturn.Add("3");
            WillReturn.Add("2");
            //2
        }
        else if (InputPattern == "Input2") { //サンプル入力
            WillReturn.Add("35");
            WillReturn.Add("10");
            WillReturn.Add("13");
            WillReturn.Add("12");
            WillReturn.Add("17");
            WillReturn.Add("10");
            WillReturn.Add("4");
            WillReturn.Add("18");
            WillReturn.Add("3");
            WillReturn.Add("11");
            WillReturn.Add("5");
            WillReturn.Add("7");
            //6
        }
        else if (InputPattern == "Input3") { //最悪計算量
            for (int I = 1; I <= 5000 + 2; I++) {
                WillReturn.Add(I.ToString());
                WillReturn[0] = "9999";
            }
        }
        else { //実際の入力
            string wk;
            while ((wk = Console.ReadLine()) != null) WillReturn.Add(wk);
        }
        return WillReturn;
    }

    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();

        List<string> InputList = GetInputList();

        int L = int.Parse(InputList[0]);

        var BouLengthList = new List<int>();
        foreach (string EachStr in InputList.Skip(2)) {
            BouLengthList.Add(int.Parse(EachStr));
        }
        int[] BouLengthArr = BouLengthList.OrderBy(X => X).ToArray();

        int UB = BouLengthArr.GetUpperBound(0);

        int AnswerCnt = 0;
        for (int I = 0; I <= UB - 2; I++) {
            for (int J = I + 1; J <= UB - 1; J++) {
                int Rest = L - BouLengthArr[I] - BouLengthArr[J];
                if (Rest <= BouLengthArr[J]) break;

                int wkInd = Array.BinarySearch<int>(BouLengthArr, Rest);
                if (wkInd < 0) continue;

                AnswerCnt++;

                Console.WriteLine("解{0} ({1},{2},{3})",
                    AnswerCnt, BouLengthArr[I], BouLengthArr[J], BouLengthArr[wkInd]);
            }
        }
        Console.WriteLine("実行時間={0}", sw.Elapsed);
        Console.WriteLine(AnswerCnt);
    }
}

デバッグ情報付の実行結果

解1 (2,3,10)
解2 (3,4,8)
実行時間=00:00:00.0289478
2

解説

事前の昇順にソートした配列を用意しておき、
2つの棒の長さのを引いた長さの棒が配列に存在するかをバイナリサーチでチェックしてます。

Array.BinarySearch<T> メソッド
Array.BinarySearchで、検索範囲の開始位置を示すインデックスと検索する範囲の長さ
を指定すれば、さらに速くなりそうですね。

総勢986名の方が挑戦！ホリエモンからの挑戦状 --- CodeIQ MAGAZINE