Codeforces #293 Div.2 B: Tanya and Postcard

題意を勘違いしていてWAを連発してしまった。問題を把握できれば簡単。

問題はこちら。

問題

文字列sとtが与えられる。tから文字を切り出して文字列sをできるだけ再現したい。あるi番目のs[i]に対して、s[i]がまだtにあるときはYとし、s[i]の文字ケースの違うものがまだtにあるときはWとする。Yをできるだけ大きくし、その次にWをできるだけ大きくすることを考えたときの、Y,Wの値を答えよ。

解法

貪欲法で答えが得られる。

まずtの文字列の中から文字ケースのあう同種文字から抜き出していく。残ったtの文字列から今度は文字ケースの違う同種文字を抜き出していけば答えとなる。

alpha = "abcdefghijklmnopqrstuvwxyz"
alpha += alpha.upper()
h1 = {i:0 for i in alpha}
h2 = {i:0 for i in alpha}

for i in raw_input(): h1[i] += 1
for i in raw_input(): h2[i] += 1
y = w = 0
for i in alpha:
    y += min(h1[i],h2[i])
    h1[i],h2[i] = max(0,h1[i]-h2[i]),max(0,h2[i]-h1[i])
for i in alpha:
    j = i.upper() if i.islower() else i.lower()
    w += min(h1[i],h2[j])
    h1[i],h2[j] = max(0,h1[i]-h2[j]),max(0,h2[j]-h1[i])
print y,w