TopCoder SRM 625

2014-06-19 | [Competitive programming]

250

文字列の長さが奇数か，偶数かで場合分けして，そもそも回文が可能かまず確かめる．不可能なら 0.0 が答え．

可能な場合は，回文の場合の数と，並べ方全部の場合の数を double で計算して確率を求める．

500

ゴールから逆算してフロー流せば解けそうと思ったけど落ちた＞＜

コンテスト中，フローライブラリがまちがっていて TLE になってかなり焦った（直した）（結局落ちた）

900

場合の数を求めるときに，「cluster の構成法」「cluster の置き方」を別に考える． cluster の構成法とは，「各 cluster において，どの人が，どういう順番で座っているか」のことである． cluster の位置だけを変えた座り方は，隣接関係 (x さんが y さんの左/右に座っている) が同じ限り，ここでは同一視する．

前者は DP で求める．DP のキーは「やってきた人の数」「現在の cluster の数」とする． 1 人増やすとき，「既存の 2 つの cluster をくっつける」「既存の cluster の隣に座る」「cluster と離れて座る」の 3 通りがある． それぞれ cluster の数は -1, 0, +1 に変化する． 現在の cluster の数を C とすると，それぞれ C(C-1), 2C, 1 通りの方法で次の状態に移動する． 当然，cluster の数が上限 G を越えてはいけない．

後者は，cluster の数が決まれば，各 cluster の長さに関係なく決定できる．そのため DP の途中では完全に無視してよい．

N = K のときの処理が若干面倒だが，このときは最後の人は K-1 人が座った後の唯一の空席に座る他ないので，K = N-1 としてよい．

結果

challenge まったくやる気しなかったのでほとんど読みすらしなかった

oxo 662.34 (16 位)

rating: 3047 -> 3066