JOIG 春合宿 2023 day2-1 Smartphone (2D, 難易度 8)

JOI ではお馴染みの「 個の区間を扱う問題」。ただし実装がしんどかった。僕は区間を set で管理する方法で実装した。

• 問題へのリンク
• editorials

問題概要

制約

• 
• 
• 
• 

考えたこと

いかにも貪欲法の香りが漂っている問題ですね。この手の問題では、

---

1. 個の区間を終端の早い順にソートする (区間スケジューリング問題など)
2. 1 日目, 2 日目, ... の順にとるべき行動を考える

---

といったアプローチが有効ですね。2 番目の解法は公式解説にあるので、ここでは 1 番目の解法で解いてみます。

終端の早い順にソート

個の区間に関する問題では、区間の終端の早い順にソートして考えることで上手くいくことが非常に多いです。今回もバッチリはまります。次の素朴な方法が最適解を導きます。

---

終端が早い区間から順に、まだ印のついていない日について、前から順に最大 日分埋めていく

---

念の為に、この手のものを証明できるようになっておくと良さそうです。例によって「交換しても悪化しない」というテクニックで証明します。

ある区間について、ある印のついていない日を飛ばして、印をつけていったような最適解が存在したとしましょう。この解に対して、「印のついた日数」を小さくすることなく、印のついていない日を飛ばさないような解へと変形できることを示します。このような論法は本当に頻出ですね。

さて、今考えている区間を 、飛ばした日を としましょう。場合分けして考えます。

---

1：その後の区間 の中に、日 に印をつけるものがないとき

• この場合は単純に、区間 についた印のうち最後の日 [tex: e を選ぶ
• æ—¥ ã‚’ swap します

2：その後の区間 の中に、日 に印をつけるものがあるとき

• 区間 についた印のうち最後の日を とする
• このとき、区間 もかならず日 を含むことに注意しましょう (これを保証するために区間の終端でソートしました)
• 区間 と区間 とで、日 の印を swap します

---

以上の方法を繰り返すことで、「印のついた日数」を小さくすることなく、印のついていない日を飛ばさないような解へと変形できます。

解法

あとは、次の解法を実装できればよいことになりました。

---

終端が早い区間から順に、まだ印のついていない日について、前から順に最大 日分埋めていく

---

この方針の実装で満点をとるのは、実際のところ結構大変です。方針としては、「すでに印のついている日」を区間の集合とみなして、set<pair<int,int>> 型で管理します。

これに対して、前から順に最大 日分埋めていく際に、これらの区間を合併したりなどを繰り返していきます。結局全体として の計算量で実装できます。実際のコードを読むと早いと思います。

詳細は「区間をsetで管理するテク」などと調べると大量の資料が見つかります。たとえば ABC 256 Ex の解説に、その解説があります。

コード

#include <bits/stdc++.h>
using namespace std;
using pll = pair<long long, long long>;
const long long INF = 1LL<<60;

int main() {
    long long res = 0;
    
    // 入力
    long long N, K;
    cin >> N >> K;
    vector<long long> A(N), B(N), C(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i] >> B[i] >> C[i];
        ++B[i];
    }
    
    // 区間の番号を終端が早い順にソートする
    vector<int> ids(N);
    for (int i = 0; i < N; ++i) ids[i] = i;
    sort(ids.begin(), ids.end(), [&](int i, int j){return B[i] < B[j];});
    
    // 「印のついた日」を、区間の集合とみなして管理する
    set<pll> S;
    S.insert(pll(-INF, -INF)), S.insert(pll(INF, INF));  // 番兵
    for (auto i : ids) {
        // 最大 C[i] 日分埋めていく
        while (C[i] > 0 && A[i] < B[i]) {
            // 区間の始点 A[i] が区間 inter1 に含まれる可能性があるが、
            // 区間 inter2 の始点は A[i] より右にあることを保証する
            auto inter2 = S.upper_bound(pll(A[i], INF));
            auto inter1 = inter2;
            --inter1;
            
            // マージする
            long long newA = A[i], newC = C[i];
            if (A[i] <= inter1->second) {
                // A[i] が区間 inter1 に含まれているとき
                if (min(inter1->second + C[i], B[i]) < inter2->first) {
                    // 最大 C[i] 日新たに印をつけても、区間 inter2 に被らないとき
                    res += min(inter1->second + C[i], B[i]) - inter1->second;
                    newC -= min(inter1->second + C[i], B[i]) - inter1->second;
                    newA = min(inter1->second + C[i], B[i]);
                    pll p(inter1->first, min(inter1->second + C[i], B[i]));
                    S.erase(inter1);
                    S.insert(p);
                } else {
                    // 最大 C[i] 日新たに印をつけると、区間 inter2 に被るとき
                    res += inter2->first - inter1->second;
                    newC -= inter2->first - inter1->second;
                    newA = min(inter2->second, B[i]);
                    pll p(inter1->first, inter2->second);
                    S.erase(inter1);
                    S.erase(inter2);
                    S.insert(p);
                }
            } else {
                // A[i] が区間 inter1 に含まれないとき
                if (min(A[i] + C[i], B[i]) < inter2->first) {
                    // 最大 C[i] 日新たに印をつけても、区間 inter2 に被らないとき
                    res += min(A[i] + C[i], B[i]) - A[i];
                    newC -= min(A[i] + C[i], B[i]) - A[i];
                    newA = min(A[i] + C[i], B[i]);
                    S.insert(pll(A[i], newA));
                } else {
                    // 最大 C[i] 日新たに印をつけると、区間 inter2 に被るとき
                    res += inter2->first - A[i];
                    newC -= inter2->first - A[i];
                    newA = min(inter2->second, B[i]);
                    pll p(A[i], inter2->second);
                    S.erase(inter2);
                    S.insert(p);
                }
            }
            A[i] = newA, C[i] = newC;
        }
    }
    cout << res << endl;
}

　

解法 2：1 日目, 2 日目, ... の順にとるべき行動を考える

公式に分かりやすく解説されています！

https://www2.ioi-jp.org/joig-camp/2023/2023-sp-tasks/contest2/smartphone-review.pdf