お題箱より。
Programming Problems and Competitions :: HackerRank
解法
分数のままでは考えにくいので、通分します。 の最大公約数は
なので、まず重りを全て
倍して
とします。そして目標の重さも
に置き換えます。するとこの問題は「重さ
の重りをそれぞれ
個以下使って合計
を作る場合の数を求めよ」という問題と見なせます。もし
が整数にならない場合は0通りです。
これは「部分和問題」と呼ばれるもので、特に今回は
- 個数制限付き:各要素が何個まで使えるか指定されている
- 数え上げ:
が作れるかどうかの判定だけでなく、その作り方の場合の数を求める必要がある
という特徴があります。
これを公式解説のDPで解きます。以下のようなDPテーブルを定義します。
重り
までの使い方を決めて、その合計が
であるような重りの使い方の場合の数
この遷移ですが…具体例で説明しましょう。重り の重さが
で、これが
個まで使えるとします。このときの
から
からの更新方法を考えます。
更新の順番として、 ごとに更新をしていくという方法を取ります。つまり
をこの順に更新する。
をこの順に更新する。
- …
をこの順に更新する。
という流れです。
いま重さ の重りを
個まで使える場合を考えているので、
に遷移できるのは
の3点からです。例えば
を更新する時には、以下の図のような遷移になります。
つまり遷移元が一定の長さを保ったままスライドしていくので、例えば の遷移元と
の遷移元の違いは両端だけです。このように範囲に入るものと出るものを差分更新することで、遷移元の値を効率的に管理することが出来ます。(解説の「しゃく取り法っぽく」はこれを指しています)
このようにすれば重り1種類についての遷移の計算量は です。
で分類しているだけで結局は遷移先の
を1回ずつ見ていることになり、遷移元の計算は差分更新で毎回
でできているからです。重りの種類数を
とあえて明示すると、全体計算量は
になります。
は制約より600万以下です。
ACコード
HackerRankは提出が非公開らしいので、ベタ書きします。
#include <bits/stdc++.h> using namespace std; int main(){ int A[5], P, Q; for(int i=0; i<5; i++) cin >> A[i]; int W[5] = {60, 30, 20, 15, 12}; cin >> P >> Q; if(60%Q){ cout << 0 << endl; return 0; } int S = P*60/Q; static int64_t dp[6][6000001]; dp[0][0] = 1; for(int i=0; i<5; i++){ for(int r=0; r<W[i]; r++){ int64_t sum = 0; for(int s=r; s<=S; s+=W[i]){ sum += dp[i][s]; int out = s - (A[i]+1)*W[i]; if(out >= 0) sum -= dp[i][out]; dp[i+1][s] = sum; } } } cout << dp[5][S] << endl; return 0; }