yosupo https://blog.hatena.ne.jp/yosupo/ よすぽの日記 https://yosupo.hatenablog.com/ 1000なだけあって非常に悩んだけど、面白かった。 すべての道は交差しないというのが非常に強い制約。 まずは円環はNGなので切って伸ばして列にする。 これのおかげで区間DPとして考えられる。 また、n % 2 == 1の場合は答え1になる事と(r-l) % 2 == 0となる橋は全部無かった事にしていいことが分かる。これを無視すると一気にコーディングが楽になる。 f([l, r]) := 区間[l, r]の橋の渡し方の通りとすればいい なのでこれで状態数O(N^2)の区間DPになる ここで、f([l, r])を求める方法について考える。これは、橋が交差しないという制約を利用すると高速に求められ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fyosupo.hatenablog.com%2Fentry%2F2014%2F12%2F29%2F224402" title="AOJ-ICPC2405 姉妹港 - よすぽの日記" 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 2014-12-29 22:44:02 rich https://yosupo.hatenablog.com/entry/2014/12/29/224402 1.0 100%