2022-08-26 ABC183 の A, B, C, D, E を解いた

ABC183 : AtCoder Beginner Contest 183 の A, B, C, D, E を解いた。

A - ReLU https://atcoder.jp/contests/abc183/tasks/abc183_a
- 提出: https://atcoder.jp/contests/abc183/submissions/34345563
- x < 0 なら 0 にすればいいので x.max(0)
B - Billiards https://atcoder.jp/contests/abc183/tasks/abc183_b
- 提出: https://atcoder.jp/contests/abc183/submissions/34345691
- G_y を -G_y にしてできた直線と x 軸の交点を求める
C - Travel https://atcoder.jp/contests/abc183/tasks/abc183_c
- 提出: https://atcoder.jp/contests/abc183/submissions/34345777
- N <= 8 なので訪問順はすべて列挙しても 7! 個
- それらについて移動時間の合計が K と一致するかを調べて数えても十分に間に合う
- next_permutation を使って列挙すると良い
D - Water Heater https://atcoder.jp/contests/abc183/tasks/abc183_d
- 提出: https://atcoder.jp/contests/abc183/submissions/34345872
- いわゆる「いもす法」で良い
- 開始位置に +P 終了位置に -P を置き、最後に累積和を取ることで計算量を減らせる
E - Queen on Grid https://atcoder.jp/contests/abc183/tasks/abc183_e
- 提出: https://atcoder.jp/contests/abc183/submissions/34346286
- 解説 AC
- 素朴に扱うと何度も行や列を走査してしまうので間に合わない
- 同一行・列・斜めを累積和として扱うことで 2 個以上先を見なくて済む
- ここまで見えていながらうまく実装できなくて諦めた

先週髪を切りそびれたので切った。

今日のコミット。