草
— ボンド@競プロ (@bond_cmprog) November 22, 2020
Bondo416さんのAtCoder Beginner Contest 184での成績：1064位
パフォーマンス：1476相当
レーティング：1489→1488 (-1) :(#AtCoder #ABC184 https://t.co/ExShOFZaN5
A - Determinant
定義が書いてあるのでそれを出力
提出コード
void solve(){ int a, b, c, d; cin >> a >> b >> c >> d; cout << a * d - b * c << endl; }
B - Quizzes
点数をシミュレートする
提出コード
void solve(){ int N, X; string S; cin >> N >> X >> S; REP(i,N){ if(S[i] == 'o') X++; else{ X = max(0, X-1); } } cout << X << endl; }
C - Super Ryuma
頭壊れる
任意の点に最大3手以内にいける
$ (r_1, c_1) = (r_2, c_2) $の場合は0でそれ以外の場合を考える
初期状態から1手で行けるときは$ |r_1 - r_2| + |c_1 - r_c| \leq 3 $ もしくは対角成分上にあるときならば可能
2手で行けるときは、市松模様にマスに色を塗ったときに同じ色の場合2手で行ける
それ以外の場合、$ |r_1 - r_2| + |c_1 - r_c| \leq 3 $が必要になるので移動できる箇所を全探索し、上記の判定をもう一度考える
提出コード
void solve(){ ll r1, c1, r2, c2; cin >> r1 >> c1 >> r2 >> c2; if(r1 == r2 and c1 == c2) cout << 0 << endl; else if(abs(r1 - r2) + abs(c1 - c2) <= 3) cout << 1 << endl; else if(r1 + c1 == r2 + c2) cout << 1 << endl; else if(r1 - c1 == r2 - c2) cout << 1 << endl; else if(abs(r2 - r1) % 2 == abs(c2 - c1) % 2) cout << 2 << endl; else{ int ans = INF; for(int i=-3;i<=3;i++) for(int j=-3;j<=3;j++){ if(i == 0 and j == 0) continue; ll nr = r1 + i, nc = c1 + j; if(abs(r1-nr) + abs(c1-nc) > 3) continue; if(r2 == nr and c2 == nc) chmin(ans, 1); else if(nr + nc == r2 + c2) chmin(ans, 2); else if(nr - nc == r2 - c2) chmin(ans, 2); else if(abs(nr - r2) + abs(nc - c2) <= 3) chmin(ans, 2); else chmin(ans, 3); } cout << ans << endl; } }
D - increment of coins
期待値のDPをする
$ dp[a][b][c] := $ 金貨がa枚、銀貨がb枚、銅貨がc枚あるときの期待値とすると3つのうちどれが選ばれるかで
$ dp[a][b][c] = \frac{dp[a+1][b][c] \times a + dp[a][b+1][c] \times b + dp[a][b][c+1] \times c}{a + b + c} + 1 $となる
実装はメモ化再起のほうが楽そう
提出コード
void solve(){ int A, B, C; cin >> A >> B >> C; if(A >= 100 or B >= 100 or C >= 100){ cout << 0 << endl; return; } vector dp(101, vector(101, vector(101, -1.0))); auto dfs = [&](auto && self, int a, int b, int c) -> double{ if(a >= 100 or b >= 100 or c >= 100) return 0; if(dp[a][b][c] > -1) return dp[a][b][c]; double sum = a + b + c; return dp[a][b][c] = (self(self, a+1, b, c) * a + self(self, a, b+1, c) * b + self(self, a, b, c+1) * c) / sum + 1; }; printf("%.12lf\n", dfs(dfs, A, B, C)); }
E - Third Avenue
各テレポーターごとに移動可能なマスを予め保存しておく
今いるマスがテレポーターなら同じテレポーターのマスにコスト1で移動出来るとしてBFSをする
テレポーターを使う場合同じテレポーターは一回までしか使わなくていいので、すでに使ったことのあるテレポーターの場合、もう使えないものとして無視すればいい
提出コード
void solve(){ int H, W; cin >> H >> W; vector<string> fi(H); REP(i,H) cin >> fi[i]; vector<vector<pair<int, int>>> alp(26); int sh, sw, gh, gw; REP(i,H) REP(j,W){ if(fi[i][j] == 'S') sh = i, sw = j; else if(fi[i][j] == 'G') gh = i, gw = j; else if(fi[i][j] != '#' and fi[i][j] !='.'){ alp[fi[i][j] - 'a'].emplace_back(i, j); } } vector<vector<int>> dist(H, vector<int>(W, INF)); queue<pair<int, int>> q; q.emplace(sh, sw); dist[sh][sw] = 0; vector<bool> used(26); while(!q.empty()){ auto [h, w] = q.front(); q.pop(); if('a' <= fi[h][w] and fi[h][w] <= 'z' and !used[fi[h][w]-'a']){ used[fi[h][w]-'a'] = true; for(auto [nh, nw] : alp[fi[h][w]-'a']){ if(dist[nh][nw] != INF) continue; if(chmin(dist[nh][nw], dist[h][w] + 1)){ q.emplace(nh, nw); } } } REP(i,4){ int nh = h + dx[i], nw = w + dy[i]; if(nh < 0 or nh >= H or nw < 0 or nw >= W or fi[nh][nw] == '#') continue; if(dist[nh][nw] != INF) continue; if(chmin(dist[nh][nw], dist[h][w] + 1)) q.emplace(nh, nw); } } ll ans = dist[gh][gw]; if(ans == INF) ans = -1; cout << ans << endl; }
F - Programming Contest
半分全列挙をする
集合の半分をbit全探索で各組み合わせのごとの和を昇順ソートした配列を作る
もう半分の集合にbit全探索を行い$ T $以下になる和の最大を二分探索で求める
提出コード
void solve(){ int N; ll T; cin >> N >> T; vector<ll> A(N); REP(i,N) cin >> A[i]; int n2 = N / 2; vector<ll> v(1<<n2); REP(i,1<<n2){ ll sumT = 0; REP(j,n2) if(i >> j & 1) sumT += A[j]; v.emplace_back(sumT); } sort(v.begin(), v.end()); ll ans = 0; dump(v); REP(i,1<<(N-n2)){ ll sumT = 0; REP(j,N-n2) if(i >> j & 1) sumT += A[j+n2]; dump(sumT); if(sumT <= T){ ll t = *(upper_bound(v.begin(), v.end(),T - sumT) - 1); chmax(ans, sumT + t); } } cout << ans << endl; }
