TopCoder SRM 526 Div1 - simezi

ゴミすぎるー

220.07 / Opened / Unopened
0チャレンジ
117位 2034 -> 2036

長方形のグリッドに、1マスに最大一匹カモがいる。
カモは、一列に最大一匹かつ、一行にも最大一匹しかいない。

このカモを移動させて、カモを同じ行または同じ列に連続するように並べたい。
(x,y)のカモを(p,q)に移動させるのにかかるコストは|x-p|+|y-q|に等しい。

最小でいくつのコストがかかるか、求めよ。

グリッドの幅、高さ≦50

重み最小二部マッチング。費用流だろうか。
さすがにeasyで費用流が出る訳がない。もう少し簡単に解けるはず。

暫く悩む。
一行または一列に1匹しかいないということは、
列を決めれば、列のどこにどのカモがくるかはgreedyでよい。

書いた。ちょっと遅い。送信。

二人がN個の石の山を使って次のようなゲームをする。

N≦50万くらい

お、ゲーム来た。解けそうな予感。
愚直なDPだとKが大きいのでO(NK)時間かかるとTLE.

素数は少ないから、なんか上手くDPできるのだろうか。
素数に移動できる場合とできない場合の境界あたりだけを考えればいいのかな？

50万以下の素数はおよそ4万個。
素数だけを考えてもTLE.

どうするんだろう。
てかこれって、素数の間が最大でも120くらいしか開かない。
んで、素数が必ず取れるときって先手が必ず勝つんじゃないだろうか（←嘘）

120以下のときだけDPして、そうじゃないときはgreedyにやればいいかな。

残り時間20分くらい。
実装できない。バグる。終了。

500書けなくてテンションだだ下がり。
落とせそうなコードもないしチャレンジせず。

かなりの人の500が落ちてる……
みんな嘘解法で出してたのか。

自分の250は通った。