公式

F - AtCoder Cards 解説 by kyopro_friends


@ がないバージョンの問題では、\(S,T\) で各文字の個数が全て一致しているとき Yes、そうでないとき No が答えとなります。@ があるバージョンでも同様に、@ を適切に置き換えることで各文字の個数を一致させることができるかどうかを考えます。

予め \(S,T\) に含まれる @ の個数を求めておきます。その後、atcoder の各文字について \(S,T\) に含まれる個数をそれぞれ求め、少ない方の個数が多い方の個数と等しくなるように @ を置き換えます(実際に文字列を置き換える必要はなく、個数だけ増減させれば良いです)。これらの操作の過程で @ が不足した場合答えは No となります。

(文字の個数を等しくするためには少ない方の個数が多い方の個数以上になるように増やす必要があることと、@ はできるだけ消費しない方が良いことから、このような置き換え方法が最善であることがわかります)

最後まで @ が不足することなく操作を行えた場合、atcoder 以外の他の英小文字についても \(S,T\) に含まれる個数が全て等しい場合 Yes、そうでないとき No となります。

実装例(Python)
実装例(C)

投稿日時:
最終更新: