No.54 Happy Hallowe'en

No.54 Happy Hallowe'en - yukicoder

• DP をやる前に、訪れる順番を決めておく問題。
• 最適な順番を最初から考えて詰まってしまった。
• 「a,b どちらが先でも同じだから、そうでないケースを考えよう。」って思考ができればよかったのかも。

class HappyHalloween {
public:
    void solve(void) {
            int N;
            cin>>N;

            int maxT = 0;
            int maxV = 0;
            vector<pair<int,int>> candy;
            REP(i,N)
            {
                int v,t;
                cin>>v>>t;
                maxT = max(maxT,t);
                maxV = max(maxV,v);
                candy.emplace_back(v,t);
            }
            // 現在の candy の個数を C とするとき
            // C < T[a], C < T[b] として家 a, b を訪れるケースを考える。
            // a,b どちらが先でもキャンディをもらえるならどちらの順でもよいが、
            // そうでないケースを考える
            //
            // 1. a -> b 順でキャンディがもらえるとき     C+V[a] < T[b]
            // 2. b -> a 順ではキャンディがもらえないとき C+V[b] >= T[a]
            //
            // 1,2 が同時に成り立つときは
            //
            // V[a]+T[a] < V[b]+T[b]
            //
            // となる。よって V[i]+T[i] でソートした順訪れれば良い。
            //

            // O(N*log(N))
            sort(RANGE(candy), [](const pair<int,int> &a, const pair<int,int> &b){
                    return a.first+a.second < b.first+b.second;
                });

            // dp[C] := キャンディを C 個もらえるか？
            vector<bool> dp(maxV+maxT+1,false);

            // O(N*maxT)
            dp[0] = true;
            REP(i,N)
            {
                int v = candy[i].first;
                // i のときの dp 更新を伝播させないために逆順にやる
                // C < T[i] のときしかもらえないので T[i]-1 から
                for (int C = candy[i].second-1; C >= 0; --C)
                    dp[v+C] = dp[v+C] | dp[C];
            }

            int C;
            for (C = dp.size()-1; C >= 0; --C)
                if (dp[C])
                    break;
            cout<<C<<endl;
    }
};