https://beta.atcoder.jp/contests/arc101
本番解けないと意味ないってそれ一番。
コンテスト中は1完です…
C
K個の連続した区間になるので適切に計算すればO(N)。
D
本番誤読してかなしぃ。中央値はやっぱりにぶたんなんだよなぁ。
https://agc006.contest.atcoder.jp/tasks/agc006_d
これっぽいですね。
ll N; ll A[MAX_N]; int S[MAX_N]; pi P[MAX_N]; bool ok(ll m) { rep(i, 0, N) { if(A[i] <= m) S[i + 1] = 1; else S[i + 1] = -1; } // debug(m, vi(S + 1, S + N + 1)); rep(i, 0, N) { S[i + 1] += S[i]; } rep(i, 0, N + 1) { P[i] = pi(S[i], -i); } sort(P, P + N + 1); ll res = 0; BIT bit(N + 1); rep(i, 0, N + 1) { int at = P[i].sec * -1; bit.update(at, at + 1, 1); res += bit.get(0, at); } return res > N * (N + 1) / 4; } void solve() { cin >> N; rep(i, 0, N) cin >> A[i]; ll lv = 0, rv = inf; while(rv - lv > 1) { ll m = (lv + rv) / 2; if(ok(m)) rv = m; else lv = m; } cout << rv << "\n"; }
E
dp[v][a]:=根がvの木で余ってる辺がk本の時とすると、
dp[v][a+b-2k]:=dp[c1][a]*dp[c2][b]*C(a,k)*C(b,k)とかになって、なんとかまとめればできそうな形になりますが全然できません。本番もこれでめちゃくちゃハマりました。
なのでこの考えから離れましょう。包除を思いつけるとあとはそんな難しくないです。
木dpの書き方も忘れてたのでよい練習になりました。
int N; vector<int> G[MAX_N]; ll dp[5010][5010][2]; ll ep[5010][5010][2]; ll pow2inv[5010]; int loop(int v, int p) { int sz = 1; dp[v][1][0] = 1; rep(q, 0, sz(G[v])) { int n = G[v][q]; if(p == n) continue; int ts = loop(n, v); rep(i, 0, sz + ts + 1) { rep(j, 0, 2) { ep[v][i][j] = 0; } } rep(i, 0, sz + 1) { rep(j, 0, ts + 1) { rep(k, 0, 2) { rep(l, 0, 2) { ADD(ep[v][i + j][(k + l) % 2], dp[v][i][k] * dp[n][j][l] % mod); } } } } rep(i, 0, sz + ts + 1) { rep(j, 0, 2) { dp[v][i][j] = ep[v][i][j]; } } sz += ts; } for(int i = 0; i <= sz; i += 2) { rep(j, 0, 2) { ADD(dp[v][0][(j + 1) % 2], dp[v][i][j] * fac[i] % mod * pow2inv[i / 2] % mod * fiv[i / 2] % mod); } } return sz; } void solve() { cin >> N; C_init(N); rep(i, 0, N - 1) { int a, b; cin >> a >> b; a--; b--; G[a].pb(b); G[b].pb(a); } pow2inv[0] = 1; rep(i, 0, N) { pow2inv[i + 1] = pow2inv[i] * inv[2] % mod; } loop(0, -1); cout << (dp[0][0][1] - dp[0][0][0] + mod) % mod << "\n"; }
F
解説とだいぶ違った。
ロボットの出口との距離を(a,b)とします。座標の点をグラフにして、0から正の方向負の方向に辺を張ります。
それから(a->b)または(b->a)の辺を張ってグラフ全体がトポロジカルソートができることが条件になります。
トポロジカルソートができる<=>ループが存在しない<=>(a,b)(c,d)の組であってa<=c,b<=dを満たし、a->b,d->cに辺を張るものが存在しない
と言い換えられます。ここまでくればあとはBITで数え上げられます。
でも解説の2次元座標の言い換えができたほうが絶対良かったよなぁ。
int N, M; ll X[MAX_N], Y[MAX_N]; ll L[MAX_N], R[MAX_N]; vl vec; vl Q[MAX_N]; int fd(ll v) { return lower_bound(all(vec), v) - vec.begin(); } void solve() { cin >> N >> M; rep(i, 0, N) cin >> X[i + 1]; rep(i, 0, M) cin >> Y[i + 1]; X[0] = -linf; Y[M + 1] = linf; int at = 1; rep(i, 0, N) { while(X[i + 1] > Y[at]) at++; if(at != M + 1) R[i] = Y[at] - X[i + 1]; else R[i] = linf; vec.pb(R[i]); } at = M; rer(i, N, 0) { while(X[i + 1] < Y[at]) at--; if(at != 0) L[i] = X[i + 1] - Y[at]; else L[i] = linf; vec.pb(L[i]); } vec.pb(linf); sort(all(vec)); // debug(vl(L, L + N)); // debug(vl(R, R + N)); vec.erase(unique(all(vec)), vec.end()); rep(i, 0, N) { int lat = fd(L[i]), rat = fd(R[i]); Q[lat].pb(rat); } rep(i, 0, sz(vec)) { sort(all(Q[i])); Q[i].erase(unique(all(Q[i])), Q[i].end()); } BIT bit(sz(vec)); bit.update(sz(vec) - 1, sz(vec), 1); rer(i, sz(vec) - 1, 0) { rep(j, 0, sz(Q[i])) { int b = Q[i][j]; ll v = bit.get(b + 1, sz(vec)); // debug(vec[i], vec[b], v); bit.update(b, b + 1, v); } } cout << bit.get(0, sz(vec)) << "\n"; }
