Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

座標圧縮を使う問題

座標圧縮は座標圧縮して数えて終わりもありますが、問題を解く前の前処理としてプラスアルファである場合が多いような気がしました。

  • xもyの重複のない点群は座圧くさい
  • せいぜいN(1000オーダ)しかないものに帰着させる

ということがポイントかと思いました。

問題

ABC8 D

D - 金塊ゲーム

問題: WxHの平面に金塊が敷き詰めてあり、その中にN(30程度)個のクレーンがある。クレーンを起動させると、自分の座標と、上下左右の連続した金塊を得る。得られる金塊の最大数を求めよ。

最初は座標圧縮して、外回りに近い金塊から貪欲にとっていくものかなぁと思いましたが、i番目のクレーンを起動した時に残りの領域が4つに分解されて、それぞれ独立なので(連続してる金塊しかとれないから)、DPで終わり。こういう問題は、どの2つのクレーンもx,yともにコンフリしないことが条件になってる。F - Enclosed Pointsも同じ条件があって、座標圧縮を前処理として行う。

AOJ0531

ペンキの色 | Aizu Online Judge

ザ・座標圧縮。座標の数はせいぜいマスキングテープの数程度しかないことを利用して圧縮する。

AOJ0536

シャッフル | Aizu Online Judge

問題: 1からN(109)が書いたカードが積み上げられており(1が一番上)、(a,b)で表される操作をM(5000)回行う。この操作は、上から[1,a][a+1,b][c,N]枚を、[c,N][a+1,b][1,a]のようにシャッフルする。M回後、pからqの間にあるr以下のカードの枚数を答えなさい。

Nが大きいので、どうにかしてMに問題を圧縮出来ないか考えたい。直感的には、aとbの種類がM個程度しかないので、なにかありそう。ここでは、毎回切った区間によって毎回の状態を表現していく。この区間の数は切った数の定数倍程度しかないので、間に合う。