https://arc103.contest.atcoder.jp/assignments
F Open- >それっぽい考察はできたけど、Dが同じ値を複数持つ時どうするんだ…- >問題文「Dの値は全て異なる」 - >実装完了。この時点で75分で、300+300+700勢に勝てなさそうなので撤退…
C
これ難しくないか?実装が意外にめんどくさい。
int N; pi P[2][100010]; int D[100010]; void solve() { cin >> N; rep(i, 0, N) cin >> D[i]; rep(i, 0, 2) { map<int, int> M; rep(j, 0, N / 2) { M[D[i + j * 2]]++; } int n = 0; for(auto p : M) { P[i][n++] = pi(-p.sec, p.fst); } } rep(i, 0, 2) sort(P[i], P[i] + N / 2); bool found = false; rep(i, 0, 2) { if(P[i][0].sec == P[i][1].sec) found = true; } if(found) { cout << N + P[0][0].fst + P[1][0].fst << "\n"; } else if(P[0][0].sec != P[1][0].sec) { cout << N + P[0][0].fst + P[1][0].fst << "\n"; } else { cout << min(N + P[0][0].fst + P[1][1].fst, N + P[0][1].fst + P[1][0].fst) << "\n"; } }
D
まず制約をちゃんと最後まで読みましょう。とりあえず、2のべき乗を並べるのはわかるとして、実験してみるのが重要でした。
再帰的にコードを書くのだから、前から実験するのは自然な発想だし、すぐできなかったのは反省。
解説では45度回転していますが、コンテスト中その発想にはなり得ないので、やはり実験が正解だったと思います。
int N; ll X[1010], Y[1010]; void solve() { cin >> N; rep(i, 0, N) cin >> X[i] >> Y[i]; bool odd = false, even = false; rep(i, 0, N) { if((X[i] + Y[i]) % 2) odd = true; else even = true; } if(odd && even) { cout << -1 << "\n"; return; } if(even) { rep(i, 0, N) { X[i]--; } } int M = 39; cout << (even ? M + 1 : M) << "\n"; for(int i = 0; i < M; i++) { cout << (1ll << (M - i - 1)) << " "; } if(even) cout << 1 << "\n"; else cout << "\n"; rep(i, 0, N) { string str; rer(j, M, 0) { ll d = (1ll << j); // debug(X[i], Y[i], d); if(X[i] + Y[i] >= 0 && Y[i] - X[i] >= 0) { str += 'U'; Y[i] -= d; } else if(X[i] + Y[i] >= 0 && Y[i] - X[i] <= 0) { str += 'R'; X[i] -= d; } else if(X[i] + Y[i] <= 0 && Y[i] - X[i] >= 0) { str += 'L'; X[i] += d; } else { str += 'D'; Y[i] += d; } } if(even) str += 'R'; cout << str << "\n"; } }
E
ごにょごにょすればできますね。
int N; string S; int A[MAX_N]; pi ans[MAX_N]; void solve() { cin >> S; N = sz(S); rep(i, 0, N) { A[i + 1] = (S[i] == '1'); } if(A[1] != 1) { cout << -1 << "\n"; return; } rep(i, 0, N + 1) { if(A[i] != A[N - i]) { cout << -1 << "\n"; return; } } ans[0] = pi(0, 1); int cur = 1; for(int i = 2; i < N; i++) { ans[i - 1] = pi(cur, i); if(i <= N / 2 && A[i] == 1) cur = i; } rep(i, 0, N - 1) { cout << ans[i].fst + 1 << " " << ans[i].sec + 1 << "\n"; } }
F
問題文はちゃんと読みましょう。葉から再帰するのはわかるとして、Dが異なる値であることが本質でした。すると、葉から順番に木の形が決まっていきます。最後重心が残るので、重心が正しい値になっているかチェックすればOK。
int N; vector<int> G[MAX_N]; pl D[MAX_N]; ll ts[MAX_N]; pi ans[MAX_N]; pl dist(int v, int p) { pl res(0, 1); rep(i, 0, sz(G[v])) { int n = G[v][i]; if(n == p) continue; pl tmp = dist(n, v); res.fst += tmp.fst + tmp.sec; res.sec += tmp.sec; } return res; } void solve() { cin >> N; rep(i, 0, N) { cin >> D[i].fst; D[i].fst *= -1; D[i].sec = i; } rep(i, 0, N) ts[i] = 1; sort(D, D + N); rep(i, 0, N - 1) { int at = lower_bound(D, D + N, pl(D[i].fst + (N - 2 * ts[i]), -inf)) - D; if(at == N || D[at].fst != D[i].fst + (N - 2 * ts[i]) || at <= i) { cout << "-1\n"; return; } ts[at] += ts[i]; ans[i] = pi(D[i].sec, D[at].sec); G[D[i].sec].pb(D[at].sec); G[D[at].sec].pb(D[i].sec); } if(dist(D[N - 1].sec, -1).fst != -D[N - 1].fst) { cout << "-1\n"; return; } rep(i, 0, N - 1) { cout << ans[i].fst + 1 << " " << ans[i].sec + 1 << "\n"; } }