TopCoder SRM 462

Codejamの敗戦直後にSRM……
なんだかどっちもぱっとしない成績だなあー。

Result

132.06 / Opened / Unopend
+0(1撃墜2ミス)

362位
1546->1555

Easy PotatoGame

問題

n個のジャガイモをTaroとHanakoが交互に食べるゲームをする。
一度に食べる数は4^k個(k≧0)(1,4,16,...)でなくてはならない。


先に4^k個のジャガイモを食べることのできなくなったプレイヤーが負けであるとき、
互いに最善をつくした場合どちらのプレイヤーが勝つかを求めよ。

n≦10^9である。

試行錯誤

うげーゲームだorz
Nimっぽい感じなのだろうか。n=15くらいまで手で書いてなにかわからないか試してみる。
なにもわからない。


mod 4で考えるのだろうか。4進法にしたときの桁でNimができたり……しない。
4進法の各桁の和とか……関係なさそう。


n=10くらいでゲーム木をかいてみる。別にヒントにならない。
どうやって考えたらいいんだろう。全く方針が立たない……


n=1000くらいまで力技でプログラム書いて求めてみよう。
バグってはまった。メモ化の配列100までしか取ってなかった。


書けた。
あれ?1,0,1,1,0って周期5で並ぶのか?
n=10000で反例がない。何故だ……送信。

Medium TwoSidedCards

600点問題。Easyで手間取りすぎて時間が余り残っていない。

問題

N枚のカードの表にTaroが1からNのそれぞれ異なる整数を書き、裏にHanakoが1からNのそれぞれ異なる整数を書く。
i番目のカードに書かれる数はTaro[i],Hanako[i]であたえられる。


その後、カードを1列に並べるとき、異なる並べ方の場合の数をmod1,000,000,007で求めよ。
ただし、並べ方が異なるとは、見えている面の数字の列が異なることをいう。


n≦50である。

試行錯誤

うーん、確率だからやっぱりDPなのかなあ。
とりあえず表裏に書かれている数が全部等しい場合はn!通り。
表裏に書かれている数が全部異なる場合は……?


どうやら書かれ方によって場合の数は異なるようだ。
んと、巡回群の位数が関係あるのかな?
じゃあn枚で、位数もnの場合を考えてみよう。
n=2だと4通り、n=3だと24通り??n=4だと……?


よくわからない。これもプログラム書いて求めてみるか。
4,24,180,1620,17100,...のようだ。なんぞこれー。規則性見えない。
n=4で180?あれ、なんか手計算と合わない……


とかやってる間に時間切れ。

Challenge Phase

  • n%5==5とやってるコードを見つけたので落とす。
  • 10^9までループしてるっぽいコード見つけたので10^9を与えてみる。Failed.うそーwww間に合うのかよこんなん。
  • なんかよくわからんがmod5とってなさそうなの見つけたので10^9投げてみる。Failed.

で、+0.

System Test

250通った。