http://codeforces.com/contest/909/problem/E
全体的に問題文の把握に手間がかかっていますね…
A
はい。
B
親の顔より見た問題。一番重なっているところを累積和で求めます。
C
勘違いした…
D
削除は奈良市計算量チャンスです。
E
問題を理解するのに無限に時間を費やした。
トポロジカルソートして一番1の連続した区間が多いpathを求めます。
トポロジカルソートの実装を忘れたので戒めとしてコード貼ります。dfsしてreverseですよ。
int N, M; int A[MAX_N]; int dp[MAX_N]; bool used[MAX_N]; vi ord; vi G[MAX_N]; void dfs(int v) { used[v] = true; rep(i, 0, sz(G[v])) { int n = G[v][i]; if(!used[n]) dfs(n); } ord.pb(v); } void solve() { cin >> N >> M; rep(i, 0, N) { cin >> A[i]; if(A[i] == 1) dp[i] = 1; } rep(i, 0, M) { int a, b; cin >> a >> b; G[b].pb(a); } rep(i, 0, N) { if(!used[i]) dfs(i); } reverse(all(ord)); rep(i, 0, N) { int v = ord[i]; if(A[v] == 0) { rep(j, 0, sz(G[v])) { int n = G[v][j]; if(A[n] == 1) MAX(dp[n], dp[v] + 1); else MAX(dp[n], dp[v]); } } else { rep(j, 0, sz(G[v])) { int n = G[v][j]; MAX(dp[n], dp[v]); } } } int ans = 0; rep(i, 0, N) MAX(ans, dp[i]); cout << ans << "\n"; }
F
2番目は普通にできて、1番目は偶数の場合はできて、奇数の場合はできないことを証明しようとしてたんですができませんでした…。
さらに解説で4行くらいで済まされて悲しかった。ディレクリで終了です。
1番目は(2^n,2^n-1),(2^n+1,2^n-2)...みたいに並べて再帰的にやります。
2番目は(N<=5||N=2^k)の時できなくて、N=6,N=7は埋め込みます。
N>=8は奇数偶数で場合分けして、N=6とN=7の結果を利用します。
int N; int ans[MAX_N]; void loop_sub1(int n) { if(n == 0) return; int pow2 = 1; while(pow2 * 2 <= n) pow2 *= 2; rep(i, 0, n - pow2 + 1) { int a = pow2 + i, b = pow2 - i - 1; ans[a] = b; ans[b] = a; } loop_sub1(pow2 * 2 - n - 2); } void ans_show() { cout << "YES\n"; rep(i, 1, N) { cout << ans[i] << " "; } cout << ans[N] << "\n"; } void sub1() { if(N % 2 == 1) cout << "NO\n"; else { loop_sub1(N); ans_show(); } } void sub2_6() { ans[1] = 3; ans[3] = 1; ans[2] = 6; ans[6] = 2; ans[4] = 5; ans[5] = 4; } void sub2_7() { ans[1] = 3; ans[3] = 7; ans[7] = 1; ans[2] = 6; ans[6] = 2; ans[4] = 5; ans[5] = 4; } void sub2() { if(N <= 5) { cout << "NO\n"; } else if(N == 6) { sub2_6(); ans_show(); } else if(N == 7) { sub2_7(); ans_show(); } else { int pow2 = 8; while(pow2 * 2 <= N) pow2 *= 2; if(N - pow2 == 0) cout << "NO\n"; else if((N - pow2) % 2 == 1) { sub2_7(); for(int i = 8; i < N; i += 2) { ans[i] = i + 1; ans[i + 1] = i; } ans_show(); } else { sub2_6(); for(int i = 8; i <= pow2; i += 2) { ans[i] = i + 1; ans[i + 1] = i; } ans[7] = pow2 + 1; ans[pow2 + 1] = 7; ans[pow2] = pow2 + 2; ans[pow2 + 2] = pow2; for(int i = pow2 + 3; i < N; i += 2) { ans[i] = i + 1; ans[i + 1] = i; } ans_show(); } } } void solve() { cin >> N; sub1(); sub2(); }
全部解けそうだったね。