AtCoder

ABC293 B問題(Call the ID Number)を解く

AtCoder_ABC293_B

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 と数列 Ai を読み込む。
  • 以下を N 回行う(ループ変数 i)。
    • 人 i が呼ばれていない限り以下を行う。
      • Ai が示す(配列 called の)要素を true に変更する(人 Ai が呼ばれた)。
  • 以下を N 回行う(ループ変数 i)
    • 人 i が呼ばれていない限り以下を行う。
      • 配列 result に i を追加する。
  • 最後に result の大きさと、result の要素を出力する。

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

上記の方針に従いプログラムします。注意としては、Ai が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番目の要素に値を挿入して、Ai の値で参照できるようにしました(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」と判定されました。

最後に

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

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

COMMENT

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

CAPTCHA