Bondo416さんのパナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 301）での成績：221位
— ボンド@競プロ (@bond_cmprog) May 13, 2023
パフォーマンス：2134相当
レーティング：1559→1631 (+72) :)#AtCoder #パナソニックグループプログラミングコンテスト2023（ABC301） https://t.co/wpUgSns4Yh
A - Overall Winner
T と A の個数を数える
個数が同じ場合、最後に数えたものが負け
void solve() { int N; string S; cin >> N >> S; bool f = false; int a = 0, t = 0; REP(i, N) { if (S[i] == 'T') { t++; f = true; } else { a++; f = false; } } if (a > t) cout << "A" << endl; else if (a < t) cout << "T" << endl; else { if (f) cout << "A" << endl; else cout << "T" << endl; } }
B - Fill the Gaps
問題文の条件のとおりに出力をする
void solve() { int N; cin >> N; vector<int> A(N); REP(i, N) cin >> A[i]; cout << A[0] << " "; REP(i, 1, N) { if (abs(A[i] - A[i - 1]) == 1) cout << A[i] << " "; else if (A[i] > A[i - 1]) { REP(j, A[i - 1] + 1, A[i] + 1) cout << j << " "; } else if (A[i] < A[i - 1]) { for (int j = A[i - 1] - 1; j >= A[i]; j--) cout << j << " "; } } cout << endl; }
C - AtCoder Cards
各文字ごとに文字数を数え、SとTで文字数が同じかどうかを比較していく
このとき @はa, t, c, o, d, e, rに置き換えられるので足りない分は置き換えてしまっていい
SとTで文字数を同じにできない文字がある場合はNo、それ以外はYesとなる
void solve() { string S, T; cin >> S >> T; vector<int> s(27), t(27); for (char c : S) { if (c == '@') s[26]++; else s[c - 'a']++; } for (char c : T) { if (c == '@') t[26]++; else t[c - 'a']++; } set<char> st = {'a', 't', 'c', 'o', 'd', 'e', 'r'}; REP(i, 26) { if (s[i] == t[i]) continue; else if (!st.count(char(i + 'a'))) { cout << "No" << endl; return; } else if (s[i] > t[i]) { if (s[i] - t[i] > t[26]) { cout << "No" << endl; return; } else { t[26] -= s[i] - t[i]; } } else if (s[i] < t[i]) { if (t[i] - s[i] > s[26]) { cout << "No" << endl; return; } else { s[26] -= t[i] - s[i]; } } } cout << "Yes" << endl; }
D - Bitmask
? を 0とした場合の2進数整数を予め求めておく
その後、上位bitから順に見ていき?を1としたときの2進数整数が $ N $ 以下の場合、そのbitは1としてしまって良い
void solve() { string S; ll N; cin >> S >> N; ll cur = 0; reverse(ALL(S)); REP(i, S.size()) if (S[i] == '1') cur += 1LL << i; if (cur > N) { cout << -1 << endl; return; } for (int i = (int)S.size() - 1; i >= 0; i--) if (S[i] == '?' and cur + (1LL << i) <= N) cur += 1LL << i; cout << cur << endl; }
E - Pac-Takahashi
S, G, o のみに注目すると頂点数は高々20となり巡回セールスマン問題のようにbit DPで求めることができる
そのため、各頂点間の距離を予めBFSなどで求めておくことで以下のDPで答えを求めることができる
$ dp[i][j] := $ 最後に訪れた頂点が $ i $ で、訪れた頂点集合が $ j $ としたときの移動回数の最小
求めたい答えは、最後にGを訪れたときに移動回数が $ T $ 以下であるときの頂点集合に含まれる oの数の最大であるので条件を満たすもののうち、頂点集合に含まれる oの数の最大を求めればいい
void solve() { int H, W, T; cin >> H >> W >> T; vector<string> s(H); REP(i, H) cin >> s[i]; vector<pair<int, int>> snack; int sh, sw, gh, gw; REP(i, H) REP(j, W) { if (s[i][j] == 'S') sh = i, sw = j; else if (s[i][j] == 'G') gh = i, gw = j; } snack.emplace_back(sh, sw); snack.emplace_back(gh, gw); REP(i, H) REP(j, W) { if (s[i][j] == 'o') snack.emplace_back(i, j); } int n = snack.size(); vector<vector<int>> dist(n, vector<int>(n, INF)); REP(i, n) { auto [h, w] = snack[i]; vector<vector<int>> d(H, vector<int>(W, INF)); d[h][w] = 0; queue<pair<int, int>> q; q.emplace(h, w); while (!q.empty()) { auto [cur_h, cur_w] = q.front(); q.pop(); REP(dir, 4) { int nh = cur_h + dx[dir]; int nw = cur_w + dy[dir]; if (nh < 0 || nh >= H || nw < 0 || nw >= W) continue; if (s[nh][nw] == '#') continue; if (d[nh][nw] < INF) continue; d[nh][nw] = d[cur_h][cur_w] + 1; q.emplace(nh, nw); } } REP(j, n) dist[i][j] = d[snack[j].first][snack[j].second]; } vector dp(n, vector<int>(1 << n, INF)); dp[0][0] = 0; dp[0][1] = 0; // s = 0, g=1 REP(i, 1, (1 << n) + 1) { REP(j, n) if (i >> j & 1) { REP(k, n) { int cost = dp[j][i ^ (1 << j)] + dist[j][k]; chmin(dp[k][i], cost); } } } int ma = -1; REP(i, 1 << n) if ((i & 1) and (i >> 1 & 1) and dp[1][i] <= T) { chmax(ma, __builtin_popcount(i ^ 1 ^ 2)); } cout << ma << endl; }