yukicoder No.54 Happy Hallowe'en

ツボクラさんがSRM 502のmedはこの問題の類題で解いたとつぶやいていたので解いてみました。
こっちの方が3倍位難しく感じる…

問題

No.54 Happy Hallowe'en - yukicoder

解法

medと同じように何らかの基準を見つけ,その基準通りもらえる家の順番を並べ,dpしていく。
しかしこの問題の「基準」を発見するのが結構難しい。結論から言うとが小さい順にt並べれば良い。以下でその理由を説明する。

pとqのどちらを先に並べるかを比べてみる。すなわち,

①..., p, q, ...
②..., q, p, ...

という２つの家への訪問の仕方について,どちらのほうが有利かを考える。

それぞれの場合で,p/qまで訪問している間に手に入れたお菓子の数をkとする。p, qの両方の家でお菓子をもらえない場合,pかqのどちらかでしかお菓子がもらえないことが確定している場合については考慮しなくて良い。
これは,今考えているのは「pとqの一方は選ぶことができるとして,どちらを先に選択するのが有利か」ということを考えている(前のmedの問題と同じように,訪問する家の集合が決まっているときにどのような順番にすべきかということを考えている)のでpとqどちらかしか訪問できないというのは対象外だからです。

さて,このときどちらの家を先に訪問するのが有利なのか考えてみます。①の場合は

となれば両方の家からお菓子をもらえ,②の場合は

となれば両方の家からお菓子をもらえます。

ここで①の条件のほうがゆるいための必要十分条件は

よって,上記の式が成り立つ時は
qを先に訪問してpとq両方の家からお菓子をもらえる pを先に訪問してもpとq両方の家からお菓子をもらえる

ということが成り立ちます。よって,この場合はpを先に訪問するほうが両方の家でお菓子をもらえる可能性があり有利です。よって,の値順にソートすれば良いということです。

以下ソースコード

const int MAXN = 10010;

struct present {
    int v;
    int t;
    present() {}
    present(int v, int t) : v(v), t(t) {}
    bool operator<(const present& rhs) const {
        return v+t < rhs.v+rhs.t;
    }
};

present p[MAXN];
bool dp[2][2*MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        int v, t;
        cin >> v >> t;
        p[i] = present(v, t);
    }
    sort(p, p+N);
    memset(dp, 0, sizeof(dp));
    dp[0][0] = true;
    for (int i = 0; i < N; i++) {
        int cur = i%2;
        int tar = cur^1;
        for (int t = 0; t <= MAXN; t++) {
            if (!dp[cur][t]) continue;
            dp[tar][t] = true;
            int tmp = t+p[i].v;
            if (t < p[i].t) dp[tar][tmp] = true;
        }
    }
    int ans = 0;
    for (int i = 0; i < 2*MAXN; i++) {
        if (dp[0][i] || dp[1][i]) ans = i;
    }
    cout << ans << endl;
    return 0;
}