K4PC E - はじめての動的計画法(Easy Dynamic Programming)
問題
https://beta.atcoder.jp/contests/k4pc/tasks/k4pc_e
「n本の胡瓜があり、それぞれの重さはa[i]である
これらの部分集合(空でも良い)のうち、重さの総和がw以下であるようなものの個数を求めよ
1 <= n, w, a[i] <= 1000」
という問題について、答えがxになるような入力例を1つ作れ
(最低1つは作れることが保証される)
1 <= x <= 10^18
解法
wを1000にし、重さ1の胡瓜をa本追加すると、問題の答えは2^aだけ増える
よってまずはa個 (2^a <= x <2^(a+1)) 追加する
更にここに重さ1000-kの胡瓜を1本追加すると、答えはΣaCi (0<=i<=k)だけ増える
これで残りを埋めていく
ただしx=1の場合だけは、条件を満たすのが空集合だけにする必要があるから、適当にn=1, a[0]=2, w=1なんかを出力すればいい
(俺はひっかかった)
実装
aを求めるのには__builtin_clzのlonglong版を使った
xの2進数表記の左側に何個0が連なっているかを求められる
64からこれを引くことで立っているビットのうち一番左側のビットが何桁目(1-based)であるかを求められる
更に1を引いて0-basedに直してる
組み合わせの数はパスカルの三角形(メモ化再帰)で求めた
個人的にスニペット貼るだけで楽だからこれで十分な(二分累乗+フェルマーの小定理を使わなくてもTLE or MLEしない)ときはこれを使ってる
s[i]: ΣaCk (0 <= k <= i)
#define int long long int x, pa[101][101], s[101]; vector<int> res; // メモ化再帰(パスカルの三角形)でnCrを求める O(NR) int comb(int n, int r) { if (r<0 || r>n) return 0; if (r==0) return pa[n][r] = 1; if (pa[n][r]) return pa[n][r]; return pa[n][r] = min(1ll<<60, comb(n-1, r-1) + comb(n-1, r)); } signed main() { cin >> x; if (x==1) return cout << "1 1\n2" << endl, 0; int a = 64 - __builtin_clzll(x) - 1; rep(i,a) res.push_back(1); x -= 1ll<<a; rep(i,a+1) s[i] = min(1ll<<60, comb(a,i) + (i ? s[i-1] : 0)); for (int i=a;i>=0;i--) while (x>=s[i]) res.push_back(1000-i), x -= s[i]; cout << res.size() << ' ' << 1000 << endl; each(i,res) cout << i << endl; }