Bondo416さんのユニークビジョンプログラミングコンテスト2023 秋 (AtCoder Beginner Contest 323)での成績：431位
— ボンド@競プロ (@bond_cmprog) October 7, 2023
パフォーマンス：1939相当
レーティング：1482→1537 (+55) :)#AtCoder #ユニークビジョンプログラミングコンテスト2023秋(ABC323) https://t.co/9CkpecfDiN
A - Weak Beats
for文で偶数番目のbitを調べる
void solve() { string S; cin >> S; bool even = true; for (int i = 1; i < (int)S.size(); i += 2) if (S[i] != '0') even = false; cout << (even ? "Yes" : "No") << endl; }
B - Round-Robin Tournament
勝ち数とインデックスをpair型で持ちソートをする
void solve() { int N; cin >> N; vector<string> S(N); vector<int> cnt(N); REP(i, N) { cin >> S[i]; for (char c : S[i]) if (c == 'o') cnt[i]++; } vector<pair<int, int>> vp; REP(i, N) vp.emplace_back(cnt[i], -i); stable_sort(ALL(vp), greater<pair<int, int>>()); for (auto [_, i] : vp) cout << -i + 1 << " "; cout << endl; }
C - World Tour Finals
予め $ A $ を降順にソートしておき、その状態で各人のスコア計算をしておく
各人のスコアをmultisetなどで持っておき、自分のスコアを削除した状態でまだ解いていない $ A_i $ を順に加算し、自分が最高のスコアになるかどうかをチェックする
void solve() { int N, M; cin >> N >> M; vector<int> A(M); REP(i, M) cin >> A[i]; vector<int> idx(M); iota(ALL(idx), 0); sort(ALL(idx), [&](int i, int j) { return A[i] > A[j]; }); vector<string> S(N); REP(i, N) cin >> S[i]; multiset<int> mst; REP(i, N) { int score = i + 1; REP(j, M) { if (S[i][j] == 'o') { score += A[j]; } } mst.insert(score); } REP(i, N) { int score = i + 1; REP(j, M) { if (S[i][j] == 'o') { score += A[j]; } } mst.erase(mst.find(score)); if (*mst.rbegin() < score) { cout << 0 << endl; } else { int nxt_score = score; int cnt = 0; REP(j, M) { if (S[i][idx[j]] == 'x') { nxt_score += A[idx[j]]; cnt++; } if (*mst.rbegin() < nxt_score) { break; } } cout << cnt << endl; } mst.insert(score); } }
D - Merge Slimes
一番小さいものは合成できるだけするのが良く、それを繰り返していけば良い
mapなどで各サイズのスライムが何匹いるかを管理し、最小のものから順に操作をしていけば良い
void solve() { int N; cin >> N; vector<ll> S(N), C(N); map<ll, ll> mp; set<ll> st; REP(i, N) { cin >> S[i] >> C[i]; mp[S[i]] += C[i]; st.insert(S[i]); } ll ans = 0; while (!st.empty()) { ll s = *st.begin(); ll c = mp[s]; ans += c % 2; st.erase(s); if (c / 2 > 0) { mp[2 * s] += c / 2; st.insert(2 * s); } } cout << ans << endl; }
E - Playlist
$ dp[i][j] := i $ 秒後に曲1が流れている $ (j = 0) $、曲1以外が流れている $ (j = 1) $ 確率としてDPをする
void solve() { int N, X; cin >> N >> X; vector<int> T(N); REP(i, N) cin >> T[i]; vector dp(X + 2, vector<mint>(2, 0)); dp[0][0] = 1; REP(i, X + 1) { dp[min(i + T[0], X + 1)][0] += dp[i][0] / N; dp[min(i + T[0], X + 1)][0] += dp[i][1] / N; REP(j, 1, N) { dp[min(i + T[j], X + 1)][1] += dp[i][0] / N; dp[min(i + T[j], X + 1)][1] += dp[i][1] / N; } } cout << dp[X + 1][0] << endl; }
F - Push and Carry
箱を上下方向から先に押すか、左右方向から先に押すかを全探索する
最初に箱の上下左右に移動する必要があるが、箱を避けて通る必要があるので予め箱からマンハッタン距離が $ 2 $ の距離に移動して、箱の上下左右に移動することを全探索する
箱の上下左右へ移動する距離はBFSなどで箱を中心とした $ 5 \times 5 $ 程度のグリッド上で求めれば良い
上記で求めた答えのうち最小のものを出力すれば良い
void solve() { ll XA, YA, XB, YB, XC, YC; cin >> XA >> YA >> XB >> YB >> XC >> YC; ll ans = LINF; for (int i = -2; i <= 2; i++) { for (int j = -2; j <= 2; j++) { if (abs(i) + abs(j) != 2) continue; vector<string> s(5, string(5, '.')); s[2][2] = 'x'; auto bfs = [&](int h, int w) { vector<vector<int>> dist(5, vector<int>(5, INF)); queue<P> q; q.push({h, w}); dist[h][w] = 0; while (!q.empty()) { auto [cur_h, cur_w] = q.front(); q.pop(); REP(k, 4) { int nh = cur_h + dy[k], nw = cur_w + dx[k]; if (nh < 0 || nh >= 5 || nw < 0 || nw >= 5) continue; if (s[nh][nw] == 'x') continue; if (dist[nh][nw] <= dist[cur_h][cur_w] + 1) continue; dist[nh][nw] = dist[cur_h][cur_w] + 1; q.push({nh, nw}); } } return dist; }; auto dist = bfs(2 + i, 2 + j); // 上から下 if (YB + i > YB and YB > YC) { ll tmp = abs(XA - (XB + j)) + abs(YA - (YB + i)); tmp += dist[3][2]; tmp += abs(YB - YC); if (XB == XC) chmin(ans, tmp); else { tmp += 2; tmp += abs(XC - XB); chmin(ans, tmp); } } // 下から上 else if (YB + i < YB and YB < YC) { ll tmp = abs(XA - (XB + j)) + abs(YA - (YB + i)); tmp += dist[1][2]; tmp += abs(YB - YC); dumps(tmp, i, j); if (XB == XC) chmin(ans, tmp); else { tmp += 2; tmp += abs(XC - XB); chmin(ans, tmp); } } // 左から右 if (XB + j < XB and XB < XC) { ll tmp = abs(XA - (XB + j)) + abs(YA - (YB + i)); tmp += dist[2][1]; tmp += abs(XB - XC); if (YB == YC) chmin(ans, tmp); else { tmp += 2; tmp += abs(YC - YB); chmin(ans, tmp); } } // 右から左 else if (XB + j > XB and XB > XC) { ll tmp = abs(XA - (XB + j)) + abs(YA - (YB + i)); tmp += dist[2][3]; tmp += abs(XB - XC); if (YB == YC) chmin(ans, tmp); else { tmp += 2; tmp += abs(YC - YB); chmin(ans, tmp); } } } } cout << ans << endl; }
