二分探索

C. Creative Snap 〜10^9を扱うには?二分探索・再帰関数〜

Quiz https://codeforces.com/contest/1111/problem/C AC Code https://codeforces.com/contest/1111/submission/56781314 解法 考えている範囲で一気に燃やすコスト 考えている範囲を二分割して個別に燃やすコスト 上記2つのうち、安い方を選ぶように再帰…

二分探索と凸関数とマンハッタン距離

Quiz https://yukicoder.me/problems/no/513 インタラクティブ問題 query(x, y)を投げると、宝までのマンハッタン距離が返ってくる 最大100クエリで場所を求めよ ACコード https://yukicoder.me/submissions/351288 x, yは独立に求められる 以下ではxを求め…

No.477 MVP

Quiz https://yukicoder.me/problems/no/477 Submit https://yukicoder.me/submissions/336588 解法 他の人は数式で解いていたが、私は二分探索で解いた 二分探索 left = 0 (絶対にMVPが取れない) right = inf (絶対にMVPが取れる) center = (left + right) …

B - 交通費

Quiz https://atcoder.jp/contests/bitflyer2018-final-open/tasks/bitflyer2018_final_b Submit https://atcoder.jp/contests/bitflyer2018-final-open/submissions/4881138 解法 editorialの通り 感想 lower_boundでiteratorを取ってきた後、+1, -1をした…

誤差と桁あふれはできれば避けたい

誤差と桁あふれに注意する必要があるよい問題(教材)がある。 Quiz https://yukicoder.me/problems/no/648 Submit https://yukicoder.me/submissions/335262 解法 t秒後の合計はt * (t+1) / 2 それとnが一致する整数があればいい tについて解の公式で解く …

D - Lazy Faith

Quiz https://atcoder.jp/contests/abc119/tasks/abc119_d Submit https://atcoder.jp/contests/abc119/submissions/4374869 Note xの位置から見て、一番近い右にある寺・神社 xの位置から見て、一番近い左にある寺・神社 をそれぞれ求める 右の神社に行って…

Coffee and Coursework D1, D2 ☕

Quiz https://codeforces.com/contest/1118/problem/D1 https://codeforces.com/contest/1118/problem/D2 Submit https://codeforces.com/contest/1118/submission/50237247 解法 d日で解けるかを二分探索 カフェイン列は大きい順にソートしておき、各日の早…

C. Magic Ship (Educational Codeforces Round 60)

Quiz https://codeforces.com/contest/1117/problem/C Submit https://codeforces.com/contest/1117/submission/50138888 解法 二分探索 日数を固定(daysとする)したとき、まず流され、そのあと移動する 流された後の位置とゴールのマンハッタン距離 <= days…