タグ: 動的計画法 埋め込みってどういうことなのか。

solution

$3$重loopを回すだけでよい。 $6$人の審査員の点数で$X$の制約に効いてくるのは中央の$4$つの点数だけなので、これらに関して全探索する。 点数の最大値$N = 100$審査員の数$K = 6$に対し$O(N^{K-3})$かな。

審査員らの点数を$a \le b \le c \le d \le e \le f$とする。 このとき$b, c, d, e$を固定する。 すると$a, f$の決めかたはざっくりと見て$b \times (100 - e)$通りぐらいな感じになる。これら$a, b, c, d, e, f$の点数を$6$人の審査員に割り振る方法は、$6!$から$a = b$のような重複部分を処理したものになる。これらを丁寧にやれば、$b, c, d, e$を固定したときの採点方法の数$f(b, c, d, e)$が求まる。

また、$X = \frac{b + c + d + e}{4}$という制約がある。これにより$4X - b - c - d = e$である。 よって、上の$f$を使って$\mathrm{ans} = \Sigma_{0 \le b \le 100} \Sigma_{b \le c \le 100} \Sigma_{c \le d \le 100} f(b, c, d, 4X - b - c - d)$として求まる。 これは$100^3$なので十分間に合う。

implementation

#include <cstdio>
#include <map>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
typedef long long ll;
using namespace std;
int fact(int n) {
    return n == 0 ? 1 : n * fact(n-1);
}
int perm(int a, int b, int c, int d, int e, int f) {
    map<int,int> g;
    g[a] += 1;
    g[b] += 1;
    g[c] += 1;
    g[d] += 1;
    g[e] += 1;
    g[f] += 1;
    int acc = 1;
    for (auto it : g) acc *= fact(it.second);
    return acc;
}
int main() {
    float x; scanf("%f", &x);
    int y = 4*x;
    ll ans = 0;
    repeat (b,100+1) {
        repeat_from (c,b,100+1) {
            repeat_from (d,c,100+1) {
                int e = y-b-c-d;
                if (e < d or 100 < e) continue;
                ans += fact(6) / perm(b,   b, c, d, e, e);
                ans += fact(6) / perm(b,   b, c, d, e, e+1)                   * max(0, 100-(e+1)+1);
                ans += fact(6) / perm(b-1, b, c, d, e, e+1) * max(0, (b-1)+1) * max(0, 100-(e+1)+1);
                ans += fact(6) / perm(b-1, b, c, d, e, e)   * max(0, (b-1)+1);
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}