2022-09-08 ABC099 の A, B, C, D を解いた
ABC099 : AtCoder Beginner Contest 099 の A, B, C, D を解いた。
- A - ABD
https://atcoder.jp/contests/abc099/tasks/abc099_a
- 提出: https://atcoder.jp/contests/abc099/submissions/34689599
if n < 1000 { "ABC" } else { "ABD" }
- B - Stone Monument
https://atcoder.jp/contests/abc099/tasks/abc099_b
- 提出: https://atcoder.jp/contests/abc099/submissions/34689675
((b - a) - 1) * (b - a) / 2 - ab - aは西側の塔と東側の塔の間隔- 西側の塔は
1 + 2 + ... + (b - a - 1)になることが分かる - 積雪量は西側の塔の高さから
aを引けば良い
- C - Strange Bank
https://atcoder.jp/contests/abc099/tasks/abc099_c
- 提出: https://atcoder.jp/contests/abc099/submissions/34690017
- 一回の操作で引き出せる金額の種類の列挙をループの境界値を間違えて 3 WA
- 貪欲に大きいから使えるだけ使うとダメなのは入力例 3 で分かる
- 一回の操作で引き出せる金額の数列を
Cとする |C|はたかだか十数個しかないN <= 10^5なのでN * |C|しても十分に間に合うdp[i]をi円の引き出しの最小操作回数とおくdp[0] = 0dp[i] = dp[i].min(dp[i - C_j] + 1)dp[N]が答えになる
- D - Good Grid
https://atcoder.jp/contests/abc099/tasks/abc099_d
- 提出: https://atcoder.jp/contests/abc099/submissions/34690263
- 意外と C より簡単かもしれない
... % 3ごとに色が決まっているのだからグリッド全体で 3 色を使うことになるC <= 30なので最終的な色の組み合わせは_30C_3 = 4060N <= 500なのでN^2 <= 2500004060 * 250000の時点で間に合わないので単純な全探索はできない- 色
Xに揃えた場合の不快感の和は250000で... % 3 == 0, 1, 2の 3 つが求められる - 各色を同様に求めると
30 * 250000で... % 3 == 0, 1, 2をそれぞれの色にしたときの不快感の和が求められる。これは間に合う - あとはこの事前に計算した不快感の和から
3つを重複がないように選んだときの最小値を求める - およそ
30 * 30 * 30なので間に合う
PostgreSQL の OFFSET LIMIT を使うときは ORDER BY で決まった順になることに注意する。 ORDER BY で並びが決まらない場合は並びが保証されないので同じものが別ページに 2 回出たりどこにも出なかったりする。
今日のコミット。