hamayanhamayan https://blog.hatena.ne.jp/hamayanhamayan/ はまやんはまやんはまやん https://blog.hamayanhamayan.com/ 競技プログラミング https://atcoder.jp/contests/abc172/tasks/abc172_c 前提知識 尺取り法 解説 https://atcoder.jp/contests/abc172/submissions/14779347 まずは全探索で考えてみる 机Aからa冊、机Bからb冊取り除くとする。 すると、必要な時間が、A[1]+A[2]+...+A[a] + B[1]+B[2]+...+B[b]となる。 これがK以下であるようなa+bの最小値を答えればいい。 普通にやるとO(NM(N+M))の計算量だけど、A[1]+A[2]+...+A[a]は、以下のような累積和を作っておけば高速に… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.hamayanhamayan.com%2Fentry%2F2020%2F06%2F27%2F230511" title="Tsundoku [AtCoder Beginner Contest 172 C] - はまやんはまやんはまやん" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2020-06-27 23:05:11 rich https://blog.hamayanhamayan.com/entry/2020/06/27/230511 1.0 100%