SRM591 Div2 1000 の解説

今回のDiv2Hardは、正答者が6人/790人のなかなかハードな問題でした。
回答方針をDPに据えるところまで辿り着く人は多かったようですが、メモ化の仕方やその利用方法になかなか工夫が必要で、実装は容易ではありません。
以下に、正解者の回答をもとに理解した内容をアウトプットしていきます。



・問題の概要
与えられたN個の自然数（数列vとする）を、以下のルールを満たすよう二つ（first と second）に分ける方法はいくつあるか？( firstの和をsumF、secondの和をsumS とする）
　1. sumF > sumS
　2. firstの任意の要素について、secondへ移動させると sumF < sumS となる。

・DPによる回答
dp[i] := sumF = i となる分け方の数、と定義します。もちろん、これをただ更新するだけでは答えを求めることはできません。そこでまず、与えられたN個の自然数を降順にソートします。このとき、v[i]について考えると、sum = v[0] + v[1] + … + v[i-1]　として
 Σ dp[ 0 <= j <= max ] = （v[i-1] までを使ったfirstの作り方の数）、となります。
（この部分は、{ 4,3,2,1 } などで実際にやってみるとよく分かります）
すると上記の範囲のそれぞれの j に対して、v[i]を加えてsumF > sumSが成り立ち、v[i]を移動させることでsumF < sumSが成り立つならば答えにdp[j]を加えていって良いことになります。なぜならば、vを降順にソートしているため、v[i]の移動で条件を満たすならば、v[0] ~ v[i-1]の移動でも必ず条件が成り立つからです。

・計算量
この解法では、vに対するループの中で更新するdpの数が最悪1つずつ増えていくので、最悪計算量はO(50^3)で楽々間に合います。

long long count(vector <int> v){
  long long dp[300001];
  long long res = 0;
  int sum = accumulate(v.begin(), v.end(),0);
  int tmp_sum = 0;
  dp[0] = 1;
  sort(v.begin(), v.end(), greater<int>);
  for(int i = 0; i < v.size(); i++){
    for(int j = tmp_sum; j >= 0; j--){
      if(dp[j]){
     dp[j+v[i]] += dp[j];
     if(2*(j+v[i]) > sum && sum > j*2) res += dp[j];
      }
    }
    tmp_sum += v[i];
  }
  return res;
}