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