Kodamanと愉快な仲間たち S - 五等分の分銅
お題箱より。
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; }