実装方針

「選ばれた番号のあつまり」を空の集合で初期化し，客 \(1, \dots, N\) の希望リストを順に見ることを考えます，

客 \(i\) の希望リストを見るとき，以下のように処理します．

• 先頭の要素から順にループを回し，各要素 \(X_{i,j}\) に対して以下の操作を行う．
  • \(X_{i,j}\) が「選ばれた番号のあつまり」に含まれる場合は何もしない．
  • そうでない場合，客 \(i\) は \(X_{i,j}\) を選んだと確定し，「選ばれた番号のあつまり」に \(X_{i,j}\) を追加してからループを終了する．
• 上のループで客 \(i\) の選ぶ番号が確定されなかった場合，客 \(i\) は水を選んだと確定する．

「選ばれた番号のあつまり」を実装する方法はいくつかあります．

• \(k\) 番目の要素が「\(k\) が選ばれたなら \(1\), 選ばれていないなら \(0\)」を表すような配列．
  • \(x\) が含まれるかどうかの判定は，\(x\) 番目の要素が \(1\) かどうかの判定として実装する．
  • \(x\) を追加する操作は，\(x\) 番目の要素を \(1\) にする操作として実装する．
• 連想配列．
  • 多くの言語では，要素追加・存在判定を基本的な機能としてもつ連想配列が標準で実装されている．

いずれによっても必要な機能を使用できます．

実装例 (Python3, C++)

Python3 での実装例を以下に示します．連想配列 used が「選ばれた番号のあつまり」に対応します．

n, m = map(int, input().split())

used = set()
for i in range(n):
	len = int(input())
	x = 0
	draftlist = list(map(int, input().split()))
	for v in draftlist:
		if not (v in used):
			x = v
			used.add(x)
			break
	print(x)

C++ での実装例を以下に示します．配列 isused が「選ばれた番号のあつまり」に対応します．

#include <iostream>
using std::cin;
using std::cout;
#include <vector>
using std::vector;

int main (void) {
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);

	int n, m;
	cin >> n >> m;
	
	vector<int> isused(m+1, 0);
	for (int i = 0; i < n; i++) {
		int len;
		cin >> len;

		vector<int> x(len);
		for (int j = 0; j < len; j++) {
			cin >> x[j];
		}

		int ans = 0;
		for (int j = 0; j < len; j++) {
			if (isused[x[j]] == 0) {
				isused[x[j]] = 1;
				ans = x[j];
				break;
			}
		}

		cout << ans << "\n";
	}

	return 0;
}