AtCoder

ABC295 C問題(Socks)を解く

AtCoder_ABC295_C

AtCoder が提供しているABC(AtCoder Beginner Contest)295 のC問題をC++とPythonで解いてみました。ABC295は、2023年3月25日21:00に実施されました。

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

C問題 Socks(Difficulty : 122)

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

ABC295 C問題 Socks

バケットを使う典型的な問題です。AtCoder Problems による Difficulty は 122 でした。

解答案

出現するデータの頻度をカウントするために、あらかじめ用意した容器(バケット)に頻度を格納していく手法は、競技プログラミングでは、よく使われています。

この問題であれば、靴下の色の頻度をバケットでカウントして、2で割り切り捨てた商の合計が解答となります。

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

    バケットは配列を使うこともありますが、わたしは map を使うことがほとんどです。今回も map を用いて靴下の色の出現頻度をカウントしました。以下が、C++プログラムとなります。

    #include <bits/stdc++.h>
    using namespace std;
    
    int main()
    {
    	int n;
    	cin >> n;
    	map<int, int> a;
    	for (int i = 0; i < n; ++i) {
    		int t;
    		cin >> t;
    		++a[t];
    	}
    
    	int result = 0;
    	for (auto e : a) {
    		result += e.second / 2;
    	}
    
    	cout << result << endl;
    
    	return 0;
    }

    AC(Accepted=正しいプログラム)と判定されました。

    Python プログラム例(ABC295C)

    Python は、defaultdict を使いました。基本的に C++ のプログラムを移植しただけです。

    """AtCoder Beginner Contest 295 C"""
    from collections import defaultdict
    
    n = int(input())
    a = list(map(int, input().split()))
    
    m = defaultdict(int)
    for i in range(n):
        m[a[i]] += 1
    
    result = 0
    for v in m.values():
        result += v // 2
    
    print(result)

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

    最後に

    バケットを使う典型問題でした。このため、B問題(156)とDifficultyが逆転しました。このような問題は、速く解くことが求められると考えています。

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

    COMMENT

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

    CAPTCHA