Bondo416さんのAtCoder Beginner Contest 291(Sponsored by TOYOTA SYSTEMS)での成績:867位
— ボンド@競プロ (@bond_cmprog) February 26, 2023
パフォーマンス:1529相当
レーティング:1452→1460 (+8) :)#AtCoder #ABC291(SponsoredbyTOYOTASYSTEMS) https://t.co/bbtd5Iwks4
A - camel Case
大文字の判定を行う
void solve() { string S; cin >> S; REP(i, S.size()) { if ('A' <= S[i] and S[i] <= 'Z') { cout << i + 1 << endl; return; } } }
B - Trimmed Mean
ソートをして $ N \leq x \lt 4N $ の平均値を求める
void solve() { int N; cin >> N; vector<int> X(5 * N); REP(i, 5 * N) cin >> X[i]; sort(ALL(X)); int ans = 0; REP(i, N, 4 * N) ans += X[i]; printf("%.12lf\n", ans / (double)(3 * N)); }
C - LRUD Instructions 2
訪れた頂点をmapなどで持ちながらシミュレートを行い、すでに訪れたかどうかをチェックする
void solve() { int N; cin >> N; string S; cin >> S; map<pair<int, int>, int> mp; int cur_x = 0, cur_y = 0; mp[{cur_x, cur_y}] = 1; for (char c : S) { if (c == 'U') { cur_y++; } else if (c == 'D') { cur_y--; } else if (c == 'R') cur_x++; else if (c == 'L') cur_x--; if (mp.count({cur_x, cur_y})) { cout << "Yes" << endl; return; } mp[{cur_x, cur_y}] = 1; } cout << "No" << endl; }
D - Flip Cards
$ i $ 番目のものを決めるときには $ i - 1 $ 番目のものを表裏どちらの状態にしたかのみに依存するので以下のDPで求めればいい
$ dp[i][j] := i $ 番目のものまで見たとき、$ i - 1 $ 番目の状態が $ j $ のときの場合の数
void solve() { int N; cin >> N; vector<vector<int>> num(2, vector<int>(N)); REP(i, N) cin >> num[0][i] >> num[1][i]; vector dp(N + 1, vector<mint>(2, 0)); dp[0][0] = 1; dp[0][1] = 1; REP(i, 1, N) { REP(j, 2) { REP(k, 2) { if (num[j][i - 1] != num[k][i]) dp[i][k] += dp[i - 1][j]; } } } cout << dp[N - 1][0] + dp[N - 1][1] << endl; }
E - Find Permutation
与えられた条件を有向グラフとして考える
このグラフ上で長さが $ N - 1 $ のパスが存在すれば条件を満たすのでこれを判定する
void solve() { int N, M; cin >> N >> M; vector<int> X(M), Y(M); vector<vector<int>> g(N); REP(i, M) { cin >> X[i] >> Y[i]; --X[i], --Y[i]; g[X[i]].emplace_back(Y[i]); } auto res = topologicalSort(g); vector<int> dist(N, -1); dist[res[0]] = 0; for (auto x : res) { for (auto nv : g[x]) chmax(dist[nv], dist[x] + 1); } int ma = *max_element(ALL(dist)); dump(dist); if (ma != N - 1) cout << "No" << endl; else { cout << "Yes" << endl; vector<int> ans(N); REP(i, N) ans[res[i]] = i + 1; for (auto x : ans) cout << x << " "; cout << endl; } }
F - Teleporter and Closed off
頂点 $ i $ を使わずに移動可能かどうかは 頂点 $ i $ を飛び越すような辺が存在すればよい
そのような辺は制約より、 $ i $ の前後 $ M $ 個の頂点に絞られるのでこれをすべて調べれば良い
頂点 $ 1 $ からの最短距離を $ d_1 $ 、$ N $ からの最短経路を $ d_2 $ とし、頂点 $ j $ から $ k $ への辺が存在するとき、そのコストは $ d_{1,j} + d_{N, k} + 1 $ となるのでその最小を答えればいい
void solve() { int N, M; cin >> N >> M; vector<string> S(N); Dijkstra<int> d1(N, INF), d2(N, INF); REP(i, N) { cin >> S[i]; REP(j, M) if (S[i][j] == '1') { d1.make_edge(i, i + j + 1, 1); d2.make_edge(i + j + 1, i, 1); } } d1.solve(0); d2.solve(N - 1); dump(d1.cost); dump(d2.cost); REP(i, 1, N - 1) { int ans = INF; REP(j, max(0, i - (M - 1)), i) { REP(k, i + 1, min(N, i + 1 + (M - 1))) { if (k - j - 1 < M and S[j][k - j - 1] == '1') chmin(ans, d1.cost[j] + d2.cost[k] + 1); } } cout << (ans == INF ? -1 : ans) << " "; } cout << endl; }