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;
}