これ結構難しくて、嵌まる人は嵌まってしまうと思う！！

問題へのリンク

問題概要

ダンジョンには、ポーション $1, 2, \dots, N$ と、敵 $1, 2, \dots, N$ がいる。

今、ダンジョンで $N$ 個のイベントが起こる。イベント $i$ は 2 つの整数 $t_{i}, x_{i}$ で表される。

のとき：ポーションが現れる
- それを拾うかどうかを決める。
のとき：モンスターが現れる
- もしポーション $x_{i}$ が 1 個以上あったら、1 個消費してモンスターを倒す
- もしポーション $x_{i}$ がなかったら、ゲームオーバー

ゲームオーバーにならずにダンジョンを突破できるかどうかを判定し、突破できるならば「ダンジョン内でのポーションの所持数の最大値」の最小値を求め、それを実現するポーションの拾い方を 1 つ求めよ。

制約

$1 \le N \le 2 \times 10^{5}$

考えたこと

大前提として、(ポーション $1$ , モンスター $1$ ), (ポーション $2$ , モンスター $2$ ), ..., (ポーション $N$ , モンスター $N$ ) はそれぞれ独立に考えられるので、独立に考えることにする。

まず、ダンジョンをクリアできるかどうかの判定は簡単だ。単純にすべてのポーションを拾い、クリアできるかどうかを試せばよいのだ。

次に、「ダンジョン内でのポーションの所持数の最大値」を最小化するためには、基本的には次のように考えたい。

ダンジョン終了時にポーションが余っているとき、その番号のその個数分のポーションは拾わなくて良いはず
モンスター $x$ が現れるとき、できるだけそれ以前の最も最近拾ったポーション $x$ を使いたい。そうすれば、無駄にポーション $x$ を長く持たずに済む

例外パターンもある。たとえば、次のような場合。

(1：ポーション x) (2：ポーション x) (3：モンスター x) (4：モンスター x)

このような時は、

3 番目のモンスター x を 2 番目のポーション x を倒す
4 番目のモンスター x を 1 番目のポーション x を倒す

というように考えて OK（入れ替えてもいいが......）。一般に、次のように解けると考えられる。

Phase 1：拾うポーションを決める

最初に、すべてのポーションを拾っていくシミュレーションを試す（ポーションの index も記録する）
モンスターが現れたときは、現在手持ちのポーションのうち、最も最近拾ったものを使うようにする
- スタックを用いて実装できる
最後に、ポーションが余ったとき、余ったポーションに対応する index のポーションは拾わなくてもよかったと解釈する

Phase 2：もう一度シミュレーション

拾うポーションを決めた状態でもう一度 Phase 1 を実行する
その過程での「ポーションの同時所持数」が答えとなる

この「現在手持ちのポーションのうち、最も最近拾ったものを使う」という方法で最適解を導くことの厳密な証明は、「交換しても悪化しない」の議論で導くことができる。

つまり、そうでないポーションを使うような最適解があったとき、解を悪化させることなく、「最も最近拾ったポーションを使うような方法」に変形することができる。

コード

計算量は $O(N)$ となる。

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int,int>;

int main() {
    int N;
    cin >> N;
    vector<int> T(N), X(N);
    for (int i = 0; i < N; i++) cin >> T[i] >> X[i], --X[i];

    // まずポーションをすべて拾うシミュレーション by スタック (どのポーションかも記録)
    // ポーション番号ごとにスタックを用意する
    vector<vector<int>> st(N);
    for (int i = 0; i < N; i++) {
        if (T[i] == 1) st[X[i]].push_back(i);
        else {
            if (st[X[i]].empty()) {
                cout << -1 << endl;
                return 0;
            }
            st[X[i]].pop_back();
        }
    }

    // 最後まで残っていたポーションは使わない
    vector<int> use(N, 1);
    for (int i = 0; i < N; i++) for (auto v : st[i]) use[v] = 0;
    for (int i = 0; i < N; i++) st[i].clear();

    // 拾うポーションを決めてもう一度、スタックシミュレーション
    int res = 0, num = 0;
    for (int i = 0; i < N; i++) {
        if (T[i] == 1) {
            if (use[i]) st[X[i]].push_back(i), num++;
        } else {
            if (st[X[i]].empty()) assert(0);
            st[X[i]].pop_back(), num--;
        }
        res = max(res, num);
    }
    cout << res << endl;
    for (int i = 0; i < N; i++) if (T[i] == 1) cout << use[i] << " ";
    cout << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 333 E - Takahashi Quest (1Q, 緑色, 450 点)

問題概要

制約

考えたこと

Phase 1：拾うポーションを決める

Phase 2：もう一度シミュレーション

コード