AtCoder が提供しているABC（AtCoder Beginner Contest）301 のC問題をC++とPythonで解いてみました。ABC301は、2023年5月13日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 AtCoder Cards（Difficulty : 380）
問題はリンク先をご覧ください。
与えられた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問題は翌朝に取り組むとあっさり解けていたため、時間の使い方も重要だと思いました。
引き続き ABC の問題を紹介していきます。
