A - Seats
#.# の数を数える
void solve() { int N; string S; cin >> N >> S; int ans = 0; REP(i, 1, N - 1) { if (S[i - 1] == '#' and S[i] == '.' and S[i + 1] == '#') ans++; } cout << ans << endl; }
B - Traveling Takahashi Problem
距離を順に足していく
void solve() { int N; cin >> N; ll x = 0, y = 0; double ans = 0; REP(N) { ll a, b; cin >> a >> b; ans += hypot(x - a, y - b); x = a, y = b; } ans += hypot(x, y); cout << fixed << setprecision(10) << ans << endl; }
C - Spiral Rotation
各点ごとに何回操作されるかが決まり、各操作は $ \pmod{4} $ でどこに移動するか求められるので各点ごとにどこに移動するかが定まる
void solve() { int N; cin >> N; vector<string> A(N); REP(i, N) cin >> A[i]; vector B = A; REP(x, N) { REP(y, N) { int cnt = (min({x, N - x - 1, y, N - y - 1}) + 1) % 4; int nx = x, ny = y; REP(k, cnt) { int tmp = nx; nx = ny; ny = N - 1 - tmp; } dump(x, y, nx, ny, cnt); B[nx][ny] = A[x][y]; } } REP(i, N) cout << B[i] << endl; }
D - ABA
中心を固定して考える
このとき、回文になる個数は中心から左右にある同じ文字の選び方の総和になる
そのため、中心から左右の文字ごとの個数を管理し、各文字ごとに選び方の総和を加算していく
void solve() { string S; cin >> S; vector<ll> l_cnt(26, 0), r_cnt(26, 0); REP(S.size()) r_cnt[S[i] - 'A']++; ll ans = 0; int N = S.size(); r_cnt[S[0] - 'A']--; l_cnt[S[0] - 'A']++; REP(i, 1, N - 1) { r_cnt[S[i] - 'A']--; ll cnt = 0; REP(j, 26) { if (l_cnt[j] > 0 && r_cnt[j] > 0) ans += l_cnt[j] * r_cnt[j]; } l_cnt[S[i] - 'A']++; } cout << ans << endl; }
E - 3 Team Division
$ dp[i][j][k] := i $ 番目まで見たときに、チーム2の総和が $ j $ 、チーム3の総和が $ k $ となるように必要な操作回数の最小としてDPをする
void solve() { int N; cin >> N; vector<int> A(N), B(N); REP(i, N) { cin >> A[i] >> B[i]; } int sum = accumulate(ALL(B), 0); if (sum % 3) { cout << -1 << endl; return; } vector dp(501, vector<int>(501, INF)); dp[0][0] = 0; REP(i, N) { vector ndp(501, vector<int>(501, INF)); REP(j, 501) { REP(k, 501) { if (dp[j][k] == INF) continue; // チーム1から移動 if (A[i] == 1) { chmin(ndp[j][k], dp[j][k]); if (j + B[i] < 501) chmin(ndp[j + B[i]][k], dp[j][k] + 1); if (k + B[i] < 501) chmin(ndp[j][k + B[i]], dp[j][k] + 1); } // チーム2から移動 if (A[i] == 2) { chmin(ndp[j][k], dp[j][k] + 1); if (j + B[i] < 501) chmin(ndp[j + B[i]][k], dp[j][k]); if (k + B[i] < 501) chmin(ndp[j][k + B[i]], dp[j][k] + 1); } // チーム3から移動 if (A[i] == 3) { chmin(ndp[j][k], dp[j][k] + 1); if (j + B[i] < 501) chmin(ndp[j + B[i]][k], dp[j][k] + 1); if (k + B[i] < 501) chmin(ndp[j][k + B[i]], dp[j][k]); } } } swap(dp, ndp); } cout << (dp[sum / 3][sum / 3] == INF ? -1 : dp[sum / 3][sum / 3]) << endl; }
F - Road Blocked
クエリを逆から見て、辺の削除を辺の追加クエリとして考える
あらかじめワーシャルフロイドで全点間の最短距離を求めておく
このとき、辺を追加したときの更新クエリは $ O(N^2) $ で更新でき、また更新クエリが $ 300 $ 以下であるので全体で $ O(N^3) $ で更新クエリを行うことができる
void solve() { int N, M, Q; cin >> N >> M >> Q; vector<ll> A(M), B(M), C(M); REP(i, M) { cin >> A[i] >> B[i] >> C[i]; A[i]--, B[i]--; } using T = tuple<int, int, int>; vector<T> query(Q); set<int> removed_edge; REP(i, Q) { int x = -1, y = -1, z = -1; cin >> x; if (x == 1) cin >> y; else cin >> y >> z; query[i] = T(x, y - 1, z - 1); if (x == 1) removed_edge.insert(y - 1); } vector<vector<ll>> G(N, vector<ll>(N, LINF)); REP(i, M) { if (removed_edge.contains(i)) continue; G[A[i]][B[i]] = C[i]; G[B[i]][A[i]] = C[i]; } REP(i, N) { G[i][i] = 0; } REP(k, N) REP(i, N) REP(j, N) { if (G[i][k] == LINF or G[k][j] == LINF) continue; chmin(G[i][j], G[i][k] + G[k][j]); } vector<ll> ans; reverse(ALL(query)); for (auto [x, y, z] : query) { if (x == 1) { ll X = A[y], Y = B[y], Z = C[y]; chmin(G[X][Y], Z); chmin(G[Y][X], Z); REP(i, N) { REP(j, N) { if (i != j) { chmin(G[i][j], G[i][X] + G[Y][j] + Z); chmin(G[i][j], G[i][Y] + G[X][j] + Z); } } } } else { if (G[y][z] == LINF) ans.push_back(-1); else ans.push_back(G[y][z]); } } reverse(ALL(ans)); for (auto a : ans) cout << a << endl; }
