AOJ埋め20

なぜか冬合宿のセットをやった．WorldFinal向けといえど鬼畜な幾何とかわけわからんやつとか以外は割と解ける．

2116 Subdividing a Land

平たく言うと，Pell Equationを解くという問題．50%以上は空白であるという制約から，パッキング問題にはならないようだ．
(1/2)*a^2-n*b^2が最小になるとしたら0になるときだが，0になりうるのは2*nが平方数のときしかありえない．
それ以外のとき，a^2-2*n*b^2=1となるときが次に最小となりえるが，これはPell Equationであり，平方数でない任意の2*nに対して解を持つ．したがってこの方程式の整数解を求めればよいことになる．
…で，問題はこれを解く方法なのだけど… 非常に難しい．まったく自明ではない．
とりあえず調べてみたらこんな記事があったので，これを参考にしてやった．
X^2-N*Y^2=1を解くには，まず√Nを標準連分数展開してやって，そのあとなんらかの漸化式を計算することで，X^2-N*Y^2=(-1)^n (nは連分数展開の周期) の解が求められる… らしい．このへんのギミックは複雑だったのでほとんど理解できていない．
nが偶数ならこれで終了してよい．nが奇数なら，(X+Y√N)^2を計算するといい… らしい．(ここを参考にした．なんでこれでいいのかはよく知らない)

Pell Equationは名前は知っていたけど正直ここまで難しいとは思っていなかった．数学科の人ならともかく情報系の人でこれを何も見ずにできる人ってほとんどいないんじゃないかな… とりあえずライブラリ化だけして見なかったことにしたい．
せっかく触れたのだからちゃんと理解しておくのが理想ではあるけど，時間も限られているし，なかなか踏み込むには躊躇してしまう．

2115 Life Game

MOD取りながら行列をかけていく問題．セルの数は最高でも100程度だし，普通にO(N^3logL)でべき乗していけばいい．
実装がちょっと面倒だけど工夫する．ラストでMODを取るタイミングにちょっとだけ注意．

2117 Connect Line Segments

ビット使ってTSP．

2119 Finding the Top RPS Player

問題文読んでやるだけ．

2114 Median Filter

2行ずつ見ていくタイプのDPでやった(記憶容量2^16*8程度)．
条件を満たせているかをチェックする必要があるのだけどその部分の実装が面倒．
あと，盤のサイズが2*2とか8*1とかだったら例外処理が必要になると思うのだけど，場合分けを書くのが面倒だったのでW,Hのどちらかが2以下だった場合は愚直に全探索するようにした．
愚直にやると条件を満たせているかのチェックで2^16*2^8*8*9程度かかって非常に遅くなってしまうのだけど，そこを適当に工夫したらなんとか間に合った．

2118 Oil Company

DPかと思ったりしたけどよくわかんない，2部グラフのフローも疑ったけどよくわかんない，ということで解説スライドを見たのだけど唖然とした．
マス目は2部グラフと見なせるから「最大重み独立点集合問題 ⇔ 最小コスト頂点被覆問題 ⇔ 最小カット ⇔ 最大流」…と帰結できてしまうらしい．なんというか，驚き…．
最小コスト頂点被覆が最小カットに帰結されるのがよくわからなかったのだけど，たとえばここを見るとなるほどなぁと納得できる．
うまいなぁと思ってしまったのだけど，2部グラフの性質をちゃんと把握できていれば自力でできたんじゃないかとも思えなくもない…．難しいけど良問だと思う．
ちなみにDPでもできるらしいけどどうやるのか全然わかりません．

2071 Web 0.5

巨大なクモの巣があるのだけど，ところどころ(100箇所くらい)歯抜けしているところがある．で，最初の位置から目的の位置まで最小距離で移動する，というもの．
基本的にダイクストラすればいいけど，クモの巣はでかいので愚直にグラフを構築すると当然TLEになる．
冷静に考えると，グラフの構造から，歯抜けしている辺の前後の位置(とあと最初の位置と目的の位置ともっとも内側の位置)だけをグラフにしてやって，あとは1本の辺で縮約してやればよいことがわかるから，縮約したグラフでダイクストラすればいい．