二分探索
考え方 回答例 考え方両端にある0と1の位置を，二分探索の要領で隣り合うまで寄せていけば良い． 回答例 N = int(input()) zero = 1 one = N while one - zero > 1: mid = (zero + one) // 2 print('?', mid) ans = int(input()) if ans == 1: one = mid eli…
周回回数を効率的に求め，残り$N$個以下になったら愚直に数えることを考える． 解法1：二分探索 考え方 回答例 解法2：シミュレーション 考え方 回答例 解法1：二分探索考え方Editorial - TOYOTA MOTOR CORPORATION Programming Contest 2022(AtCoder Beginn…
解法1：二分探索 考え方 回答例 解法2：消費する本の数に着目 考え方 解法1：二分探索考え方「$x$巻まで読むことができる」は， $x$巻以下で持っている本の種類の数 (↑以外の本の数) // 2 の和が$x$以上であることと同値．Editorial - KYOCERA Programming C…
考え方 回答例 考え方$i$軸のうち，どの$j$座標にもルークが含まれないのは1つだけである．したがって，「$(A, B, 1, N)$を聞いたときに$B - A - 1$が帰って来ること」が「$A \leq X \leq B$」の必要十分条件である．よって，二分探索で$X$を求めることがで…
解法：しゃくとり法 考え方 回答例 解法：累積和（+set） 考え方 解法：しゃくとり法考え方3回のしゃくとり法で，$x = P, Q, R$に対し 区間和が$\sum_{[l, r)} A_{l} = x$を満たす$l$の集合$S_{x}$ $l$を$r$に対応させる辞書$f_{x} (l)=r$ を求めておく．Yes…
考え方 回答例 考え方最小値の最大値なので，二分探索を考える．すべての要素を$x$以上にできるかは， $x + b$以上の要素から$b$減らせる操作回数 $x$未満の要素から$a$増やさなければならない操作回数 の2つを比較することで判定できる．回答例 N, a, b = m…
考え方 回答例 考え方答え（$S$）で二分探索（$O(\log \cdots)$）する．$S$を決めれば辺を$O(N^{2})$で張れる．スタート地点（$N$通り）を決めれば，BFS（$O(N^{2})$）で全ての頂点に行けるかどうかを計算できる．回答例すでに訪れた頂点はリストではなくset…
解法1 考え方 回答例 解法1考え方$S_{1} = [A_{1},...,A_{K}]$と$S_{2} = [A_{K + 1},...,A_{N}]$の中から1つずつ$A_{i} $S_{2}$を前から見ていって，$A_{i - 1} > A_{i}$となる$i$があれば，$A_{i}$を$A_{i - 1}$で置き換える．こうしてできた配列を$S_{2}^…
考え方 回答例 考え方式変形（因数分解など）で何かを見出そうとしても上手く行かない．2変数の問題は， 2次元平面で考える 1変数を固定して考える とよい．$0 \leq N \leq 10^{18}$だから，$0 \leq a,b \leq 10^{6}$である．よって，$a,b$の全探索はできな…
考え方 回答例 (Python) 回答例 (C++) 考え方最小値を最大にする問題なので，二分探索ぽい．実際， 答え$x$を決め打ちすれば，$K+1$個に分割できるかどうかは$O(N)$でシミュレーションでき（※）， ある値を堺に$K+1$分割できる / できなくなるが決まる とな…
考え方 平均値 中央値 二分探索＋DP 回答例 考え方公式解説がわかりやすい．二分探索＋DP． Editorial - AtCoder Beginner Contest 236平均値\begin{aligned} & \frac{1}{n} \sum_{i=1}^{n} x_{i} \geq K \\ & \Leftrightarrow \sum_{i=1}^{n} (x_{i} -K) \g…
ABC227Dと内容はほとんど同じですが，計算を効率的にしなければなりません． 【類題】 D - Project Planning (ABC227D - Project Planning - 競プロはじめました) 方法1 考え方 回答例 方法2 考え方 回答例 方法3 考え方 回答例 方法1考え方まず，整数$a$が…
【類題】 F - Distinct Numbers (ABC143F - Distinct Numbers - 競プロはじめました) 考え方 回答例 考え方部署$i=1$から順番に，下図のように割り当てることを考える．考え方すると，部署$i$のメンバーで使えるのは$\min(x, A_{i})$となる（チーム数を超え…
