https://beta.atcoder.jp/contests/arc096
C.
Cを全通り試します。
ll A, B, C, X, Y; void solve() { cin >> A >> B >> C >> X >> Y; ll ans = linf; for(int c = 0; c <= max(X, Y) * 2; c += 2) { ll res = 0; res += C * c; res += A * max(X - c / 2, 0ll); res += B * max(Y - c / 2, 0ll); MIN(ans, res); } cout << ans << "\n"; }
D.
折り返す場所を全通り試します。
int N; ll C; ll X[MAX_N], V[MAX_N]; ll L1[MAX_N], L2[MAX_N], R1[MAX_N], R2[MAX_N]; void solve() { cin >> N >> C; rep(i, 0, N) { cin >> X[i] >> V[i]; } ll vs = 0, l1m = 0, l2m = 0; rep(i, 0, N) { vs += V[i]; MAX(l1m, vs - X[i]); MAX(l2m, vs - 2 * X[i]); L1[i + 1] = l1m; L2[i + 1] = l2m; } vs = 0; ll r1m = 0, r2m = 0; rer(i, N, 0) { vs += V[i]; MAX(r1m, vs - (C - X[i])); MAX(r2m, vs - 2 * (C - X[i])); R1[i] = r1m; R2[i] = r2m; } ll res = 0; rep(i, 0, N + 1) { MAX(res, L1[i] + R2[i]); MAX(res, L2[i] + R1[i]); } cout << res << "\n"; }
E.
うわー2byte差で落とすというね…。
包除原理します。
そして、dp[i][j]:=iケタ0or1にするときその中で1を含む数の個数がjの時の場合の数とします。
するとdp[i][j]は簡単な遷移で求められて、
あとはiケタ0or1にするときの場合の数は、
ΣC(N,i)*2^(2^(N-i))*2^((N-i)*j)*dp(i,j)となるのでO(N^2)で求められます。
しかし、注意すべきことはpow(2,pow(2,N-i,mod),mod)としないことです。正しくは
pow(2,pow(2,N-i,mod-1),mod)です。2^(p-1)=1だからですね。これさえ気づければ通っていた…。
ll dp[3010][3010]; void solve() { cin >> N >> mod; C_init(N + 10); dp[0][0] = 1; rep(i, 0, N) { rep(j, 0, N) { if(dp[i][j] == 0) continue; ADD(dp[i + 1][j + 1], dp[i][j]); ADD(dp[i + 1][j], dp[i][j] * (j + 1) % mod); } } ll ans = 0; rep(i, 0, N + 1) { ll dps = 0; ll pown = mod_pow(2, mod_pow(2, N - i, mod - 1), mod); ll pp = mod_pow(2, N - i, mod); ll d = 1; rep(j, 0, i + 1) { ll pows = pown * d % mod; MUL(d, pp); ADD(dps, dp[i][j] * pows % mod); } if(i % 2 == 0) { ADD(ans, (C(N, i) * dps % mod)); } else { ADD(ans, mod - (C(N, i) * dps % mod)); } } cout << ans << "\n"; }
mod-1の件があったにせよ、解法を詰めるのが遅すぎですね…場合の数の計算に自信が持てないのはなんとかしないと…。