2022-08-24 ABC104 の A, B, C, D を解いた

ABC104 : AtCoder Beginner Contest 104 の A, B, C, D を解いた。

A - Rated for Me https://atcoder.jp/contests/abc104/tasks/abc104_a
- 提出: https://atcoder.jp/contests/abc104/submissions/34309325
- if r < 1200 { "ABC" } else if r < 2800 { "ARC" } else { "AGC" }
B - AcCepted https://atcoder.jp/contests/abc104/tasks/abc104_b
- 提出: https://atcoder.jp/contests/abc104/submissions/34309397
- 指示通りに判定するだけではあるけどミスしやすい
C - All Green https://atcoder.jp/contests/abc104/tasks/abc104_c
- 提出: https://atcoder.jp/contests/abc104/submissions/34309621
- ボーナス点を無視すれば高得点側から貪欲に取れば良い
- ボーナス点のとり方の組み合わせは 2.pow(D) D <= 10 しかないのでそれごとに貪欲に調べても十分に間に合う
D - We Love ABC https://atcoder.jp/contests/abc104/tasks/abc104_d
- 提出: https://atcoder.jp/contests/abc104/submissions/34310107
- 解説 AC
- 3 点を選ぶときは真ん中を決め打ちすると良いことが多い
- B の位置を前から順に走査する (B または ? の箇所以外は 0)
- その位置より左の A の数 (L_A), 右の C の数 (R_C), 同様に ? を L_Q, R_Q とおく
- ? を無視すれば、左側 (L_A) と右側 (R_C) をかけたものの和が答えになる
- ? を考慮すると……
- A を A として使う場合は L_A * 3.pow(L_Q), ? を A として使う場合は L_Q * 3.pow(L_Q - 1) が左側
- 同様に右側が R_C * 3.pow(R_Q) + R_Q * 3.pow(R_Q - 1)
- 左側と右側をかけたものの和が答えになる
- 真ん中を固定、位置ごとの個数を数える、A を A として使う場合と ? を A として使う場合分けまでは見えていた
- 3.pow(...) の部分がなぜか出なかった……なぜ……

今日のコミット。