CODE FESTIVAL 2014 予選B C - 錬金術士

問題原文

atcoder.jp

解法

から「最低何文字使う必要があるか」「最大何文字使う必要があるか」を計算し、 がその間にあれば YES。

各文字種について互いに影響し合わないので個別に考えて良い。

ある文字種 について、 から使える最大個数は、 内の の個数, 内の の個数 個。
ある文字種 について、 から使う必要がある最低個数は、 , 内の の個数 - 内の の個数
個。

これらの情報を求めておいて判定すればいい。
ポイントは 厳密に１つの解を求めようとするのではなく、ざっくりと可能不可能を判定しようとする ことかなぁ。。。
上限と下限を求めておいて、その間にあるかで判定 みたいな考え方は汎用性高そう。

実装

from collections import Counter
S1 = input()
S2 = input()
S3 = input()

C1 = Counter(S1)
C2 = Counter(S2)
C3 = Counter(S3)

L, R = 0, 0
for i in range(26):
    x = chr(ord('A') + i)
    L += max(0, C3[x] - C2[x])
    R += min(C1[x], C3[x])

if L <= len(S3) // 2 <= R:
    print('YES')
else:
    print('NO')

感想

推定1300弱diffらしいけど解けなかったよ。。。
何もわからなかったのでたくさん勉強させてもらったと思おう。

雰囲気近いのは

atcoder.jp

のにぶたん解かなぁとか思ったり。