AtCoder

ABC301 C問題(AtCoder Cards)を解く

AtCoder_ABC301_C

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

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

C問題 AtCoder Cards(Difficulty : 380)

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

ABC301 C問題 AtCoder Cards

与えられた2つの文字列に現れる文字の頻度差を計算する問題です。AtCoder Problems による Difficulty は 380 でした。

解答案

与えれらた文字列に現れる文字の頻度を比較します。ワイルドカードである ‘@’ が一文字もない場合は、文字の頻度がすべて一致する場合に ”Yes” を出力します。異なる場合に ”No” を出力します。

文字列 ”atcoder” に含まれる7種類の文字については、ワイルドカード ‘@’ で代替えができます。足りない文字をワイルドカードで補って、文字の頻度が一致すれば “Yes” を出力します。それ以外の場合は “No” を出力します。

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

文字列 S と T の文字頻度を map<char, int> である ms と mt に記憶します(15-17行目)。

文字の頻度を ‘a’ から ’z’ まで調べます。ワイルドカードを用いて文字を補い、ループを抜けてから、ワイルドカード(ms[‘@’] および mt[‘@’])の個数が負になっていないか確認します(34-35行目)。

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

// ABC301C

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

int main()
{
	string s, t;
	cin >> s >> t;
	string atcoder = "atcoder";

	map<char, int> ms;
	map<char, int> mt;
	int size = s.length();
	for (int i = 0; i < size; ++i) {
		++ms[s[i]];
		++mt[t[i]];
	}

	bool result = true;
	for (char ch = 'a'; ch <= 'z'; ++ch) {
		if (atcoder.find(ch) != string::npos) {
			if (ms[ch] > mt[ch]) {
				mt['@'] -= (ms[ch] - mt[ch]);
			} else if (ms[ch] < mt[ch]) {
				ms['@'] -= (mt[ch] - ms[ch]);
			}
		} else {
			if (ms[ch] != mt[ch]) {
				result = false;
			}
		}
	}
	if ((ms['@'] < 0)||(mt['@'] < 0)) {
		result = false;
	}

	if (result) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}

	return 0;
}

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

Python プログラム例(ABC301C)

Python では、defaultdict を使いました(2、7、8行目)。英字の小文字とワイルドカードを文字列で表現しました(15、16行目)。全体的なロジックは、C++ を移植しています。

"""AtCoder Beginner Contest 301 C"""
from collections import defaultdict

s = input()
t = input()

ms = defaultdict(int)
mt = defaultdict(int)
for _, ch in enumerate(s):
    ms[ch] += 1
for _, ch in enumerate(t):
    mt[ch] += 1

result = True
for ch in "abcdefghijklmnopqrstuvwxyz":
    if ch in "atcoder":
        if ms[ch] > mt[ch]:
            mt['@'] -= ms[ch] - mt[ch]
        elif ms[ch] < mt[ch]:
            ms['@'] -= mt[ch] - ms[ch]
    else:
        if ms[ch] != mt[ch]:
            result = False
if ms['@'] < 0 or mt['@'] < 0:
    result = False

print("Yes" if result else "No")

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

最後に

ABC301では、C問題より先にD問題を取り組みました。D問題のWAが取り切れず、残り15分でC問題に取り組みましたが、時間内に解くことができませんでした。C問題は翌朝に取り組むとあっさり解けていたため、時間の使い方も重要だと思いました。

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

COMMENT

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

CAPTCHA