Yukicoder No.398 ハーフパイプ(2)
タグ: 動的計画法 埋め込み
ってどういうことなのか。
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;
}