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 の世界での失敗にやりなおしが効かないのに「やり直せます」みたいなフレーズで売っていることへの嫌悪感が強い。
上の子が寝るときに「とんとんして」などと甘えてくる。下の子を見て甘えたくなる、そんな時期なのだろうか。
今日のコミット。
