AT274 https://blog.hatena.ne.jp/AT274/ あっとのTECH LOG https://at274.hatenablog.com/ 競プロ 問題原文 atcoder.jp 問題要旨 日本列島は横長い島であり、地点 の高さは である。 また海面の高さは０であり、海面より高い部分を陸地、陸地が１つ以上連続している区間を島と呼ぶ。 海面が徐々に高くなっていくと、島の数が増減し、最終的には０になる（日本沈没）してしまうが、それまでに島の数は最大でいくつになりうるか？ 解法 ある時間になったら辺が消えて〜みたいなイメージ。そしてそういう問題は、辺を切っていくよりも辺を追加していくと考えたほうが扱いやすい。 よって初期状態は完全に沈没しきった状態とし、そこから時間を巻き戻すように地点を追加していく。 地点の追加においては、その両隣が陸なら島の… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fat274.hatenablog.com%2Fentry%2F2020%2F03%2F22%2F165503" title="JOI難易度６ 日本沈没 - あっとのTECH LOG" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=%20%201%20%5Cleq%20N%20%5Cleq%2010%5E%7B5%7D Hatena Blog https://hatena.blog 2020-03-22 16:55:03 rich https://at274.hatenablog.com/entry/2020/03/22/165503 1.0 100%