ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

Kodamanと愉快な仲間たち S - 五等分の分銅

お題箱より。

Programming Problems and Competitions :: HackerRank

解法

分数のままでは考えにくいので、通分します。 1, 2, 3, 4, 5 の最大公約数は  60 なので、まず重りを全て  60 倍して  60, 30, 20, 15, 12 とします。そして目標の重さも  S = \frac{60p}{q} に置き換えます。するとこの問題は「重さ  60, 30, 20, 15, 12 の重りをそれぞれ  a, b, c, d, e 個以下使って合計  S を作る場合の数を求めよ」という問題と見なせます。もし  S が整数にならない場合は0通りです。

これは「部分和問題」と呼ばれるもので、特に今回は

  • 個数制限付き:各要素が何個まで使えるか指定されている
  • 数え上げ: S が作れるかどうかの判定だけでなく、その作り方の場合の数を求める必要がある

という特徴があります。

これを公式解説のDPで解きます。以下のようなDPテーブルを定義します。

  •  dp\lbrack i \rbrack\lbrack s\rbrack = 重り  i までの使い方を決めて、その合計が  s であるような重りの使い方の場合の数

この遷移ですが…具体例で説明しましょう。重り  i の重さが  60 で、これが  2 個まで使えるとします。このときの  i-1 から  i からの更新方法を考えます。

更新の順番として、 \bmod 60 ごとに更新をしていくという方法を取ります。つまり

  •  dp\lbrack i \rbrack\lbrack 0 \rbrack, dp\lbrack i \rbrack\lbrack 60 \rbrack, dp\lbrack i \rbrack\lbrack 120 \rbrack, ... をこの順に更新する。
  •  dp\lbrack i \rbrack\lbrack 1 \rbrack, dp\lbrack i \rbrack\lbrack 61 \rbrack, dp\lbrack i \rbrack\lbrack 121 \rbrack, ... をこの順に更新する。
  •  dp\lbrack i \rbrack\lbrack 59 \rbrack, dp\lbrack i \rbrack\lbrack 119 \rbrack, dp\lbrack i \rbrack\lbrack 179 \rbrack, ... をこの順に更新する。

という流れです。

いま重さ  60 の重りを  2 個まで使える場合を考えているので、 dp\lbrack i \rbrack\lbrack s \rbrack に遷移できるのは  dp\lbrack i-1 \rbrack\lbrack s \rbrack, dp\lbrack i-1 \rbrack\lbrack s-60 \rbrack, dp\lbrack i-1 \rbrack\lbrack s-120 \rbrack の3点からです。例えば  0, 60, 120, ... を更新する時には、以下の図のような遷移になります。

f:id:betrue12:20191006152757p:plain

つまり遷移元が一定の長さを保ったままスライドしていくので、例えば  dp\lbrack i \rbrack\lbrack 180 \rbrack の遷移元と  dp\lbrack i \rbrack\lbrack 240 \rbrack の遷移元の違いは両端だけです。このように範囲に入るものと出るものを差分更新することで、遷移元の値を効率的に管理することが出来ます。(解説の「しゃく取り法っぽく」はこれを指しています)

このようにすれば重り1種類についての遷移の計算量は  O(S) です。 \bmod で分類しているだけで結局は遷移先の  0, ..., S を1回ずつ見ていることになり、遷移元の計算は差分更新で毎回  O(1) でできているからです。重りの種類数を  N=5 とあえて明示すると、全体計算量は  O(NS) になります。  S = \frac{60p}{q} は制約より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;
}