AtCoder Grand Contest 029
はい。
https://atcoder.jp/contests/agc029
A - Irreversible operation
PyPy3
s=input() ans=chk=0 for i in s[::-1]: if i=="B": ans+=chk else: chk+=1 print(ans)
操作消化後の最終形がW...Bになります。操作回数はWより後ろにあるBの個数分だけになるはずです。文字列Sを逆から見ていってWの個数を数えつつ、Bがあったならそれより前にあるWの個数が操作回数になるはずなのでansに加算していくと解になるはずです。
B - Powers of two
PyPy3
n=int(input()) a=[int(i) for i in input().split()] a.sort() d={} for i in a: if i in d: d[i]+=1 else: d[i]=1 p=max(a)*2 chk=[pow(2,i) for i in range(1,32) if pow(2,i)<=p] ans=0 for i in a[::-1]: if d[i]>0: d[i]-=1 for j in chk[::-1]: if j-i in d and d[j-i]>0: d[j-i]-=1 ans+=1 break print(ans)
2のべき乗のリストを作成します。最大値はA内の最大値の2倍まででいいと思います。Aの中から2つの数の和が2のべき乗〜というのを探すので2倍より大きい数はペアでは作成できないことが確定するので。
ですけど今回はTLEとか、最悪ケースの場合に何か対策をとかはないので if pow(2,i)<=p
はしてもしなくても変わらないと思います。つまりよく分かりません。