■

09JOI予選5

https://atcoder.jp/contests/joi2009yo/tasks/joi2009yo_e

概要:n(<1e9)枚のカードをm(<5000)回シャッフルする。シャッフルは以下の通り

(1~x)(x+1~y)(y+1~n)->(y+1~n)(x+1~y)(1~x)

この時、シャッフル後にp枚目からq枚目にr以下のものは何枚あるか。

解法:順序を保つブロックで考える（座圧的な）。各シャッフルでブロックが高々二個増える。ブロックの左端の情報のみでシャッフルを行い、最後にブロックごとに[p,q]との交差であってr以下になるものを数えればよい。

実装:半開区間で整理するのがよい。添字に関してよく整理してから実装する。

感想:複数の処理がある。特に区間の交差の処理でもたついた。何度か書くと良さそうな問題。

09JOI本選5

https://www.ioi-jp.org/joi/2008/2009-ho-prob_and_sol/2009-ho.pdf#page=12

概要:二つの建物があり、それぞれW_k*H_k（それぞれ500以下）マスの部屋の塊で構成される。各部屋には数字が振られており、一つ入り口がある。ある数字N_kが与えられた時に建物kにおいて、今いる部屋と隣接していて、N_k以下の数字が振られている部屋に移動することができる。二つの建物で合わせてR以上の部屋を訪問するために必要なN_1+N_2として考えられる最小値を求めよ。

解法:建物kに対してnum_k[r]=r個訪れるのに必要な番号の最小値　を求める。

まず、隣接するコストで最も小さいものをmとし、m以下の部分を掘り進める。この時の部屋の数をrとし、num_k[r]=mとする。（間は埋める）

このあとはnum_1[x]+num_2[R-x]の最小値を求める。

実装：priority_queue

感想：４より簡単のような。