TopCoder SRM 475 (Div 1)
Result
146.39 / Opened / Unopened
0チャレンジ
256位
1574->1592
底辺黄色の安定感がやばい。
Easyが遅すぎて話にならない。Medium書く時間ない。
Easy RabbitStepping
問題
一列にN個のマスがあり、左から0,1,...,N-1と番号がついている。それぞれのマスの色が与えられる。
ここに各マスに最大1匹になるようr匹のウサギがランダムに置かれ、以下のようなゲームをする。
- 0番目のマスにいるウサギは右に動く
- N-1番目、N-2番目にいるウサギは左に動く。
それ以外のマスでは、
- 白のマスにいるウサギは左に動く
- 黒のマスにいるウサギは右に動く
- 赤のマスにいるウサギは直前のマスに（ただし最初にその赤のマスにいた場合は左に）動く
次に、一番右のマスを取り除きN:=N-1とする。Nが2以下になるまでこの操作を続けるとき、残るウサギの数の期待値を求めよ。
N≦17,r≦Nを満たす
試行錯誤
サーバ重くてアリーナ入れない……
うげ、300,600,900のセットとか自分には一番きつい。
重くて問題が開けない。1分くらい反応がないので再接続しようとして消したら問題文のウィンドウが出てきたorz
再接続もなかなかできねーorz
再接続おｋ.
なんだこの300の問題文の長さorz
Nは17...愚直にシミュレートできるだろうか。17C8っていくつ？
計算……できぬ。電卓曰くおよそ24000.
ウサギは初期位置が決まれば状態は全部一意に決まる。んじゃあ全ての初期状態の組み合わせをみてやればいいんじゃないだろうか。
next_permutation使って書き始める。
ん、赤は直前のマスだと？？そんな面倒な……
Easyだしもっといい解法があるんじゃ……偶奇とか関係ないかなー。
よくわからない。。。
直前の位置を持っておいてシミュレーション書こう。。。変数全部なおす。
書いた。あれー数字あわないぞ？
ウサギが2匹以下になるまでシミュレートだよな？
ウサギが2匹以下……に？シミュレーション終わってから、2匹以下なら終了？
do...while文？？
あれ？すると別のサンプルあわないぞ？
問題読み直す。
ウサギじゃなくてマスの数が2以上じゃん。
はー。訂正。
あれまた一つサンプルあわない。do...whileのままにしてた。修正。
漸くサンプル通った。サンプルかなり親切なのでそのまま送信。
酷い点数。
Medium RabbitIncreasing
問題
ある国の、1年目の7/1に一組のウサギのつがいがいる。
毎年3/1に満一歳以上のつがいはオスとメスの子供を生む。
毎年4/1にオスとメスのウサギはつがいになる
leavingで与えられた年の11/1には、つがいの半分（切り上げ）は国の外へ出る。
k年目の12/1に国内にいるウサギの数をmod1,000,000,009で求めよ。
leavingの要素は50個以下、kは10000000以下である。
試行錯誤
Easyに40分取られるとかどんだけバカなの……orz
フィボナッチ数を求める問題？？と思ったらiヶ月後にウサギのつがいが半減するらしい。
でもk≦10000000だしなんかDPでいけそう。
というかDPでTLEするかどうかだけでも試さないとチャレンジが勝負にならない。
書く。
日付わかりにくいよー。あれサンプルあわない。
プリントデバッグ。焦ってきた。
7/1に最初のつがいがいて、3/1に満1歳以上が子供を生んで……ややこしい！！最初は1年目？0年目？？？1年目っぽい。
混乱しながらコード修正→コンパイルの無限ループしてたら時間おわた。
ちゃんと漸化式たててからコードかけよなクズが！！！
Hard
Unopened.
Challenge Phase
Easyはかなりサンプル親切だったから落とす人いないだろうなー……
Mediumから見る。うーん合ってそう。
Easy絶対落とす奴一人くらいはいるはず。頑張って見つけよう。
……
見つからない。終了。
System Test
300通った。色々と終わっている。
