atcoder.jp 解法 愚直に解こうとするとO(2N)で絶対間に合わない。 Aはmax、Bは総和が条件として示されているため、A[i] ≦ 5000という制約が気になる。 この制約があることで、Bの和が5000より大きい数になるような集合は考えなくて良いことになる。 Bの要素…

atcoder.jp 解法 二次元グリッドの問題はHとWの制約が同じことが多いが、この問題はHだけが何故かとても小さい。 あからさまに怪しいのでHの小ささを利用したくなる。 そこで、bit全探索を使って横方向の切り方を全探索することにする。 縦方向の切れ目の入…

問題リンク 解法 体重・身長の取る範囲が小さいということがとても気になる。 これをどうにか使えないかと考えてみると、二次元平面上に(身長, 体重)のようにプロットして、何らかの方法で条件を満たすそれぞれの範囲内にいくつ点が存在するかを高速に計算で…