hogecoder

tsutaj 競技プログラミングの記録

AOJ 0096: Sum of 4 Integers II

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

問題概要

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

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

解説

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

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

ちなみに私は読解力がないので、 a, b, c, dが「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;
}