野田さんのやつの最終コード

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

マジメにやった最終版。

//C.
#include <stdio.h>
#include <stdlib.h>

#define MAX_N (1000000)
#define MIN_N (10)

//高速版atoi
//http://lazyattribute.sakuratan.com/la/?p=656 改変.
int fast_atoi(const char *s)
{
    int result = 0;
    while(1)
    {
        if(*s > '9' || *s < '0')break;
        result = result * 10 + *s - '0';
        s++;
    }

    return result;
}

//ソート前からnを全て配列の添え字で換算する.
//重複アイテムを判別するためn_arrayは++する.
int main(){

    int N, D, i, d;

    scanf("%d %d\n", &N, &D);

    const int strbuf_size = (N + D + 3) * 8 * sizeof(char);
    const int d_array_size = D * sizeof(int);
    const int n_array_size = MAX_N * sizeof(char);

//    char *strbuf = calloc(strbuf_size + d_array_size + n_array_size, 1);
    char *strbuf = malloc(strbuf_size + d_array_size + n_array_size);    //ホントはcallocのほうが良い.
    int *d_array = (int *)(strbuf + strbuf_size);                    //普通の配列.
    char *n_array = (char *)(strbuf + strbuf_size + d_array_size);    //nがあれば, n_array[n]++.

    //一括Read.
    fread(strbuf, strbuf_size, 1, stdin);

    //自作strtok().
    char *p = strbuf;
    for (i = 0; i < N; i++){
//        n_array[strtol(p, NULL, 10)]++;        //3倍以上遅い.
        n_array[fast_atoi(p)]++;
        while (*p != '\n') p++;
        p++;
    }
    for (i = 0; i < D; i++){
        d_array[i] = fast_atoi(p);
        while (*p != '\n') p++;
        p++;
    }
    const char *min_answerp = n_array + MIN_N;    //答えになる最小値.
    for (d = 0; d < D; d++){
        int answer = 0;    //今の解候補.
        int target = d_array[d];
        int diff = target - MIN_N + 1;

        char *np;
        for (np = n_array + target - MIN_N; np >= min_answerp; np--){
            if (*np){
                int n_value = (int)(np - n_array);
                *np -= 1;    //1つしかないときの重複参照を防止する.

                //OKならdiffが0になる値からスタート.
                char *mp, *mp0;
                for (mp = mp0 = n_array + (target - n_value); (mp >= min_answerp) && ((int)(mp0 - mp) < diff); mp--){
                    if (*mp){
                        int sum = n_value + (int)(mp - n_array);
                        int diff_temp = target - sum;
                        if (sum == target){
                            answer = sum;
                            *np += 1;
                            np = n_array; break;    //npのforからも抜ける.
                        } else if (diff_temp < diff){
                            answer = sum;
                            diff = diff_temp;
                        }
                        break;    //1つのnに対する良いmは１つのみ.
                    }
                }
                *np += 1;
            }
        }
        fprintf(stdout, "%d\n", answer);
    }
    return 0;
}

atoi()の高速化だけはネットからGetしてきましたが他は独力です。
簡単に説明すると・・・

●入力＆ソート
入力は一括でバッファに。その後strtok()で価格をひとつずつ読み込み、該当する配列要素を++しています。基数ソートとかバケットソートとか言うみたいです。

●答えの算出＆出力
例えば設定金額が100の場合、答えの１つを90以下で探します。90が見つかったら次に10を探します。価格を配列で持っていると探しやすいです。
もし１つめが50だったらもうひとつも50から探しますが、50円の商品が1つしかない場合にエラーにならないよう配列要素を増減させてます。

●高速化
strtokが重いので自作して３倍ぐらい高速化。atoi()が重いのでネットから取ってきて３倍ぐらい高速化。
Cではsetvbuf()でI/Oの設定ができますが、特に効果が見えなかったので入れてません。
I/Oを一括でやるか要素ごとにやるかもあまり違いがありませんでした。
ローカルの擬似環境を用意して速度計測するのが重要ですね。支配的なところから高速化していくのが大事です。