2022-09-19 ABC075 の A, B, C, D を解いた

ABC075 : AtCoder Beginner Contest 075 の A, B, C, D を解いた。

A - One out of Three https://atcoder.jp/contests/abc075/tasks/abc075_a
- 提出: https://atcoder.jp/contests/abc075/submissions/34985700
- if a == b { c } else if a == c { b } else { a }
B - Minesweeper https://atcoder.jp/contests/abc075/tasks/abc075_b
- 提出: https://atcoder.jp/contests/abc075/submissions/34985769
- すべてのマスを走査して、各マスの周囲の '#' を数える
- 難しくないけど面倒くさい
C - Bridge https://atcoder.jp/contests/abc075/tasks/abc075_c
- 提出: https://atcoder.jp/contests/abc075/submissions/34985906
- N が小さいので指示通りに調べればできてしまう
- 橋の判定は Dsu (Union-Find) を使って単一の連結成分になっているかを調べれば良い
D - Axis-Parallel Rectangle https://atcoder.jp/contests/abc075/tasks/abc075_d
- 提出: https://atcoder.jp/contests/abc075/submissions/34986804
- 愚直にやると上下左右の辺の座標と K 個判定で N^5 で間に合わない
- 座標圧縮と二次元累積和で解く
- 最小の面積になる長方形の各辺は必ずいずれかの点を通る
- K 個以上含んでいるかの判定で x, y の点は各点のものだけになる
- [-10^9, 10^9] の範囲は不要なので座標圧縮してしまう
- 圧縮した座標で二次元累積和を求めて区間和で K 個以上含むかの判定が O(1) になる
- N^4 になり、間に合う

『竜とそばかすの姫』を観た。話が全体的に散らかっている。 U の AS 、現実世界と 1:1 に対応しており U の世界での失敗にやりなおしが効かないのに「やり直せます」みたいなフレーズで売っていることへの嫌悪感が強い。

上の子が寝るときに「とんとんして」などと甘えてくる。下の子を見て甘えたくなる、そんな時期なのだろうか。

今日のコミット。