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) の値を答えに乗じる.