AOJ2510 双子の読書感想文 - ferinの競プロ帳

問題ページ
Twin book report | Aizu Online Judge

考えたこと

まず本を読む時間を最小化することを考える
感想を書く時間を無視して読書にかかる時間の方だけ考える
とりあえずソートしたい気持ちになる
いろいろ試してると大体 sum(r) で読書が終わりそう
sum(r)でできないのはsampleのように max(r) > sum(r) - max(r) となるときだけっぽい
rを降順ソートしたとする
max(r) <= sum(r)-max(r) ならば亜美がr[0],r[1],…,r[n-1]、真美がr[1],r[2],…,r[n-1],r[0]と読めばsum(r)で読書ができる
max(r) > sum(r)-max(r) ならば問題文中のサンプルのようにmax(r)の本を読んでいる間に残りの本を全部読むとしてmax(r)*2となる
感想を書く時間について考える
max(r) <= sum(r)-max(r) ならば sum(r) で読書が完了しているので sum(w) で感想を書けばよくこれが最適解
max(r) > sum(r)-max(r) ならば問題文中のサンプルのように読書中の空いた時間に感想を書いておきたい
したがってmax(r)*2 + sum(w) - (読書中に感想を書いた分) になる
読書中に感想を書ける時間は max(r)*2 - sum(r) が最大
最大にできるだけ近づけられるようなwの部分集合の取り方を知りたい
これは部分和DPをすれば求まる
O(nsum(w))の状態を取るとだめだが冷静に考えると部分和の最大はO(max(r))なのでO(nmax(r))で求められる

解法

max(r) <= sum(r)-max(r) ならば sum(r) + sum(w)
max(r) > sum(r)-max(r) ならば max(r)*2 + sum(w) - (部分和DPで求めた値)
部分和DPはO(nmax(r))でできる

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dp[1010][3010];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  while(true) {
    int n;
    cin >> n;
    if(!n) break;
    VI r(n), w(n);
    int sumr = 0, sumw = 0;
    int ma=0, idx=-1;
    REP(i, n) {
      cin >> r[i] >> w[i];
      if(ma < r[i]) {
        ma = r[i];
        idx = i;
      }
      sumr += r[i];
      sumw += w[i];
    }

    if(ma <= sumr - ma) {
      cout << sumr + sumw << endl;
    } else {
      memset(dp, 0, sizeof(dp));
      dp[0][0] = 1;
      REP(i, n) REP(j, 2*ma-sumr+1) {
        dp[i+1][j] |= dp[i][j];
        if(j+w[i] <= 2*ma-sumr && i != idx) dp[i+1][j+w[i]] |= dp[i][j];
      }

      int tmp = -1;
      REP(i, 2*ma-sumr+1) if(dp[n][i]==1) chmax(tmp, i);

      cout << ma*2 + sumw - tmp << endl;
    }
  }

  return 0;
}