hamayanhamayan https://blog.hatena.ne.jp/hamayanhamayan/ はまやんはまやんはまやん https://blog.hamayanhamayan.com/ 競技プログラミング https://atcoder.jp/contests/acl1/tasks/acl1_d 解説 https://atcoder.jp/contests/acl1/submissions/16924046 強実装問題。 クエリ問題は1クエリではどう解くかを考えよう まずは1つのクエリに対してどうやって解くかを考えていこう。 「よい集合の和集合のサイズ」という珍しい条件は一旦忘れて、 条件を満たす部分集合の個数を最大化する方法を考える。 これは先頭の点から貪欲に距離がK以上となるように選択していくことで、 取れる点の個数を最大化できる。 色々実験してみると、区間にある頂点で1番目として使用できる… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.hamayanhamayan.com%2Fentry%2F2020%2F09%2F21%2F020458" title="Keep Distances [ACL Contest 1 D] - はまやんはまやんはまやん" 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-09-21 02:04:58 rich https://blog.hamayanhamayan.com/entry/2020/09/21/020458 1.0 100%