JOI予選 - 魚の生息範囲
母上「そういえばさ、あれに変えたいんだけど。なんだっけ、バカチョンだっけ」
母上「そうそうそれ」(そうそれではない)
帰省してました
確か土曜に解いた問題です
ここだけの話、ビンゴがACできなくて飛ばした
魚の生息範囲 | Aizu Online Judge (AOJ 0580)
(問題は読んで)
最初、下手なdfsなどで被った範囲を全探索してK以上になったら値を加算するなどしようとしたのですが、それだと同じ範囲を何度も数えてしまうことになるので死んでしまった(一般に、人はこういったことをすると死んでしまいます)。
与えられる座標だけを使えばいいことはわかっていたので、X, Y, Z座標それぞれをマージしてソートしておいて細かい範囲に区分、全探索して (ここまでO(n ^ 3) )、その区間がK個以上の範囲に含まれているかをO(n)で判定するといいことに気がついたのでやった
一応想定解を見たらその通りみたいなことが書かれていて、はい。(その通りとは書かれていない)
こういうのも座標圧縮っていうんですね
はい