Bondo416さんのトヨタ自動車プログラミングコンテスト2024#4（AtCoder Beginner Contest 348）での成績：565位
— ボンド@競プロ (@bond_cmprog) 2024年4月6日
パフォーマンス：1819相当
レーティング：1525→1558 (+33) :)#AtCoder #トヨタ自動車プログラミングコンテスト2024#4（ABC348） https://t.co/7CnnlaWZwf
A - Penalty Kick
$ N $ 個の o 文字列を作り、3の倍数番目を x にする
void solve() { int N; cin >> N; string ans = string(N, 'o'); REP(i, N) if ((i + 1) % 3 == 0) ans[i] = 'x'; cout << ans << endl; }
B - Farthest Point
全探索で各頂点からの距離が最大の頂点を求める
void solve() { int N; cin >> N; vector<ll> X(N), Y(N); REP(i, N) cin >> X[i] >> Y[i]; REP(i, N) { ll ma = 0; int idx = i; REP(j, N) { if (chmax(ma, (X[i] - X[j]) * (X[i] - X[j]) + (Y[i] - Y[j]) * (Y[i] - Y[j]))) { idx = j; } } cout << idx + 1 << endl; } }
C - Divide and Divide
mapなどで各 $ C_i $ の最小値を持っておき、その中の最大を出力する
void solve() { int N; cin >> N; vector<int> A(N), C(N); map<int, int> mp; REP(i, N) { cin >> A[i] >> C[i]; if (mp.contains(C[i])) chmin(mp[C[i]], A[i]); else mp[C[i]] = A[i]; } int ma = 0; for (auto [c, a] : mp) { chmax(ma, a); } cout << ma << endl; }
D - String Bags
2回ワーシャルフロイドをする
薬のある$ N $ 間の最短距離を$ N $ 回BFSをした後にワーシャルフロイドで求める
その後、頂点 $ i $ から頂点 $ j $ まで薬 $ i $ のみを使って移動できる（$ dist[i][j] \leq E_i $） グラフを作り、そのグラフ上でワーシャルフロイドを行いゴールにたどり着けるかどうかを判定する
スタート/ゴールがない場合は予め $ E_k = 0 $ の頂点を追加しておく
void solve() { int H, W; cin >> H >> W; vector<string> A(H); REP(i, H) cin >> A[i]; int sh = 0; int sw = 0; int th = 0; int tw = 0; REP(i, H) REP(j, W) { if (A[i][j] == 'S') { sh = i; sw = j; } else if (A[i][j] == 'T') { th = i; tw = j; } } int N; cin >> N; vector<int> R(N), C(N), E(N); int s = -1, t = -1; REP(i, N) { cin >> R[i] >> C[i] >> E[i]; R[i]--, C[i]--; if (R[i] == sh && C[i] == sw) s = i; if (R[i] == th && C[i] == tw) t = i; } if (s == -1) { R.push_back(sh); C.push_back(sw); E.push_back(0); s = N; N++; } if (t == -1) { R.push_back(th); C.push_back(tw); E.push_back(0); t = N; N++; } vector<vector<int>> dist(N, vector<int>(N)); REP(i, N) { vector<vector<int>> d(H, vector<int>(W, INF)); d[R[i]][C[i]] = 0; queue<P> q; q.push(P(R[i], C[i])); while (!q.empty()) { auto [r, c] = q.front(); q.pop(); REP(j, 4) { int nr = r + dx[j], nc = c + dy[j]; if (nr < 0 || nr >= H || nc < 0 || nc >= W || A[nr][nc] == '#') continue; if (d[nr][nc] > d[r][c] + 1) { d[nr][nc] = d[r][c] + 1; q.push(P(nr, nc)); } } } REP(j, N) dist[i][j] = d[R[j]][C[j]]; } REP(k, N) REP(i, N) REP(j, N) chmin(dist[i][j], dist[i][k] + dist[k][j]); vector<vector<int>> hokyu(N, vector<int>(N, INF)); REP(i, N) hokyu[i][i] = 0; REP(i, N) REP(j, N) { if (i == j) continue; if (dist[i][j] <= E[i]) chmin(hokyu[i][j], 1); } REP(k, N) REP(i, N) REP(j, N) chmin(hokyu[i][j], hokyu[i][k] + hokyu[k][j]); cout << (hokyu[s][t] == INF ? "No" : "Yes") << endl; }
E - Minimize Sum of Distances
ABC220Fと同じ要領でやる
部分木のサイズの代わりに部分木の $ C_i $ の総和を$ sz $ としてdfsで求めておく
根を $ v $ から $ nv $ に移動させたときの変化量は $ sz_{nv} $ だけ減り、$ \sum _i C_i - sz_{nv} $ だけ増えるのでこれをdfsで求めれば良い
void solve() { int N; cin >> N; vector<vector<int>> G(N); vector<int> u(N - 1), v(N - 1); REP(i, N - 1) { cin >> u[i] >> v[i]; G[--u[i]].emplace_back(--v[i]); G[v[i]].emplace_back(u[i]); } vector<ll> C(N); vector<ll> sz(N, 1); REP(i, N) { cin >> C[i]; sz[i] = C[i]; } ll sum = accumulate(C.begin(), C.end(), 0LL); vector<ll> ans(N); auto dfs1 = [&](auto &&self, int v, int par = -1) -> void { for (auto nv : G[v]) { if (nv == par) continue; self(self, nv, v); sz[v] += sz[nv]; ans[v] += ans[nv] + sz[nv]; } }; auto dfs2 = [&](auto &&self, int v, int par = -1) -> void { for (auto nv : G[v]) { if (nv == par) continue; ans[nv] = ans[v] - sz[nv] + sum - sz[nv]; self(self, nv, v); } }; dfs1(dfs1, 0); dfs2(dfs2, 0); cout << *min_element(ans.begin(), ans.end()) << endl; }
