Bondo416さんのマイナビプログラミングコンテスト2021(AtCoder Beginner Contest 201)での成績:1532位
— ボンド@競プロ (@bond_cmprog) May 15, 2021
パフォーマンス:1262相当
レーティング:1523→1500 (-23) :(#AtCoder #マイナビプログラミングコンテスト2021(ABC201) https://t.co/4PFSgetU4C
A - Tiny Arithmetic Sequence
next_permutationで全探索した
よく考えるとソートをして条件を満たしているか確認すればいい
提出コード
void solve(){ vector<int> A(3); REP(i,3) cin >> A[i]; sort(A.begin(), A.end()); do{ if(A[2] - A[1] == A[1] - A[0]){ cout << "Yes" << endl; return; } }while(next_permutation(A.begin(), A.end())); cout << "No" << endl; }
B - Do you know the second highest mountain?
高さで降順ソートをし、2番目の高さになる元のインデックスの山の名前を答えればいい
提出コード
void solve(){ int N; cin >> N; vector<string> S(N); vector<int> T(N); REP(i,N) cin >> S[i] >> T[i]; vector<int> idx(N); iota(idx.begin(), idx.end(), 0); sort(idx.begin(), idx.end(), [&](int a, int b){ return T[a] > T[b]; }); cout << S[idx[1]] << endl; }
C - Secret Number
長さが4桁の文字列なので全探索をする
4つの数字のいずれかがx
なら条件を満たさない
また、選んだ数字以外にo
になっている数字があればそれも条件を満たさない
それ以外であれば条件を満たしているのでこれを数える
提出コード
void solve(){ string S; cin >> S; int cnt = 0; REP(i,10) REP(j,10) REP(k,10) REP(l,10){ if(S[i] == 'x') continue; if(S[j] == 'x') continue; if(S[k] == 'x') continue; if(S[l] == 'x') continue; bool ok = true; REP(m,10) if(m != i and m != j and m != k and m != l){ if(S[m] == 'o') ok = false; } if(ok) cnt++; } cout << cnt << endl; }
D - Game in Momotetsu World
高橋くんの得点を $ sum_t $ 、青木くんの得点を $ sum_a $ とする
高橋くんの立場で考えると、$ sum_t - sum_a $ を最大化したく、青木くんはこれを最小化したい
よって、今いるマスの手番が高橋くんなら上記を最大化するように、青木くんなら上記を最小化するようにDPで求めればいい
提出コード
void solve(){ int H, W; cin >> H >> W; vector<string> fi(H); REP(i,H) cin >> fi[i]; vector<vector<int>> A(H, vector<int>(W)); REP(i,H) REP(j,W){ if(fi[i][j] == '+') A[i][j] = 1; else A[i][j] = -1; } vector dp(H, vector(W, 0)); vector used(H, vector(W, 0)); auto memo = [&](auto && self, int h, int w) -> int{ if(h == H - 1 and w == W - 1) return dp[h][w] = 0; if(used[h][w]) return dp[h][w]; used[h][w] = 1; if((h + w) % 2 == 0){ int res = -INF; if(h + 1 < H) chmax(res, self(self, h+1, w) + A[h+1][w]); if(w + 1 < W) chmax(res, self(self, h, w+1) + A[h][w+1]); return dp[h][w] = res; } else{ int res = INF; if(h + 1 < H) chmin(res, self(self, h+1, w) - A[h+1][w]); if(w + 1 < W) chmin(res, self(self, h, w+1) - A[h][w+1]); return dp[h][w] = res; } }; memo(memo, 0, 0); if(dp[0][0] == 0) cout << "Draw" << endl; else if(dp[0][0] > 0) cout << "Takahashi" << endl; else cout << "Aoki" << endl; }
E - Xor Distances
ある頂点を適当に根とした木を考える
根 $ x $ から他の頂点 $ i $ への距離を $ dist_{x, i} $ とする
ある二頂点 $ (i, j) $ のパスの距離は最小共通祖先を考えると $ dist_{i, j} = dist_{x,i} \oplus dist_{x,j} $ と表せる
よって $ 1 \leq i \lt j \leq N $ を満たすパスの総和を求めればいい
これはbitの各桁ごとに見るといい
$ dist_{x, i} $ の $ k $ 番目のbitが立っているものの個数を $ cnt_1 $、立っていないものの個数を $ cnt_0 $ とすると、$ 2^{k - 1} \times cnt_0 \times cnt_1 $ が総和に寄与する
これを各桁ごとに求めた総和が答え
提出コード
void solve(){ int N; cin >> N; vector<vector<pair<int, ll>>> g(N); REP(i,N-1){ ll u, v, w; cin >> u >> v >> w; --u, --v; g[u].emplace_back(v, w); g[v].emplace_back(u, w); } vector dist(N, 0LL); auto dfs = [&](auto && self, int cur, int par=-1, ll sum=0) -> void{ dist[cur] = sum; for(auto [nv, w] : g[cur]){ if(nv == par) continue; self(self, nv, cur, sum^w); } }; dfs(dfs, 0, -1); mint ans = 0; REP(i,60){ vector<mint> cnt(2, 0); REP(j,N) cnt[dist[j]>>i&1] += 1; ans += cnt[0] * cnt[1] * (1LL << i); } cout << ans << endl; }