ARC101 - omochan's diary

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";
}