ブログ記事 http://sayurin.blogspot.com/2013/12/c.html 新人女子プログラマの書いたコードを直すだけの簡単なお仕事です！｜paizaオンラインハッカソンVol.1 https://paiza.jp/poh/ec-campaign

CsPoh.cs

using System;

static class CsPoh {
    /// <summary>
    /// 標準入力のデータをintに変換する
    /// </summary>
    /// <param name="input">標準入力のバイト列</param>
    /// <param name="length">inputの長さ</param>
    /// <param name="values">変換結果を格納する配列</param>
    /// <remarks>
    /// <para>標準入力はASCII文字列だがこれをUnicodeに文字コード変換しstringインスタンスを生成するコストを回避するためにバイト列のまま処理する。
    /// セパレーターは' 'もしくは'\n'、Windows環境ではないため'\r'は含まない模様。</para>
    /// <para>引数3、変数4なので効率よく参照可能。（valuesは本来変数にして戻り値にすべきだが引数2、変数5となり効率が悪くなる。）</para>
    /// </remarks>
    static void ParseInput(byte[] input, int length, int[] values) {
        for (int i = 0, value = 0, offset = 0; i < length; i++) {
            var d = input[i] - '0';
            if (0 <= d)
                value = value * 10 + d;
            else {
                values[offset++] = value;
                value = 0;
            }
        }
    }

