ABC287 B問題（Postal Card）を解く

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

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

B問題 Postal Card（Difficulty : 45）

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

ABC287 B問題 Postal Card

全検索で、数字が一致しているか確認していく問題です。AtCoder Problems による Difficulty は 45 でした。

解答案

問題を読むと、set や map を使いたくなるかもしれません。ただし、問題の制約から、$ 1 \leqq N,\; M \leqq 1000$ であることが分かります。$N \times M = 10^6$ 回程度であれば、全検索ができます。

問題を解く方針を書きだします。なお、S_i と T_i は、文字列として扱うこともできますが、整数として扱うことにします。

• N、M、数字 S_i、T_i を読み込む。
• 各 S_i に対して、以下を繰り返す。
  • S_i の下3桁が T_j のどれかに等しい場合は、変数 result をインクリメントする。
  • 等しい場合は、それ以上インクリメントしないようにループを抜けて、次の S_i を調べる。
• 最後に変数 result を出力する。

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

方針に従い、そのままプログラムしました。

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

int main()
{
	int n, m;
	cin >> n >> m;
	vector<int> s(n);
	for (int i = 0; i < n; ++i) {
		cin >> s[i];
	}
	vector<int> t(m);
	for (int i = 0; i < m; ++i) {
		cin >> t[i];
	}

	int result = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (s[i] % 1000 == t[j]) {
				++result;
				break;
			}
		}
	}

	cout << result << endl;

	return 0;
}

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

Python プログラム例（ABC287B）

Python は、C＋＋ プログラムをそのまま移植しました。

"""AtCoder Beginner Contest 287 B"""
n, m = map(int, input().split())
s = [int(input()) for i in range(n)]
t = [int(input()) for i in range(m)]

result = 0
for i in range(n):
    for j in range(m):
        if s[i] % 1000 == t[j]:
            result += 1
            break

print(result)

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

最後に

最初から全検索をする地道な解法で解いていけば、それほど難しくないと思います。

一方、set を使う場合は、S_i に重複がある場合などの考慮が必要となります。問題の制約から素直な全検索で解けるか見極めることも重要なのかもしれません。

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