SRM 257 DIV1 Hard Computers

問題 Editorial

問題

サイズamountの数値のmultisetであって、総和がnで、全ての要素がminInComp以上で、全ての要素の最大と最小の差がminDif以下であるようなものの場合の数を求めよ

• 5 <= minDif <= 1000
• 1 <= n, minInComp, amount <= 1000

解答

Editorialを参考にした。あまりよくわかっていない。
DP。
まず、minInCompは最初に(n -= amount*minInComp)してしまえば考える必要はなく、0以上で考えられる。
そのような、「全ての最低の数を引いてしまう」という考え方がさらにできる。
そのようにやると、O(amount^2*n)っぽいDPができるが、minDifが5以上であるという制約がうまく効いて(？)かなり速く実行できるようだ

コメント

あまりよくわかっていない。計算量の見積りがわからない。
ともかく「全部のlowerbound*数を引いてしまう」という考え方は普通に考えつくべきだ。しっかり覚えておこう

コード

#include <vector>
#include <cstring>
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
typedef long long ll;
ll dp[1111][1111];
struct Computers {
	int md;
	ll rec(int a, int n) {
		if(n < 0) return 0;
		if(a == 0) return n == 0;
		if(dp[a][n] != -1) return dp[a][n];
		ll r = 0;
		r += rec(a, n - a);
		rer(i, 1, a) {
			r += rec(a - i, n - md * (a - i));
		}
		return dp[a][n] = r;
	}
	long long choices(int n, int minDif, int minInComp, int amount) {
		md = minDif;
		mset(dp, -1);
		return rec(amount, n - minInComp * amount);
	}
};