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