    /// <summary>
    /// Array.BinarySearch()から引用。https://github.com/mono/mono/blob/mono-2-8/mcs/class/corlib/System/Array.cs#L2072
    /// ただし、オリジナルと異なりビット反転しない。
    /// </summary>
    /// <param name="array">走査対象の配列</param>
    /// <param name="index">走査範囲の下限</param>
    /// <param name="length">走査範囲の長さ</param>
    /// <param name="value">走査する値</param>
    /// <returns>インデックス</returns>
    /// <remarks>
    /// <para>オリジナルコードはIComparer&lt;T&gt;を使用して比較するが、==演算子、&lt;演算子の方が効率いいため、int専用バージョンを用意する。</para>
    /// <para>mid（オリジナルではiMid）の計算はオーバーフローを考慮しているが、今回の条件では安全なため簡略化している。</para>
    /// <para>引数4、変数4なので効率よく参照可能。</para>
    /// </remarks>
    static int BinarySearch(int[] array, int index, int length, int value) {
        var low = index;
        var high = index + length - 1;
        while (low <= high) {
            var mid = (high + low) / 2;
            var current = array[mid];
            if (value == current)
                return mid;
            if (value < current)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return low;
    }

    /// <summary>
    /// Array.qsort()から引用。 https://github.com/mono/mono/blob/mono-2-8/mcs/class/corlib/System/Array.cs#L1762
    /// 要素数が8以下になった段階で挿入ソートに切り替える。
    /// </summary>
    /// <param name="array">ソート対象の配列</param>
    /// <param name="low0">ソート範囲の下限</param>
    /// <param name="high0">ソート範囲の上限</param>
    /// <remarks>
    /// <para>オリジナルコードはComparison&lt;T&gt;を使用して比較するが、==演算子、&lt;演算子の方が効率いいため、int専用バージョンを用意する。</para>
    /// <para>midの計算はオーバーフローを考慮しているが、今回の条件では安全なため簡略化している。</para>
    /// <para>変数に余裕があるためswap()はインライン展開してある。</para>
    /// <para>引数3、変数4なので効率よく参照可能。</para>
    /// </remarks>
    static void Sort(int[] array, int low0, int high0) {
        int low = low0, high, keyPivot, temp;
        if (high0 - low0 < 9) {
            // Insertion Sort
            for (; low <= high0; low++) {
                keyPivot = array[low];
                if (array[low - 1] > keyPivot) {
                    high = low;
                    temp = array[high - 1];
                    do {
                        array[high] = temp;
                        high--;
                    } while (high > low0 && (temp = array[high - 1]) > keyPivot);
                    array[high] = keyPivot;
                }
            }
        } else {
            // Quick Sort
            high = high0;
            keyPivot = array[(high + low) / 2];
            while (true) {
                while (low < high0 && keyPivot > array[low])
                    ++low;
                while (high > low0 && keyPivot < array[high])
                    --high;
                if (low <= high) {
                    temp = array[low];
                    array[low] = array[high];
                    array[high] = temp;
                    ++low;
                    --high;
                } else
                    break;
            }
            if (low0 < high)
                Sort(array, low0, high);
            if (low < high0)
                Sort(array, low, high0);
        }
    }

    static int Search(int[] values, int n, int targetPrice) {
        int low = 2, high, price;
        int bestPrice = 0, lprice = values[low];
        //if (lprice < targetPrice)  // 本来必要。ただしhighがinvalid offsetになるがvaluesに有効なエントリがあるため問題にならない。
        {
            high = BinarySearch(values, 2, n, targetPrice) - 1;
            var hprice = values[high];
            while (low < high) {
                price = lprice + hprice;
                if (price == targetPrice) {
                    bestPrice = price;
                    break;
                }
                if (price < targetPrice) {
                    if (bestPrice < price)
                        bestPrice = price;
                    lprice = values[++low];
                } else
                    hprice = values[--high];
            }
        }
        return bestPrice;
    }

    static void Calculate(int[] values, int n, int iend, byte[] output) {
        var offset = 0;
        Sort(values, 2, n + 1);
        for (int i = 2 + n; i < iend; i++) {
            var bestPrice = Search(values, n, values[i]);
#if false
            if (bestPrice == 0)
                output[offset++] = (byte)'0';
            else {
                var l = 100000 <= bestPrice ? 1000000 <= bestPrice ? 1000000
                                                                   :  100000
                      :  10000 <= bestPrice ?                          10000
                      :   1000 <= bestPrice ?                           1000
                      :    100 <= bestPrice ?                            100
                      :                                                   10;
                do {
                    output[offset++] = (byte)('0' + bestPrice / l);
                    bestPrice %= l;
                    l /= 10;
                } while (l >= 1);
            }
#else
            int c;
            if (100000 <= bestPrice) {
                if ((c = bestPrice / 1000000) > 0) {
                    output[offset++] = (byte)('0' + c); bestPrice %= 1000000;
                }
                output[offset++] = (byte)('0' + bestPrice / 100000); bestPrice %= 100000;
                output[offset++] = (byte)('0' + bestPrice /  10000); bestPrice %=  10000;
                output[offset++] = (byte)('0' + bestPrice /   1000); bestPrice %=   1000;
                output[offset++] = (byte)('0' + bestPrice /    100); bestPrice %=    100;
                output[offset++] = (byte)('0' + bestPrice /     10); bestPrice %=     10;
            } else if ((c = bestPrice / 10000) > 0) {
                output[offset++] = (byte)('0' + c);                bestPrice %= 10000;
                output[offset++] = (byte)('0' + bestPrice / 1000); bestPrice %=  1000;
                output[offset++] = (byte)('0' + bestPrice /  100); bestPrice %=   100;
                output[offset++] = (byte)('0' + bestPrice /   10); bestPrice %=    10;
            } else if ((c = bestPrice / 1000) > 0) {
                output[offset++] = (byte)('0' + c);               bestPrice %= 1000;
                output[offset++] = (byte)('0' + bestPrice / 100); bestPrice %=  100;
                output[offset++] = (byte)('0' + bestPrice /  10); bestPrice %=   10;
            } else if ((c = bestPrice / 100) > 0) {
                output[offset++] = (byte)('0' + c);              bestPrice %= 100;
                output[offset++] = (byte)('0' + bestPrice / 10); bestPrice %=  10;
            } else if ((c = bestPrice / 10) > 0) {
                output[offset++] = (byte)('0' + bestPrice / 10); bestPrice %= 10;
            }
            output[offset++] = (byte)('0' + bestPrice);
#endif
            output[offset++] = 10;
        }
        Console.OpenStandardOutput().Write(output, 0, offset);
    }

    static void Main() {
        const int valueLength = 2 + 200000 + 75;
        var input = new byte[valueLength * 7];
        var length = Console.OpenStandardInput().Read(input, 0, valueLength * 7);
        var values = new int[valueLength];
        ParseInput(input, length, values);
        var n = values[0];
        Calculate(values, n, 2 + n + values[1], new byte[75 * 7]);
    }
}