はまやんはまやんはまやん

hamayanhamayan's blog

再帰的ケーキ [yukicoder No.777]

https://yukicoder.me/problems/no/777

考察過程

1. 今回の問題のように包含関係を使うものは、上における場合にケーキの間に有効辺を貼るとDAGになるので、DPになりやすい傾向がある
2. DPで考えてみると、遷移の数が多いので、なんとかしたくなる
3. こういうときの策としては色々あるが「遷移をへらす」「遷移をまとめる」で考えてみる
4. 「遷移をへらす」より「遷移をまとめる」方が簡単なので、こっちで考える
5. あるケーキへの遷移は、Aが小さく、Bも小さいものだが、これはとある区間にできそうなので、まとめられそう
6. ここでDPのテクを2つ使うことでなんとかする「選択するものを最初にソートしておくと、DPできたり、状態を同一化できたりする」と「配列を使い回すことでメモリ使用量を節約する(500^3は256MBに乗らない)」
7. このテクを使うことを考えると「dp[i] := 一番上の奥行きがiのケーキの最大カロリー」を更新していくことで答えが出せる

解法

https://yukicoder.me/submissions/307842

DPをする。
dp[i] := 一番上の奥行きがiのケーキの最大カロリー
このDPの更新のために、奥行きを座圧しておこう。
 
DPのテクとして「選択するものを最初にソートしておくと、DPできたり、状態を同一化できたりする」を使う。
Aが小さい方からまとめて処理して、DP更新をする。
この処理のために「buf[a] := A[i]=aであるiの配列」を作って、aの小さい方から処理をしていくことにする。
こうしておくことで、これより前に処理されたケーキはすべてAが小さい条件を満たすことになる。
 
次に「配列を使い回すことでメモリ使用量を節約する(500^3は256MBに乗らない)」を使う。
あるAについて、ケーキを使うかどうか考えていく。
奥行きがb[i]であるケーキは、「dp[j](j<b)の最大値+C[i]」によってdp[i]を更新できる。
つまり、更新される要素は各ケーキについて1つだけになる。
なので、dp配列を使いまわすことで、更新を高速に行える。
 
あとは、「dp[j](j<b)の最大値」を高速に求める方法だが、これはdpをセグメントツリーにしておけば実現できる。

int N, A[201010], B[201010], C[201010];
SegTree<ll, 1 << 18> st;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i] >> B[i] >> C[i];

    vector<int> v;
    rep(i, 0, N) v.push_back(B[i]);
    sort(all(v));
    v.erase(unique(all(v)), v.end());
    rep(i, 0, N) B[i] = lower_bound(all(v), B[i]) - v.begin();

    map<int, vector<int>> buf;
    rep(i, 0, N) buf[A[i]].push_back(i);

    fore(p, buf) {
        auto& v = p.second;
        vector<pair<int, ll>> nxt;
        fore(i, v) {
            ll c = st.get(0, B[i]) + C[i];
            nxt.push_back({ B[i], c });
        }
        fore(p, nxt) st.update(p.first, max(p.second, st[p.first]));
    }

    ll ans = st.get(0, N);
    cout << ans << endl;
}