問題 atcoder.jp 考察 となっていて、区間として範囲が大きいので いもす法という手法を使って、単純に各区間の増減の累積和を取ることができないことが分かる。最初は各区間についてを一組としてまとめて、うまくソートなりなんなりをすれば良さそうと考えていたが そこからまったく分からなかった。公式解説によると 各区間のをまとめて考えるのではなく、を別々のものとして扱い、 いもす法の発想を少し応用した工夫をすることで解くことができる。こんな感じに区間を直線で表すと 日目を1からなめていったときにいずれかの区間のかと重なるまで 払う料金は一定で、かに出くわしたときに料金が変動することが分かるので …