Zenn
🐎

AtCoder Beginner Contest 301 C問題解説

2023/05/21に公開
Python
AtCoder
#
collections
tech

最近プログラミングコンテストに興味を持ちまして，まぁこれが難しい．
てことで備忘録として躓いた問題を復習したいと思います．
ちなみに言語はPython3です

今回は，AtCoder Beginner Contest 301のC問題

問題文

AtCoder社ではカードを使った 1 人ゲームが流行っています。
ゲームで使う各カードには、英小文字 1 文字または @ の文字が書かれており、いずれのカードも十分多く存在します。
ゲームは以下の手順で行います。

  1. カードを同じ枚数ずつ 2 列に並べる。
  2. @ のカードを、それぞれ a, t, c, o, d, e, r のいずれかのカードと置き換える。
  3. 2 つの列が一致していれば勝ち。そうでなければ負け。
    このゲームに勝ちたいあなたは、次のようなイカサマをすることにしました。
  • 手順 1 以降の好きなタイミングで、列内のカードを自由に並び替えてよい。
  • 手順 1 で並べられた 2 つの列を表す 2 つの文字列 S,T が与えられるので、イカサマをしてもよいときゲームに勝てるか判定してください。

制約

S,T は英小文字と @ からなる
S,T の長さは等しく 1 以上 2×10^5以下

入力

S
T

出力

イカサマをしてもよいとき、ゲームに勝てるなら Yes、勝てないなら No と出力せよ。




以下解説．単語の使い方やその他間違いがあればご指摘ください．

躓いたポイント

1. @の扱い方
2. 二つの配列の比較方法

いや全部で草
唯一良かった着眼点は@の数数えたことぐらいです（白目）



てことで

解き方

1. 各配列から@の数を数え，@を取り除く
2. 二つの配列の各文字とその数の差をとる
3. その差に関して以下の順番で条件をみる
  ¡. 残った文字は@の要素に含まれるか
  ⅱ. 残った文字の合計数はそれぞれ@の数と等しいか

1はreplaceメソッド使えば簡単ですね．

2,3をスマートに行うためには，collectionsライブラリのCounterモジュールを使いましょう．

3の条件を順番通りに全て満たせば Yes と出力します．

解答例

from collections import Counter
 
#入力
S = input()
T = input()
a = {"a","t","c","o","d","e","r"}

#1
Sa = S.count("@")
Ta = T.count("@")
S = S.replace("@","")
T = T.replace("@","")

#2 初心者の方はここのSCやTCの中身を実際に確かめてみて下さい．
SC = Counter(S)
TC = Counter(T)

#辞書型の差をとる
ST = SC-TC
TS = TC-SC
 
#3
if not set(ST.keys()) <= a:
    print('No')
    exit()
elif not set(TS.keys()) <= a:
    print('No')
    exit()
elif sum(ST.values()) > Ta:
    print('No')
    exit()
elif sum(TS.values()) > Sa:
    print('No')
    exit()
print('Yes')

理解できれば全然難しくないなぁって感じ．
ポイントはCounterモジュールの使い方と条件分岐ですねー．

Discussion