2009 TCO Round 1

日曜日午前2時開始だったので，3/7（土）にあった集合論ゼミの後，その場所（自宅ではない）で参加．
さすが，「ネトゲ」と言われるだけあり，場所を選ばない．

250:
ある数を連続する非負整数の和として表す方法を求める問題です．
非負整数の長さが100を超えない場合を調べるという問題設定のため，
長さで場合分けして高々100通り調べればよく，素直に解きました．
235.63

500:
ランダムにM個とって，K番目に小さい数がNである確率を求める問題です．
k個がn以下，(m-k)個がn超となる確率を
n=N-1,Nについてk,mでDPし，差を取れば出ます．
条件に端を含むかで混乱しつつも，それを抑えて書き，
399.75

1000:
3マス以上進み，直角に曲がり2マス以上進むコマで，盤上に書かれた文字を与えられる文字列の順で踏む方法の数を求める問題です．
文字列のうち何文字目までかと今どこにいるかでDPすればいいのですが，
あまりに動きが激しいため，普通にループして和を取ると更新に盤の大きさぐらいの時間がかかります．
よって，長方形についての和を高速に計算するための前処理（なんて呼ぶのでしたっけ）を書くことになります．
境界のメモリの取り忘れなどでsegmentation faultしつつも，書き上げました．
455.38

Challenge:
テストケースが親切すぎてやることがないかと思われたのですが，
他の人はいろいろ撃墜していました．
1000でTLEなものをすぐに探すべきだったのかもしれません．
+0

合計: 1090.76
部屋内2位
総合82位
Rating: 2499→2554