ライトニングまさかり

その馬肉で和同開珎の刺繍をしよう

Topcoder SRM575 Div2

easyとmedium解いた。Hard読んでない。

なんか灰から緑になった。エコい。

 

-easy(250)

読解が若干手間取った。

要するに数え上げ。

数列の内2つの要素をスワップしてできる配列がいくつになるか数える。

全く同じ数列は数えない。

数列の長さ2<=L<=47。

とりあえずスワップした数列は(L-1)*L/2個ある。

このうち同じものを消していけばよい。

数列中の同じ要素を数えて先ほどの数から引いていく。

最後に初期値より小さくなっていたら1を足してreturn。

多分穴あるけどsample全部通ったので提出。通る。激アツ。

 

-medium(500)

2人で交互に整数nの約数の1つを選んでnから引いていき、

引いたときに素数になった方が勝つゲーム。

互いに最善手を選ぶ。

つまり素数にできるときは必ず素数にするので、

深さ優先的に調べれば勝ち負けがわかる。

単純に数えるとTLEするのでメモ化する。

多分DPできるかもしれないけど実力不足で思いつかない。

実装に手間取って200点ちょい。激寒。