読者です 読者をやめる 読者になる 読者になる

SRM 651 Div2 Medium FoxAndSouvenirTheNext

問題

今回は解説リンクが開けなかったのでリンクはなし.

価値value[i]の品物がn個与えられた時,品数が等価で, 価値の総和が等価な2分割が出来るかどうかを判定する問題.

解答

  • 典型的なDPの問題.
  • value[i]の総和をsumとするとsumあるいはnが奇数の時は等価な分割が出来ない.
  • dp[sum_value]={num_items}はsum_valueを作れる品数集合を保持した配列とする.
  • i-1個までの品物を使ったdp配列があればi個までの品物を使ったdp配列を簡単に作ることが出来る.
  • n個までの品物を使ったdp配列を計算しdp[sum/2]n/2を含む場合,条件を満たす分割が存在する.
using namespace std;

class FoxAndSouvenirTheNext
{
public:
  string ableToSplit(vector <int> value)
    {
      vector<set<int> > dp(2600, set<int>());
      int n = value.size();
      int i, j;
      for (i = 0; i < n; i++) {
        dp[value[i]].insert(1);
        for (j = dp.size()-1; j >= 0; j--) {
          for (auto k:dp[j]) {
            dp[j + value[i]].insert(k + 1);
          }
        }
      }
      int sum = accumulate(value.begin(), value.end(), 0) ;
      if (sum % 2 != 0 || n % 2 != 0) return "Impossible";
      if (dp[sum/2].find(n/2) != dp[sum/2].end()) return "Possible";
      return "Impossible";
    }
};