AtCoder

ABC287 B問題(Postal Card)を解く

AtCoder_ABC287_B

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$ 回程度であれば、全検索ができます。

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

  • N、M、数字 Si、Ti を読み込む。
  • 各 Si に対して、以下を繰り返す。
    • Si の下3桁が Tj のどれかに等しい場合は、変数 result をインクリメントする。
    • 等しい場合は、それ以上インクリメントしないようにループを抜けて、次の Si を調べる。
  • 最後に変数 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 を使う場合は、Si に重複がある場合などの考慮が必要となります。問題の制約から素直な全検索で解けるか見極めることも重要なのかもしれません。

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

    COMMENT

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

    CAPTCHA