https://beta.atcoder.jp/contests/arc102/tasks
C
K/2が肝とわかれば。
D
2^nの辺を張って、適当に付け加えれば良さそうと思って実際そうでした。添字がめんどい。
int L; vector<pi> G[20]; void solve() { cin >> L; int N = 1; while(L >= (1 << N)) N++; rep(i, 0, N - 1) { G[i].pb(pi(i + 1, (1 << (N - 2 - i)))); G[i].pb(pi(i + 1, 0)); } L -= (1 << (N - 1)); int now = (1 << (N - 1)); rer(i, N - 1, 0) { if(L & (1 << i)) { G[0].pb(pi(N - 1 - i, now)); now += (1 << i); } } int M = 0; rep(i, 0, N) { M += sz(G[i]); } cout << N << " " << M << "\n"; rep(i, 0, N) { rep(j, 0, sz(G[i])) { cout << i + 1 << " " << G[i][j].fst + 1 << " " << G[i][j].sec << "\n"; } } }
E
奇偶に分けてじっと見たら対称性があることに気づいたのでDPしました。でもよく考えると二項係数だけで行ける。
最初包除かなと思ったんですが、こんがらがってしまいました。
包除なんですが、f(集合)というよりは、f(条件)とすれば、
f(S1∨S2∨S3)=(f(S1)+f(S2)+f(S3))-(f(S1∧S2)+f(S2∧S3)+f(S3∧S1))+f(S1∧S2∧S3)
となってわかりやすくないですか?僕はわかりやすいです。
int K, N; ll ans[4040]; ll dp[4040][4040]; void solve() { cin >> K >> N; C_init(4040); dp[0][0] = 1; for(int i = 0; i <= K / 2; i++) { rep(j, 0, K + 1) { if(!dp[i][j]) continue; ADD(dp[i + 1][j + 1], dp[i][j] * 2 % mod); ADD(dp[i + 1][j], dp[i][j]); } } for(int i = 1; i <= K / 2 + 1; i++) { for(int j = 0; j <= N; j++) { if(!dp[i][j]) continue; int a = N - j; int b = K - (i * 2) + j; // debug(i * 2 + 1, j, a, b, dp[i][j] * C(a + b - 1, a)); ADD(ans[i * 2 + 1], dp[i][j] * C(a + b - 1, a) % mod); } } for(int i = 1; i <= K / 2 + 1; i++) { for(int j = 0; j <= N; j++) { if(!dp[i][j]) continue; int a = N - j; int b = K - ((i - 1) * 2 + 1) + j; // debug(i * 2, j, a, b); ADD(ans[i * 2], dp[i - 1][j] * C(a + b - 1, a) % mod); a = N - j - 1; b = K - ((i - 1) * 2 + 1) + j; // debug(i * 2, j, a, b); ADD(ans[i * 2], dp[i - 1][j] * C(a + b - 1, a) % mod); } } // rep(i, 0, 2 * K + 1) { // debug(i, ans[i]); // } for(int i = K + 1; i <= 2 * K; i++) { ans[i] = ans[2 * K + 2 - i]; } for(int i = 2; i <= K * 2; i++) { cout << ans[i] << "\n"; } }
F
pi-1 < pi < pi+1となればpiはこれ以降動けないのでpi=iが成立しないといけないことを中心に考察を進めました。
こういうのは適当にiterationを決めて実験をダラダラしてたら解けることはわかっていたので、時間かけたら解法が降ってきました。
でも速く解こうと思ったらやっぱり性質が他にないか確かめるべきですね。もし数が動き始めたら左右どちらかにしか移動しないことに気づいてなかったのは良くなかったです。問題たくさん解けばこういう性質にもう少し敏感になれるかなぁ。
int N; int A[MAX_N]; bool used[MAX_N]; void solve() { cin >> N; memset(A, -1, sizeof(A)); rep(i, 0, N) { cin >> A[i]; A[i]--; } int lv = -1, uv = -1; for(int i = 0; i < N; i++) { if(uv == -1) { if(A[i] != i) { uv = A[i]; lv = i; if((uv - lv) % 2) { cout << "No\n"; return; } } } else if((uv - i) % 2) { if(A[i] != i) { cout << "No\n"; return; } } else { if(A[i] > uv) { used[uv] = true; uv = A[i]; } else if(lv == A[i]) { used[lv] = true; while(used[lv]) lv += 2; } else { cout << "No\n"; return; } if(lv == uv) { lv = -1, uv = -1; } } } if(lv != -1) cout << "No\n"; else cout << "Yes\n"; }
re_shaさんすごい。めちゃくちゃかしこいですね…。