AtCoder

ABC294 D問題(Bank)を解く

AtCoder_ABC294_D

AtCoder が提供しているABC(AtCoder Beginner Contest)294 のD問題をC++とPythonで解いてみました。ABC294は、2023年3月19日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

D問題 Bank(Difficulty : 385)

問題はリンク先をご覧ください。

ABC294 D問題 Bank

コンテナを使い、クエリを処理する問題です。AtCoder Problems による Difficulty は 385 でした。

解答案

コンテストに提出したプログラムを紹介します。

  • 並んでいる人を priority_queue コンテナ waited に格納します。
  • 呼ばれた人を別の priority_queue コンテナ called に格納します。
  • C++ の priority queue には削除がないため、受付された人は、set コンテナ receipt に格納します。called の top が receipt にないことを確認して表示します。

用意したコンテナに対して、クエリの処理結果を格納していきます。以下がC++プログラムになります。

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n, q;
	cin >> n >> q;

	priority_queue<int, vector<int>, greater<int>> waited;
	priority_queue<int, vector<int>, greater<int>> called;
	set<int> receipt;
	for (int i = 1; i <= n; ++i) {
		waited.push(i);
	}

	for (int i = 0; i < q; ++i) {
		int command;
		cin >> command;
		if (command == 1) {
			called.push(waited.top());
			waited.pop();
		} else if (command == 2) {
			int x;
			cin >> x;
			receipt.insert(x);
		} else if (command == 3) {
			while (true) {
				int temp = called.top();
				if (receipt.find(temp) != receipt.end()) {
					called.pop();
				} else {
					break;
				}
			}
			cout << called.top() << endl;
		}
	}

	return 0;
}

C++ プログラム例(ABC294D)

上記は、冗長なプログラムになっていました。

  • waited は必ず番号順になるため、コンテナは必要なく変数で管理します。
  • called は、削除ができる set コンテナに変更します。

set コンテナは順番を保持しており、最初の要素が一番小さくなります。結果的に以下のすっきりとしたプログラムになりました。

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n, q;
	cin >> n >> q;

	set<int> called;
	int waited = 1;
	for (int i = 0; i < q; ++i) {
		int command;
		cin >> command;
		if (command == 1) {
			called.insert(waited);
			++waited;
		} else if (command == 2) {
			int x;
			cin >> x;
			called.erase(x);
		} else if (command == 3) {
			cout << *(called.begin()) << endl;
		}
	}

	return 0;
}

AC(Accepted=正しいプログラム)と判定されました。

Python プログラム例(ABC294D)

Python では、辞書を使います。辞書は、Python 3.7 から順序を保つようになっています。辞書の要素は、pop で削除して(12行目)、next(iter()) で先頭要素を取得できます(14行目)。

なお、このプログラムは、Pyhon(3.8.2)では、TLE(Time Limit Exceeded)判定でした。PyPy3(7.3.0)は、AC判定でした。

"""AtCoder Beginner Contest 294 D"""
n, q = map(int, input().split())
called = {}
waited = 1

for _ in range(q):
    que = list(map(int, input().split()))
    if que[0] == 1:
        called[waited] = 1
        waited += 1
    elif que[0] == 2:
        called.pop(que[1])
    else:
        print(next(iter(called)))

最後に

問題の意図に従ったプログラムをコンテストで提出しました。公式回答を元にコンテナの使い方を見直し、すっきりとしたプログラムになりました。

ABC294 について、引き続き、E問題まで紹介します。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA