Official

E - Takahashi Quest Editorial by MMNMM

どのモンスターに対しても、そのモンスターを倒すのに使えるポーションのうち最も遅く発見するポーションを使うことにしてもよさそうです。

このことから、次の貪欲法を考えることができます。

  • ポーションはすべて一旦拾う。
  • モンスターと遭遇したとき、
    • そのモンスターを倒すことができるポーションを持っていなければ、敗北する。
    • そのモンスターを倒すことができるポーションを持っていれば、そのうち最後に拾ったものを使う。
  • 冒険が終了したあとに持っているポーションは拾わなかったことにする。

この貪欲法は正しい敗北判定と、敗北しない場合最小の \(K\) を与えます。

正当性の証明

  • 敗北判定が正しいこと
    • すべてのポーションを一旦拾うので、敗北と判定された場合、あるタイプのモンスターを \(K\) 体倒すためのポーションをそれらのモンスターとの遭遇までに \(K\) 個以上発見できません。よって、どのような戦略でも敗北します。逆に、敗北と判定されなかった場合は敗北しない戦略を具体的に与えています。
  • \(K\) が最小であること
    • 戦略は「各モンスターに対して何番目のポーションを用いるか」で表現できるので、戦略 \(t\) でモンスター \(m\) に対して用いるポーションを \(f(t,m)\) とします。
      \(K\) を最小にする戦略 \(T\) を一つ取ります。貪欲法の結果 \(T ^ \prime\) と一致しないモンスターが存在すると仮定し、そのうち最も早く遭遇するモンスターを取り \(M _ {\operatorname{first}}\) とします。 貪欲法の仮定より、\(f(T,M _ {\operatorname{first}})\) を発見するより後に \(f(T ^ \prime,M _ {\operatorname{first}})\) を発見します。
      \(f(T,\hat{M})=f(T ^ \prime,M _ {\operatorname{first}})\) となるようなモンスター \(\hat M\) が存在しないとき、単に \(f(T,M _ {\operatorname{first}})\) を \(f(T ^ \prime,M _ {\operatorname{first}})\) で置き換えても \(K\) は増加しません（\(f(T,M _ {\operatorname{first}})\) を発見してから \(f(T ^ \prime,M _ {\operatorname{first}})\) を発見するまでポーションを \(1\) 本少なく持つため）。 \(\hat M\) が存在するとき、\(f(T,\hat M)\) と \(f(T,M _ {\operatorname{first}})\) を交換しても \(K\) は増加しません（\(M _ {\operatorname{first}}\) の取り方から、\(\hat M\) は \(M _ {\operatorname{first}}\) より後に出現します。よって、発見・遭遇するタイミングは \(f(T,M _ {\operatorname{first}})\rightarrow f(T,\hat M)\rightarrow M _ {\operatorname{first}}\rightarrow\hat M\) の順になり、\(2\) つのポーションを使う順番を変えてもそれぞれの時点で持っているポーションの本数は変化しません）。
      よって、\(K\) を増加させないまま \(M _ {\operatorname{first}}\) （およびそれ以前に遭遇するモンスター）に使うポーションを \(T ^ \prime\) と一致させることができます。 モンスターは有限なので、これを有限回行うことで戦略が \(T ^ \prime\) と一致します。 \(T\) の取り方から、\(T ^ \prime\) の \(K\) が最小であることが示されました。

「遭遇したモンスターに使えるポーションのうち最後に拾ったもの」を高速に求める必要があります。 これは、スタックの配列を使って一旦拾っておいたポーションを管理することなどで十分高速に求められます。

それぞれのモンスターに対して使うポーションがわかれば、imos 法などを用いることで \(K\) の値を求めることができます。

実装例は以下のようになります。

#include <iostream>
#include <utility>
#include <stack>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>

int main() {
    using namespace std;

    unsigned N;
    cin >> N;

    // ポーションのタイプ -> {いつ拾ったか, 何本目のポーションか}
    vector<stack<pair<unsigned, unsigned>>> potion_holder(N);

    // potion_result[i] := i 番目のポーションを拾う ⇔ true
    basic_string<bool> potion_result;
    // ∑_{j≤i}occupied_imos[j] := i 番目の出来事の時点で持っているポーションの本数
    vector<unsigned> occupied_imos(N);

    for (unsigned turn = 0; turn < N; ++turn) {
        unsigned event_type;
        cin >> event_type;
        if (event_type == 1) { // ポーションを発見したら
            unsigned potion_type;
            cin >> potion_type;
            --potion_type;
            potion_holder[potion_type].emplace(turn, size(potion_result)); // とりあえず拾い
            potion_result += false; // 一旦使わないと思っておく
        } else { // モンスターと遭遇したら
            unsigned monster_type;
            cin >> monster_type;
            --monster_type;
            if (empty(potion_holder[monster_type])) { // 使えるポーションがなければ
                cout << "-1" << endl; // 敗北
                return 0;
            }
            // 使えるポーションがあれば
            const auto&[t, i]{potion_holder[monster_type].top()}; // 最後に拾ったものを使う
            ++occupied_imos[t];
            --occupied_imos[turn];
            potion_result[i] = true;
            potion_holder[monster_type].pop();
        }
    }

    // imos 法をする
    inclusive_scan(begin(occupied_imos), end(occupied_imos), begin(occupied_imos));

    // 必要な最大本数
    cout << ranges::max(occupied_imos) << endl;

    // それぞれのポーションを拾うか出力する
    for (const auto result : potion_result)
        cout << result << " ";
    cout << endl;
    return 0;
}

posted:
last update: