AtCoder が提供しているABC（AtCoder Beginner Contest）333 のE問題をC++とPythonで解いてみました。ABC333は、2023年12月16日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Takahashi Quest（Difficulty : 948）
問題はリンク先をご覧ください。
逆順に考えることで、解くことができました。AtCoder Problems による Difficulty は 948 でした。
解答案
出来事を逆順に処理していきます。
- 手順2（$t_i = 2$）で遭遇したモンスターを記録する。
- 手順1（$t_i = 1$）の場合、以下の場合分けとなります。逆順に処理しているため、あるモンスターと遭遇するかどうかは分かります。
- ポーションに一致したモンスターと、この先で遭遇する場合、ポーションを拾うことにして、モンスターの数を減らす。
- ポーションに一致したモンスターと、この先で遭遇しない場合、ポーションを捨てることにする。
この手順で出来事を先頭まで処理して、先頭の時点でモンスターが残っていれば、ポーションが足りないことが分かります。この場合は、高橋君は敗北するため、-1 を出力して終了します。
この時点で、高橋君は敗北しません。先頭から出来事をシミュレーションして、ポーションを持つ最大個数を求めることができます。
C++ プログラム例（ABC333E）
上記の考察を、プログラムとして実装します。モンスターの数は配列 enemy として管理します。ポーションを拾う（1）か捨てるか（0）は、配列 action に格納します。
敗北しないことを確認した以降は、出来事のシミュレーションをします（37ー50行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> t(n), x(n);
for (int i = 0; i < n; ++i) {
cin >> t[i] >> x[i];
}
vector<int> enemy(n + 1, 0);
vector<int> action;
for (int i = n - 1; i >= 0; --i) {
if (t[i] == 1) {
if (enemy[x[i]] > 0) {
--enemy[x[i]];
action.push_back(1);
} else {
action.push_back(0);
}
} else if (t[i] == 2) {
++enemy[x[i]];
}
}
for (int i = 1; i <= n; ++i) {
if (enemy[i] > 0) {
cout << -1 << endl;
return 0;
}
}
reverse(action.begin(), action.end());
int max_result = 0;
int result = 0;
int action_index = 0;
for (int i = 0; i < n; ++i) {
if (t[i] == 1) {
if (action[action_index] == 1) {
++result;
max_result = max(max_result, result);
}
++action_index;
} else if (t[i] == 2) {
--result;
}
}
cout << max_result << endl;
for (int i = 0; i < action.size(); ++i) {
cout << action[i] << " \n"[i == action.size() - 1];
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC333E）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 333 E"""
import sys
n = int(input())
t = [0] * n
x = [0] * n
for i in range(n):
t[i], x[i] = map(int, input().split())
enemy = [0] * (n + 1)
action = []
for i in range(n - 1, -1, -1):
if t[i] == 1:
if enemy[x[i]] > 0:
enemy[x[i]] -= 1
action.append(1)
else:
action.append(0)
elif t[i] == 2:
enemy[x[i]] += 1
if max(enemy) > 0:
print(-1)
sys.exit()
action.reverse()
max_result = 0
result = 0
action_index = 0
for i in range(n):
if t[i] == 1:
if action[action_index] == 1:
result += 1
max_result = max(max_result, result)
action_index += 1
elif t[i] == 2:
result -= 1
print(max_result)
print(*action)こちらも「AC」と判定されました。
最後に
コンテスト中ではミスコーディングをしていましたが、時間内にデバッグして、コンテスト中にAC判定をもらうことができました。E問題が解けることはあまりないため、うれしく感じました。
引き続き ABC の問題を紹介していきます。
