AGC054 B - Greedy Division (800)
コンテスト中の考察
全ての順列を試すわけにはいかないしbitDPにもできない
いったん同じ重さになるみかんの分け方をDPで求めてみる
$ dp[i][j][k] でi番目まででj個用いて重さkになる組み合わせの数
これが答えに一致するのでAC
$ \sum_{i=1}^{n} dp[n-1][i][sum/2] i! (n-i)! が答えになる
ある取り方を決めれば高橋君と青木君がそれぞれその順番で取ることになる順列を決めることができる
片方がi個取るともう一方はn-i個でそれぞれの並べ方だけあり得る順列が増える