AOJ 0096: Sum of 4 Integers II

今日もAOJを埋めるだけの簡単なお仕事 (簡単とは言ってない)

問題概要

原文 → ４つの整数の和 | Aizu Online Judge

4000以下の正の整数が与えられる。0から1000までの範囲の整数の組でを満たす組み合わせの数を出力せよ。

解説

ナイーブ解法だと4重ループですが、とか間に合うわけありません。そこで、一旦「2つの0以上の整数の和がになる組み合わせの数」を0～2000の範囲で考え、配列に保存しておきます。

これがわかれば、「{の和がになる組み合わせ} = {の和がになる組み合わせ} + {の和がになる組み合わせ}」より、1つの入力あたり最大2001回の計算で解くことができます。が負になったり2000を超えたりしないように注意ですね。

ちなみに私は読解力がないので、が「0から1000までの整数」をとるという制約を忘れ、Combinationで解いてしまい最初死亡しました。まあおかげでCombinationのライブラリが副産物で出来上がったのでよしとしよう()

#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a; i<n; i++)
using namespace std;

int main() {
    int n;
    int a[2010];
    memset(a, 0, sizeof(a));
    rep(i,0,1001) rep(j,0,1001) a[i+j]++;
    while(cin >> n) {
        int ans = 0;
        rep(i,0,2001) {
            if(0 <= n-i && n-i <= 2000) ans = ans + a[i] * a[n - i];
        }
        cout << ans << endl;
    }
    return 0;
}