ARC088

https://beta.atcoder.jp/contests/arc088

C
A*2^n<=B

D
結構詰まった人もいるっぽい。端は好き勝手変えられるので真ん中だけ考えればいいです。

AtCoder Regular Contest 080F: Prime Flip - omochan's diary

のように区間→2点更新の問題に言い換えられますが、今回はそれをすると逆に辛い問題に帰着されます。悲しい。

E
なんだこれはたまげたなぁ…

POJ 1854: Evil Straw Warts Live - omochan's diary

F
これも解いたことあるし、でもコンテスト中勘違いして解けなかった…Eまで解いて満足してしまった感がある。
あとこういう削除が絡む操作はsetでやっちゃいましょう。

CF434D: Wizard's Tour - omochan's diary

int N;
int in[MAX_N];
vi G[MAX_N];
int dp[MAX_N];
int M;

void dfs(int v, int p) {
	multiset<int> S;
	rep(i, 0, sz(G[v])) {
		int n = G[v][i];
		if(n == p) continue;
		dfs(n, v);
		if(dp[n] != -1) S.insert(-(dp[n] + 1));
	}
	if(in[v] % 2) S.insert(0);
	while(!S.empty()) {
		int t = -(*S.begin());
		S.erase(S.begin());
		auto b = S.lower_bound(-(M - t));
		if(b != S.end()) {
			S.erase(b);
		}
		else {
			if(dp[v] == -1) dp[v] = t;
			else dp[v] = M + 1;
		}
	}
}

bool ok(int m) {
	M = m;
	memset(dp, -1, sizeof(dp));
	dfs(0, -1);
	if(dp[0] == -1) return true;
	else return false;
}

void solve() {
	cin >> N;
	rep(i, 0, N - 1) {
		int a, b;
		cin >> a >> b; a--; b--;
		G[a].pb(b);
		G[b].pb(a);
		in[a]++; in[b]++;
	}
	int A = 0;
	rep(i, 0, N) {
		A += in[i] % 2;
	}
	int lv = 0, rv = N;
	while(rv - lv > 1) {
		int m = (lv + rv) / 2;
		if(ok(m)) rv = m;
		else lv = m;
	}
	cout << A / 2 << " " << rv << "\n";
}