Bondo416さんのトヨタ自動車プログラミングコンテスト2024#3（AtCoder Beginner Contest 344）での成績：452位
— ボンド@競プロ (@bond_cmprog) March 9, 2024
パフォーマンス：1894相当
レーティング：1570→1607 (+37) :)#AtCoder #トヨタ自動車プログラミングコンテスト2024#3（ABC344） https://t.co/HFPZSaSyYO
A - Spoiler
| でフラグを切り替え、フラグによって出力をするかしないかを判断する
void solve() { string S; cin >> S; bool skip = false; for (char c : S) { if (c == '|') skip = !skip; else if (!skip) cout << c; } cout << endl; }
B - Delimiter
0 が出てくるまで値を読み込みvectorなどに格納し、逆順に出力する
void solve() { vector<int> A; int n; while (true) { cin >> n; A.push_back(n); if (n == 0) break; } reverse(ALL(A)); for (auto a : A) cout << a << endl; }
C - Divide and Divide
最大ケースでも $ NML = 10^6 $ なので予め前計算した結果をsetなどに入れておくことで各クエリに高速に答えられる
void solve() { int N; cin >> N; vector<int> A(N); REP(i, N) cin >> A[i]; int M; cin >> M; vector<int> B(M); REP(i, M) cin >> B[i]; int L; cin >> L; vector<int> C(L); REP(i, L) cin >> C[i]; set<int> st; REP(i, N) REP(j, M) REP(k, L) { st.insert(A[i] + B[j] + C[k]); } int Q; cin >> Q; while (Q--) { int X; cin >> X; cout << (st.count(X) ? "Yes" : "No") << '\n'; } }
D - String Bags
$ dp[i][j] := i $ 番目の袋まで見たときに $ j $ 文字目まで一致している状態に必要な最小金額としてDPをする
void solve() { string T; int N; cin >> T >> N; vector<int> A(N); vector<vector<string>> S(N); REP(i, N) { cin >> A[i]; REP(j, A[i]) { string s; cin >> s; S[i].emplace_back(s); } } int sz = T.size(); vector<int> dp(sz + 1, INF); dp[0] = 0; REP(i, N) { vector<int> nxt(sz + 1, INF); REP(j, sz + 1) { if (dp[j] == INF) continue; chmin(nxt[j], dp[j]); int len = S[i].size(); REP(k, len) { int l = S[i][k].size(); if (j + l > sz) continue; bool ok = true; REP(m, l) { if (T[j + m] != S[i][k][m]) { ok = false; break; } } if (ok) { chmin(nxt[j + l], dp[j] + 1); } } } swap(dp, nxt); } cout << (dp[sz] < INF ? dp[sz] : -1) << endl; }
E - Insert or Erase
ABC225D と同じように各値について自分の前後の値の情報を持っておき、各クエリごとにそれらを更新する
void solve() { int N; cin >> N; map<int, pair<int, int>> node; vector<int> A(N); REP(i, N) { cin >> A[i]; node[A[i]] = {-1, -1}; } REP(i, N - 1) { node[A[i]].second = A[i + 1]; node[A[i + 1]].first = A[i]; } int Q; cin >> Q; while (Q--) { int q; cin >> q; if (q == 1) { int x, y; cin >> x >> y; if (node[x].second == -1) { // 末尾 node[x].second = y; node[y].first = x; node[y].second = -1; } else { // それ以外 int z = node[x].second; node[x].second = y; node[y].first = x; node[y].second = z; node[z].first = y; } } else if (q == 2) { int x; cin >> x; if (node[x].first == -1) { // 先頭 int y = node[x].second; node[y].first = -1; } else if (node[x].second == -1) { // 末尾 int y = node[x].first; node[y].second = -1; } else { // それ以外 node[node[x].first].second = node[x].second; node[node[x].second].first = node[x].first; } node.erase(x); } } int start = -1; for (auto [key, value] : node) { if (value.first == -1) { start = key; break; } } while (start != -1) { cout << start << " "; start = node[start].second; } cout << endl; }
F - Earn to Advance
マス $ (i, j) $ から マス $ (k, l) $ まで移動するのに必要な最小コストは予めDPで求められるので前計算しておく
また、マス $ (i, j) $ から マス $ (k, l) $ へ移動するため必要な最小行動回数は現在の所持金と必要なコストから求めることができるので以下のDPをする
$ dp[i][j] := $ マス $ (i, j) $ にたどり着くのに必要な (最小の行動回数, その時の所持金の最大)のペア
void solve() { ll N; cin >> N; vector<vector<ll>> P(N, vector<ll>(N)); REP(i, N) REP(j, N) cin >> P[i][j]; vector<vector<ll>> R(N, vector<ll>(N - 1)); REP(i, N) REP(j, N - 1) cin >> R[i][j]; vector<vector<ll>> D(N - 1, vector<ll>(N)); REP(i, N - 1) REP(j, N) cin >> D[i][j]; int sz = N * N; vector<vector<ll>> cost(sz, vector<ll>(sz, LINF)); REP(i, N) REP(j, N) { // y, x int start = i * N + j; cost[start][start] = 0; REP(k, i, N) REP(l, j, N) { int from = k * N + l; if (l + 1 < N) { // R int ny = k, nx = l + 1; int to = ny * N + nx; chmin(cost[start][to], cost[start][from] + R[k][l]); } if (k + 1 < N) { // D int ny = k + 1, nx = l; int to = ny * N + nx; chmin(cost[start][to], cost[start][from] + D[k][l]); } } } dump(cost); vector<LP> dp(sz, LP(LINF, -LINF)); // move, money dp[0] = LP(0, 0); REP(i, sz) { REP(j, sz) { if (i == j) continue; if (cost[i][j] == LINF) continue; int y1 = i / N, x1 = i % N; int y2 = j / N, x2 = j % N; ll cur_money = dp[i].second; ll need_money = cost[i][j]; ll need_move_cnt = abs(y1 - y2) + abs(x1 - x2); if (cur_money >= need_money) { if (dp[j].first > dp[i].first + need_move_cnt) { dp[j].first = dp[i].first + need_move_cnt; dp[j].second = cur_money - need_money; } else if (dp[j].first == dp[i].first + need_move_cnt) { chmax(dp[j].second, cur_money - need_money); } } else { ll need = need_money - cur_money; ll need_cnt = ceil_div(need, P[y1][x1]); ll earned_money = need_cnt * P[y1][x1]; if (dp[j].first > dp[i].first + need_cnt + need_move_cnt) { dp[j].first = dp[i].first + need_cnt + need_move_cnt; dp[j].second = earned_money + cur_money - need_money; } else if (dp[j].first == dp[i].first + need_cnt + need_move_cnt) { chmax(dp[j].second, earned_money + cur_money - need_money); } } } } cout << dp[sz - 1].first << endl; }
