GCJ 2014 Round 2

2014-06-01 | [Competitive programming]

A

よくある問題．注意点は

1. 問題文を正確に読む (more than 2 を not less than 2 と解釈しない)
2. 送るファイルを間違えない

B

JOI 春合宿で既出．

C

最初本気でフローを高速化するものと思っていて，まったく解けず (愚直なフローで Small だけ通した），残り 30 分を切った地点で最小カットを使った解法に気づき， 書いてみたら愚直なフローと答えが一致することがわかったので Large を送った．

D

trie のノード P に対して，そのノード以下で「文字列の端」となっているノードの数を w(P) とする．

trie を実際に書いてみると，X の値はただちに Σmin(N, w(P)) であることがわかる．

Y の値は，trie の根から順に，次の要領で求める．(考えているノードを P とする)

1. w(P) <= N のときは，(w(P))!
2. それ以外のときは，N 種類のサーバーを各子ノードに，どのサーバーも 1 回以上使うという条件で割り当てる場合の数をまず求める．(DP, 包除原理などが使える) ここで，子ノード Q には min(N, w(Q)) 個のサーバーを割り当てる． さらに，各子ノード Q に対して w(Q) の値を答えに乗じる．