Codeforces Round #372 (Div.2) 参加記

はい。 ox--- (0/0) 1054(-7)
http://codeforces.com/contest/716
B問題はちょっと解読ミスのようなで、、C問題以降は捨ててた。。

A. Crazy Computer

ざっくりと大意

・ZSはn文字を\(t_i\)秒のときに1文字ずつ入力する。
・Crazy Computerなので入力がc秒をこえて間隔が空くと全て失われる。 ・サンプル1は1秒のときに1文字目入力、このとき1文字保存されている。3秒のときに2文字目入力、間隔は2秒だったので合わせて2文字保存されている。8秒のときに3文字目入力、間隔は5秒だったので合わせて3文字が保存されている。14秒のときに4文字目入力、間隔は6秒で過去入力文は全ては消えて1文字が保存されている。19秒のときに5文字目入力、間隔が5秒だったので合わせて2文字が保存されている。20秒のときに6文字目入力、間隔が1秒だったので合わせて3文字が保存されている。

Python

n,c=map(int,raw_input().split())
l=map(int,raw_input().split())
ans=chk=0
for i in l:
    if c<i-chk:
        ans=1
    else:
        ans+=1
    chk=i
print ans

間隔がcと同秒以内なら消去されないのサンプル1で分かるようになってるので、素直にシミュレートすれば大丈夫だと思う。Hackされてる人たちは最後の文字が間隔が空いて1文字のみの保存になるときの処理ミスが狙われていたっぽい。なんでpreに含んでないんだよ、、という感じですけど。自分は同じミスをしないように、いつかHack狙えるようになんとなく覚えておくメモ。

B. Complete the Word

ざっくりと大意

・文字列Sの?を置換して長さ26の区間で各アルファベットが1度だけあるような状態にする。

Python

s=raw_input()
#n,k=map(int,raw_input().split())
#l=map(int,raw_input().split())
w=[0]*26
ans=chk=q=f=0
memo='ABCDEFGHIJKLMNOPQRSTUVWXYZ'
for a,i in enumerate(s):
    if i!='?':
        w[ord(i)-65]+=1
    else:
        q+=1
    if a>=25:
        if w.count(1)+q==26:
            f=1
            ans=''
            tmp=0
            for j in s[a-25:a+1]:
                if j!='?':
                    ans+=j
                    memo=memo.replace(j,'')
                else:
                    ans+=chr(tmp+97)
                    tmp+=1
            o=97
            for j in ans:
                if not j.isupper():
                    ans=ans.replace(chr(o),memo[0])
                    memo=memo[1:]
                    o+=1
            #print s[:a-25]+ans+s[a+1:]
            s=s[:a-25]+ans+s[a+1:]
            w=[0]*26
            q=0
            memo='ABCDEFGHIJKLMNOPQRSTUVWXYZ'
        if s[a-25]!='?':
            w[ord(s[a-25])-65]-=1
        else:
            q-=1
s=s.replace('?','A')
print -1 if f==0 else s

とある区間が長さ26で1文字ずつの区間になったら、その区間の文字は他の区間に関わらないと思う、多分。 例えば、"A??BA"という文字列でA-Cが1度だけあるような最効率？はABCBAで1-3文字の区間と3-5文字の区間というようなことまで求められていないと思う。そういったことを考慮しないでAC出るので。最終の出力で?を残さずに置換しておく必要があるようです。問題文やサンプルのどこからそれを読み取るのかはわかりませんが。コンテストでは?を置換せずでWAでした。