Bondo416さんのユニークビジョンプログラミングコンテスト2023 夏 (AtCoder Beginner Contest 312)での成績：778位
— ボンド@競プロ (@bond_cmprog) July 29, 2023
パフォーマンス：1665相当
レーティング：1537→1551 (+14) :)#AtCoder #ユニークビジョンプログラミングコンテスト2023夏(ABC312) https://t.co/mrBbtVwop2
A - Chord
問題文のとおりに判定する
void solve() { string S; cin >> S; vector<string> T = {"ACE", "BDF", "CEG", "DFA", "EGB", "FAC", "GBD"}; for (auto t : T) { if (S == t) { cout << "Yes" << endl; return; } } cout << "No" << endl; }
B - TaK Code
サンプルにTak Codeがあるのでそれを利用する
左上の点の位置を全探索し、# と . の点の位置全て一致するかを判定する
###.????? ###.????? ###.????? ....????? ????????? ?????.... ?????.### ?????.### ?????.###
void solve() { int N, M; cin >> N >> M; vector<string> S(N); REP(i, N) cin >> S[i]; vector<string> task = { "###.?????", "###.?????", "###.?????", "....?????", "?????????", "?????....", "?????.###", "?????.###", "?????.###", }; REP(i, N - 9 + 1) REP(j, M - 9 + 1) { int cnt = 0; REP(h, 9) REP(w, 9) { if (task[h][w] == '?') cnt++; else if (task[h][w] == S[i + h][j + w]) cnt++; } if (cnt == 9 * 9) { cout << i + 1 << " " << j + 1 << endl; } } }
C - Invisible Hand
$ X $ 円のときに条件を満たすかどうかを判定できるのでこれを二分探索で求める
void solve() { int N, M; cin >> N >> M; vector<int> A(N), B(M); REP(i, N) cin >> A[i]; REP(i, M) cin >> B[i]; sort(ALL(A)); sort(ALL(B)); ll l = 0, r = 2 * INF; while (r - l > 1) { ll m = (l + r) >> 1; ll cnt_a = 0; ll cnt_b = 0; REP(i, N) if (A[i] <= m) cnt_a++; REP(i, M) if (B[i] >= m) cnt_b++; if (cnt_a >= cnt_b) r = m; else l = m; } cout << r << endl; }
D - Count Bracket Sequences
括弧列は ( のとき +1 、 ) のとき -1 としたときの累積和が途中で負にならず、合計が0となるものであるので
$ dp[i][j] := i $ 番目の文字まで見たときの累積和が $ j $ であるときの場合の数としてDPを行えば良い
void solve() { string S; cin >> S; const int N = S.size(); vector<mint> dp(N + 110); dp[0] = 1; REP(i, N) { vector<mint> nxt(N + 10); REP(j, N + 1) { if (S[i] == '(') { nxt[j + 1] += dp[j]; } else if (S[i] == ')') { if (j > 0) nxt[j - 1] += dp[j]; } else { nxt[j + 1] += dp[j]; if (j > 0) nxt[j - 1] += dp[j]; } } swap(dp, nxt); } cout << dp[0] << endl; }
E - Tangency of Cuboids
それぞれの立方体が重なることはないので $ 1 \times 1 \times 1 $ の立方体は高々1つの立方体に属することになる
また、各立方体は上下左右前後の6方向に対して別の立方体が属する $ 1 \times 1 \times 1 $ の立方体が存在すれば面で接することになる
立方体の数は制約から最大で $ 10 ^ 6 $ 程度であるので全探索をすれば良い
void solve() { int N; cin >> N; vector<int> X1(N), Y1(N), Z1(N), X2(N), Y2(N), Z2(N); vector cube(111, vector(111, vector(111, -1))); REP(i, N) { cin >> X1[i] >> Y1[i] >> Z1[i] >> X2[i] >> Y2[i] >> Z2[i]; REP(x, X1[i], X2[i]) REP(y, Y1[i], Y2[i]) REP(z, Z1[i], Z2[i]) cube[x][y][z] = i; } vector<set<int>> st(N); REP(x, 101) REP(y, 101) REP(z, 101) if (cube[x][y][z] != -1) { if (cube[x + 1][y][z] != -1 and cube[x + 1][y][z] != cube[x][y][z]) { st[cube[x + 1][y][z]].emplace(cube[x][y][z]); st[cube[x][y][z]].emplace(cube[x + 1][y][z]); } if (cube[x][y + 1][z] != -1 and cube[x][y + 1][z] != cube[x][y][z]) { st[cube[x][y + 1][z]].emplace(cube[x][y][z]); st[cube[x][y][z]].emplace(cube[x][y + 1][z]); } if (cube[x][y][z + 1] != -1 and cube[x][y][z + 1] != cube[x][y][z]) { st[cube[x][y][z + 1]].emplace(cube[x][y][z]); st[cube[x][y][z]].emplace(cube[x][y][z + 1]); } } REP(i, N) cout << st[i].size() << endl; }
F - Cans and Openers
$ T_i = 2 $ のものを使うときは $ X_i $ が大きいものから順に使っていけばいい
また、$ T_i = 0 $ のものははじめから全て集合に追加されているとし、$ T_i = 2 $ のものを選んだときの $ X_i $ の合計だけ $ T_i = 1 $ の要素を降順に集合に追加していくと考える
そうすると、今ある集合から降順 $ k $ 個の総和を求める事ができれば良い
これはBITやpriority_queueを用いれば高速に求めることができるので、$ T_i = 2 $ のものを $ i $ 個選び、$ X_i $ 個だけ $ T_i = 1 $ のものが追加された集合の降順 $ M - i $ 個の総和をそれぞれ求め、その最大を答えれば良い
void solve() { int N, M; cin >> N >> M; vector<int> T(N), X(N); vector<vector<int>> TX(3); MaximumSum<ll> sum(M); REP(i, N) { cin >> T[i] >> X[i]; TX[T[i]].push_back(X[i]); } REP(i, M) sum.insert(0); for (auto x : TX[0]) { sum.insert(x); } priority_queue<int> pq; for (auto x : TX[1]) { pq.push(x); } sort(ALL(TX[2])); reverse(ALL(TX[2])); ll ans = sum.query(); int used = 0; for (auto x : TX[2]) { while (x > 0 && !pq.empty()) { int y = pq.top(); pq.pop(); sum.insert(y); x--; dump(y); } used++; if (M - used <= 0) break; sum.set_k(M - used); chmax(ans, sum.query()); } cout << ans << endl; }
