🐎
AtCoder Beginner Contest 301 C問題解説
最近プログラミングコンテストに興味を持ちまして,まぁこれが難しい.
てことで備忘録として躓いた問題を復習したいと思います.
ちなみに言語はPython3です
今回は,AtCoder Beginner Contest 301のC問題
問題文
AtCoder社ではカードを使った 1 人ゲームが流行っています。
ゲームで使う各カードには、英小文字 1 文字または @ の文字が書かれており、いずれのカードも十分多く存在します。
ゲームは以下の手順で行います。
- カードを同じ枚数ずつ 2 列に並べる。
- @ のカードを、それぞれ a, t, c, o, d, e, r のいずれかのカードと置き換える。
- 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