Codeforces 8VC Venture Cup 2016 - Elimination Round F. Group Projects

通した人のコードを眺めてたら大体何をしてるのか分かったので解説を書きます。

codeforces.com

解法

配列はソートしておく。

次のようにグループ分けするのではなく、 f:id:pekempey:20160215155614p:plain

次のようにグループ分けすると考えても imbalance は変わらない。 f:id:pekempey:20160215155625p:plain

imbalance は図に書かれた値の総和である。

f:id:pekempey:20160215165242p:plain

このことを用いると次のような DP ができる。

  • dp[ i番目まで見た ][ j 個の区間が open ][ imbalance ] := この状態に至るパターン数

遷移パターンは open, close, pass, open and close の 4 通り。順に説明する。

open

f:id:pekempey:20160215165927p:plain

close

どの区間を閉じるかで open 通りある。

f:id:pekempey:20160215165840p:plain

pass

ai をどのグループに入れるかで open 通りある。

f:id:pekempey:20160215165844p:plain

open and close

つまりグループに要素がひとつしかないとき。 imbalance は変化しない。

f:id:pekempey:20160215165847p:plain


Codeforces 8VC Venture Cup 2016 - Elimination Roun ...

DP テーブルの置き方までは素直だけど imbalance の扱いが技巧的。