ABC293 B問題（Call the ID Number）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）293 のB問題をC++とPythonで解いてみました。ABC293は、2023年3月11日21:00に実施されました。

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

B問題 Call the ID Number（Difficulty : 65）

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

ABC293 B問題 Call the ID Number

Bool 配列を使って条件を処理する問題です。AtCoder Problems による Difficulty は 65 でした。

解答案

人が呼ばれたか管理する Bool 配列 called（初期値 false）を用意して、それを使って問題を解きます。以下の手順で処理を行います。

• N と数列 A_i を読み込む。
• 以下を N 回行う（ループ変数 i）。
  • 人 i が呼ばれていない限り以下を行う。
    • A_i が示す（配列 called の）要素を true に変更する（人 A_i が呼ばれた）。
• 以下を N 回行う（ループ変数 i）
  • 人 i が呼ばれていない限り以下を行う。
    • 配列 result に i を追加する。
• 最後に result の大きさと、result の要素を出力する。

C++ プログラム例（ABC293B）

上記の方針に従いプログラムします。注意としては、A_i が1から始まっているため、読み込む配列 A を N ＋ 1 個用意して、添え字 1 から N までを使います。A[0] は確保されていますが使いません。

以下が、C＋＋プログラムとなります。

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

int main()
{
	int n;
	cin >> n;
	vector<int> a(n + 1);
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}

	vector<bool> called(n + 1, false);
	for (int i = 1; i <= n; ++i) {
		if (!called[i]) {
			called[a[i]] = true;
		}
	}

	vector<int> result;
	for (int i = 1; i <= n; ++i) {
		if (!called[i]) {
			result.push_back(i);
		}
	}

	cout << result.size() << endl;
	for (int i = 0; i < result.size(); ++i) {
		cout << result[i] << " \n"[i == result.size() - 1];
	}

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

Python プログラム例（ABC293B）

Python のリストは、インデックス0から格納されます。そのため、0番目の要素に値を挿入して、A_i の値で参照できるようにしました（4行目）。基本は、C++ 版の移植です。

リスト result は、内包記法で定義しました（11行目）。

"""AtCoder Beginner Contest 293 B"""
n = int(input())
a = list(map(int, input().split()))
a.insert(0, 0)

called = [False] * (n + 1)
for i in range(1, n + 1):
    if not called[i]:
        called[a[i]] = True

result = [i for i in range(1, n + 1) if not called[i]]

print(len(result))
print(*result)

こちらも「AC」と判定されました。

最後に

上手い方法が無いか考えましたが思い浮かばず、問題に従いシミュレーションしました。

引き続き ABC の問題を紹介していきます。