yutasの競技プログラミング勉強帖

競技プログラミングの問題についての解説記事を主に書いています。

E - Takahashi Quest / トヨタ自動車プログラミングコンテスト2023#8 (AtCoder Beginner Contest 333)

ABC333 AtCoder C++ AtCoder Beginner Contest 450点 競技プログラミング

問題

高橋君が冒険に出る。 冒険では、 n 個の出来事が起こり、 i 番目の出来事は整数 ({t}_{i}, {x}_{i}) の組で表され、以下のようなものが起きる。

  • {t}_{i} = 1 のとき: タイプ {x}_{i} のポーションを1つ発見し、それを拾うかどうかを選択する。
  • {t}_{i} = 2 のとき: タイプ {x}_{i} のモンスターと1体遭遇する。タイプ {x}_{i} のポーションを1つ消費することで勝利できるが、ポーションを持っていない場合は敗北する。

高橋くんが敗北することなく、すべてのモンスターに勝利できるか判定せよ。

もし勝利できる場合は、冒険の途中で持っているポーションの個数の最大値のうち、最小値として考えられる値と、どのようにポーションを拾うかを出力せよ。

入力

最初の1行に、整数 n が与えられる。

次の n 行の i 行目には、整数 {t}_{i}, {x}_{i} が与えられる。

条件

  • 実行時間制限: 2s
  • メモリ制限: 1024MB
  • 1 \leq n \leq 2 \times {10}^{5}
  • 1 \leq {t}_{i} \leq 2
  • 1 \leq {x}_{i} \leq n

出力

高橋くんが途中で敗北する場合には、 -1 を出力すること。

すべてのモンスターに勝利できる場合には、1行目にポーションの所持数の最大値の最小値を出力すること。

そして、2行目に {t}_{i} = 1 であるすべての i について昇順に、拾う場合は 1 を、拾わない場合は 0 を、それぞれ空白区切りで1行ですべて出力すること。

解法

まず、 {t}_{i} = 2 のときについて、モンスター {x}_{i} を倒すための条件は「 i - 1 回目以前にて、 {x}_{i} のポーションが出現していること」となります。

そしてこの問題は「所持しているポーションの個数の最大値」を小さくしたいという問題なので、ポーションを所持している時間を可能な限り減らす、ということが必要になります。

従って、 x のポーションがどこの出来事で出現したのかということを管理し、同じタイプのモンスターが出現したら、その中で最も直近で出てきたものを拾ったことにする、ということで最大値の最小値を実現できます。

これは、各出来事 i = 1, 2, \cdots, n の順に

  • {t}_{i} = 1 であれば、ポーション {x}_{i} に i が現れたことを記録する
  • {t}_{i} = 2 であれば、ポーション {x}_{i} の要素を確認する
    • その際に、要素数が0であれば -1 を出力して終了する
    • 要素が存在すれば、そのうち最大のものを拾ったこととして、その要素を削除する

ということを行えば、最大値の最小値を与える方法を管理することができます。

ソースコード

main() 関数の中に、答えを出力する部分を直接実装しました。

int n, t[int(2e5 + 5)], x[int(2e5 + 5)];
vector<int> potion[int(2e5 + 5)]; // potion[i] は、ポーション i が出現した出来事のインデックスを管理する
bool get_potion[int(2e5 + 5)]; // get_potion[i] は、i 回目の出来事でポーションを拾ったかどうかを管理する

int main() {
  // 値の入力
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> t[i] >> x[i];
  }

  // 出来事を i = 1, 2, ..., n の順で見る
  for (int i = 1; i <= n; i++) {
    if (t[i] == 1) {
      // ポーション x[i] が i 番目の出来事で出現したことを記録する
      potion[x[i]].push_back(i);
    } else {
      int l = potion[x[i]].size(); // ポーション x[i] が出現した回数
      if (l == 0) {
        cout << -1 << endl; // もしポーション x[i] が出現していないならば、 -1 を出力して終了する
        return 0;
      } else {
        get_potion[potion[x[i]][l - 1]] = true; // ポーション x[i] が最後に出現した出来事について、拾ったことにする
        potion[x[i]].erase(potion[x[i]].begin() + l - 1); // ポーション x[i] が最後に出現した出来事を、管理から削除する
      }
    }
  }

  int ans = 0, k = 0; // ans は最終的な答えとなる値、 k はその時点で所持しているポーションの個数
  vector<int> action; // t[i] = 1 である i に対して、拾ったかどうかを 0, 1 で管理する
  for (int i = 1; i <= n; i++) {
    if (t[i] == 1) {
      if (get_potion[i]) {
        k++; // ポーションを拾ったので、 k を1つ増やす
        action.push_back(1); // ポーションを拾ったので、action に 1 を追加する
      } else {
        action.push_back(0); // ポーションを拾っていないので、action に 0 を追加する
      }
    } else {
      k--; // モンスターが出たときはポーションを1つ消費するので、 k を1つ減らす
    }
    ans = max(ans, k); // ans の更新
  }

  cout << ans << endl; // ans の値の出力
  // どのようにポーションを拾ったのかを出力する
  for (int i = 0; i < action.size(); i++) {
    cout << action[i];
    if (i == action.size() - 1) {
      cout << endl;
    } else {
      cout << " ";
    }
  }

  return 0;
}