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);
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";
}
}
(問題文はちゃんと読もうな重要な制約が書いてある可能性があるから+もっと再帰的に考えような)ですね…。
