AtCoder

ABC308 B問題(Default Price)を解く

AtCoder_ABC308_B

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

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

B問題 Default Price(Difficulty : 52)

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

ABC308 B問題 Default Price

連想配列を使って寿司と値段を関連付けて問題を解きます。AtCoder Problems による Difficulty は 52 でした。

解答案

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

以下の説明では、配列の添え字を 0 からカウントしています。問題では、C と D の添え字は 1 から、P の添え字は 0 からカウントしているため注意してください。

与えらえた文字列(皿の色)Di と値段 Pi+1 を連想配列で関連付けます(23行目)。Di にない皿の色の値段は P0 となります。C++ の map は存在しないキーに対して 0 を返しますが、Pi は1以上のため問題ありません(28行目)。

価格の合計を result として、食べた皿の色に従い更新していきます。

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

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

int main()
{
	int n, m;
	cin >> n >> m;
	vector<string> c(n);
	for (int i = 0; i < n; ++i) {
		cin >> c[i];
	}
	vector<string> d(m);
	for (int i = 0; i < m; ++i) {
		cin >> d[i];
	}
	vector<int> p(m + 1);
	for (int i = 0; i <= m; ++i) {
		cin >> p[i];
	}

	map<string, int> price;
	for (int i = 0; i < m; ++i) {
		price[d[i]] = p[i + 1];
	}

	int result = 0;
	for (int i = 0; i < n; ++i) {
		if (price[c[i]] == 0) {
			result += p[0];
		} else {
			result += price[c[i]];
		}
	}

	cout << result << endl;

	return 0;
}

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

Python プログラム例(ABC308B)

Python 版では、連想配列として辞書を使いました。普段は defaultdict を使いますが、この問題では初期値がない配列を読むことがないため辞書で対応できます(7行目)。

"""AtCoder Beginner Contest 308 B"""
n, m = map(int, input().split())
c = list(input().split())
d = list(input().split())
p = list(map(int, input().split()))

price = {}
for i in range(m):
    price[d[i]] = p[i + 1]

result = 0
for i in range(n):
    if not c[i] in price:
        result += p[0]
    else:
        result += price[c[i]]

print(result)

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

最後に

連想配列を学べる良い問題だと思います。

連想配列はキーが存在しない場合の値の扱いがプログラミング言語によって異なるようです。Python の辞書と defaultdict についての理解が深まりました。

ABC308 について、引き続き問題を紹介していきます。

COMMENT

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

CAPTCHA