Bondo416さんのfreee プログラミングコンテスト2022（AtCoder Beginner Contest 264）での成績：1165位
— ボンド@競プロ (@bond_cmprog) August 13, 2022
パフォーマンス：1393相当
レーティング：1453→1447 (-6) :(#AtCoder #freeeプログラミングコンテスト2022（ABC264） https://t.co/9Rrn35b1fk
A - "atcoder".substr()
$ S_L $ から $ S_R $ までを出力
void solve(){ int L, R; cin >> L >> R; string S = "atcoder"; for (int i = L - 1; i <= R - 1;i++){ cout << S[i]; } cout << endl; }
B - Nice Grid
if文で全通り書く
void solve() { int R, C; cin >> R >> C; string ans = "white"; if (R == 1 or R == 15) { ans = "black"; } else if (R == 2 or R == 14) { if (C == 1 or C == 15) ans = "black"; } else if (R == 3 or R == 13) { if (C == 1 or C == 15) ans = "black"; if (3 <= C and C <= 13) ans = "black"; } else if (R == 4 or R == 12) { if (C == 1 or C == 3 or C == 13 or C == 15) ans = "black"; } else if (R == 5 or R == 11) { if (C == 1 or C == 3 or C == 13 or C == 15) ans = "black"; if (5 <= C and C <= 11) ans = "black"; } else if (R == 6 or R == 10) { if (C == 1 or C == 3 or C == 5 or C == 11 or C == 13 or C == 15) ans = "black"; } else if (R == 7 or R == 9) { if (C == 1 or C == 3 or C == 5 or C == 11 or C == 13 or C == 15) ans = "black"; if (7 <= C and C <= 9) ans = "black"; } else if (R == 8) { if (C == 1 or C == 3 or C == 5 or C == 7 or C == 9 or C == 11 or C == 13 or C == 15) ans = "black"; } cout << ans << endl; }
C - Matrix Reducing
どの列、行を残すかをそれぞれbit全探索を行い、一致させることができるかを判定
void solve() { int H1, W1, H2, W2; cin >> H1 >> W1; vector A(H1, vector(W1, 0)); REP(i, H1) REP(j, W1) cin >> A[i][j]; cin >> H2 >> W2; vector B(H2, vector(W2, 0)); REP(i, H2) REP(j, W2) cin >> B[i][j]; bool ok = false; REP(i, 1 << H1) { if (__builtin_popcount(i) != H2) continue; REP(j, 1 << W1) { if (__builtin_popcount(j) != W2) continue; vector<vector<int>> C(H2, vector<int>(W2, 0)); int ii = 0; REP(k, H1) if (i >> k & 1) { int jj = 0; REP(l, W1) if (j >> l & 1) { C[ii][jj] = A[k][l]; jj++; } ii++; } if (C == B) ok = true; } } cout << (ok ? "Yes" : "No") << endl; }
D - "redocta".swap(i,i+1)
隣接スワップの最小操作回数は転倒数になるため、文字列を数列とみなしてその転倒数を求める
ll inversionNumber(string &x, string &y){ // xをyにするために必要な隣接swapの回数（転倒数）を返す // 同じ値が含まれる場合、最小回数を返す int sz = x.size(); assert(sz == (int)y.size()); BIT<ll> bit(sz); // 座圧 map<char, vector<int>> idx; for(int i=sz-1;i>=0;i--){ idx[x[i]].emplace_back(i); } ll res = 0; for(int i=0;i<sz;i++){ vector<int> &v = idx[y[i]]; // xをyに出来ない時 -1 を返す if(v.empty()) return -1; int id = v.back(); v.pop_back(); res += id - bit.sum(id); bit.add(id+1, 1); } return res; } void solve(){ string S; cin >> S; string T = "atcoder"; cout << inversionNumber(S, T) << endl; }
E - Blackout 2
UnionFindを使って、クエリの逆順に答えを求めていく
都市 $ x $ が発電所とつながっているとき、$ contain[x] = true $ とし、$ (x, y) $ を uniteするとき、発電所と繋がっていない方の都市の数を答えに加算していく
struct UnionFind { vector<int> par; int _N; vector<int> sum; vector<bool> contain; ll ans; UnionFind(int n, int _N) : par(n, -1), sum(n, 0), contain(n, false), ans(0) { REP(i, _N){ sum[i] = 1; } REP(i, _N, n){ contain[i] = true; } } void init(int n) { par.assign(n, -1); } int root(int x) { if (par[x] < 0) return x; else return par[x] = root(par[x]); } bool issame(int x, int y) { return root(x) == root(y); } bool unite(int x, int y) { x = root(x); y = root(y); if (x == y) return false; if (par[x] > par[y]) swap(x, y); // merge technique if(contain[x] and contain[y]){} else if(contain[x]){ contain[y] = true; ans += sum[y]; } else if(contain[y]){ contain[x] = true; ans += sum[x]; } sum[x] += sum[y]; par[x] += par[y]; par[y] = x; return true; } int size(int x) { return -par[root(x)]; } }; void solve() { int N, M, E; cin >> N >> M >> E; vector<pair<int, int>> edge(E); REP(i, E) { int u, v; cin >> u >> v; edge[i] = {--u, --v}; } int Q; cin >> Q; vector<int> x(Q); vector<int> used(E); REP(i, Q) { cin >> x[i]; --x[i]; used[x[i]] = 1; } UnionFind uf(N + M, N); REP(i, E) if (!used[i]) { uf.unite(edge[i].first, edge[i].second); } vector<int> ans(Q); for (int i = Q - 1; i >= 0; i--) { ans[i] = uf.ans; uf.unite(edge[x[i]].first, edge[x[i]].second); } REP(i, Q) cout << ans[i] << endl; }
F - Monochromatic Path
マス $ (i, j) $ にいるときに行 $ i $ 、列 $ j $ より手前の状態については考慮しなくていいので
$ dp[i][j][row][col] := i $ 行、$ j $ 列にいるときに、$ i $ 行目が反転した状態かどうか（$ row $）、$ j $ 列目が反転した状態かどうか（$ col $）の場合の最小値としてDPを行う
void solve() { int H, W; cin >> H >> W; vector<ll> R(H), C(W); REP(i, H) { cin >> R[i]; } REP(i, W) { cin >> C[i]; } vector<string> A(H); REP(i, H) { cin >> A[i]; } ll ans = LINF; REP(_, 2) { vector dist(2, vector(2, vector(H, vector(W, LINF)))); if (A[0][0] == '0') { dist[0][0][0][0] = 0; dist[1][1][0][0] = R[0] + C[0]; } else { dist[1][0][0][0] = R[0]; dist[0][1][0][0] = C[0]; } REP(h, H) REP(w, W) REP(row, 2) REP(col, 2) { // 下 { int nh = h + 1; int nw = w; if (nh < 0 or nh >= H or nw < 0 or nw >= W) { } else { char c = A[nh][nw]; if (col) { if (c == '0') c = '1'; else c = '0'; } if (c == '0') { chmin(dist[0][col][nh][nw], dist[row][col][h][w]); } else { // nh 行を反転 chmin(dist[1][col][nh][nw], dist[row][col][h][w] + R[nh]); } } } // 右 { int nh = h; int nw = w + 1; if (nh < 0 or nh >= H or nw < 0 or nw >= W) { } else { char c = A[nh][nw]; if (row) { if (c == '0') c = '1'; else c = '0'; } if (c == '0') { chmin(dist[row][0][nh][nw], dist[row][col][h][w]); } else { // nw 列を反転 chmin(dist[row][1][nh][nw], dist[row][col][h][w] + C[nw]); } } } } chmin(ans, min({dist[0][0][H - 1][W - 1], dist[1][0][H - 1][W - 1], dist[0][1][H - 1][W - 1], dist[1][1][H - 1][W - 1]})); REP(i, H) REP(j, W) { if (A[i][j] == '0') A[i][j] = '1'; else A[i][j] = '0'; } } cout << ans << endl; }
