Codeforces Round #372 (Div.2)
はい。
http://codeforces.com/contest/716
A. Crazy Computer
ざっくりと大意
・ZSは狂っているコンピューターでc秒間継続して入力がないと入力済のものが消え去る。
・入力を\(t_i\)秒の時に行って、最終で何文字が残っているか。
・サンプル1は1,3,8秒の時に入力があり3文字の状態(3,8の秒間の5秒はcが5だが消えないらしい)、次が14で6秒間空くので全て消えた状態で14の時に1文字入力される。続けて19,20で合計3文字で入力が終了。
Python2
n,c=map(int,raw_input().split()) l=map(int,raw_input().split()) ans=chk=0 for i in l: if i-chk>c: ans=1 else: ans+=1 chk=i print ans
先頭から見ていって前の秒数と累積の文字数をメモしておいて、c秒を越えたら文字数を1に戻す感じで大丈夫だと思う。
B. Complete the Word
ざっくりと大意
・?を任意の文字に置換して文字列内のどこか長さ26の箇所で英大文字の各字がそれぞれ1回現れるようにできるか。
Python2
s=raw_input() if len(s)<26: print -1 exit() l=set([chr(x+ord('A')) for x in range(26)]) for i in range(len(s)-25): ans='' t=s[i:i+26] if ('?' not in t and len(set(t))==26) or ('?' in t and len(set(t))+t.count('?')==27): ans+=s[:i] tmp=s[i:i+26] dif=l-set(tmp) for k in tmp: if k=='?': ans+=dif.pop() else: ans+=k ans+=s[i+26:] ans=ans.replace('?','A') print ans exit() print -1
部分文字列を見るのに開始位置1ずつずらして、2重目のforは長さ26でしゃくとりでもTLEギリギリでもなくAC出来るっぽい。または長さ26の部分をスライスで一気に取得して調べることが出来る。いや、やってることは同じですが。
長さ26部分をset型にして'?'を含んでいないなら要素数26になるはず、含んでいるなら要素数と26部分内の'?'の個数の和が27になるはず。'?'に何を使うかは全26文字と部分の差で調べられる。26のが作れたらそれ以外の部分をスライスしたものを繋いで残りの'?'を一括で置換して適当に'A'とかに置換する。