AtCoder Beginner Contest 151：F - Enclose All

問題

https://atcoder.jp/contests/abc151/tasks/abc151_f

解法

求める半径を二分探索で求める．

半径を r に決めたとき，任意の 2 点を円の中心，半径を r とした円の交点は 2 つに定まる．そして，この 2 点それぞれを円の中心，半径を r とした円 2 つが N 個全ての点を内部または周上に含むかどうかを判定すればよい．このような円が 1 つでもあれば半径 r は十分な大きさだと分かる．1 つもなければ r よりも大きい半径を考える必要があると分かる．O(N^3 * log(ans))．

解答

https://atcoder.jp/contests/abc151/submissions/9471462

AtCoder Beginner Contest 148：D - Brick Break

問題

https://atcoder.jp/contests/abc148/tasks/abc148_d

解法

壊すレンガの数を少なくするには残すレンガの数を増やせばよいので，できる限り 1, 2, 3, ... の列を長くすればよい．これは，次に残したい数字 k（最初は 1）を保持しながら左端からレンガを見ていき，k 以外の数字のレンガが現れたらひたすら壊し，k の数字のレンガが現れたら k++ する，という風に処理すればよい．O(N)．

解答

https://atcoder.jp/contests/abc148/submissions/9061407

AtCoder Beginner Contest 148：E - Double Factorial

問題

https://atcoder.jp/contests/abc148/tasks/abc148_e

解法

N が奇数のとき，答えは 0．なぜならば，f(N) は素因数に 2 と 5 を持たないから．

N が偶数のとき，f(N) が 5 で割れる回数が答えとなる（正確には 2 で割れる回数との min になるが，5 で割れる回数の方が圧倒的に小さいため）．これは，N / (2 * (5^k)) (1 <= k) の和になる（イメージ的には 2 ~ N の偶数のうち 5 で割れるもの， 25 で割れるもの，... の個数を計算していく感じ）．O(log_5(N))．

解答

https://atcoder.jp/contests/abc148/submissions/9072149