Codeforces Round #374 (Div.2) - 君はまるで砂漠に咲く、一輪の花。

A. One-dimensional Japanese Crossword

ざっくりと大意

・クロスワードのような白マスと黒マスが１行に並んだものがある。
・１行目に黒マスの塊が何箇所あるか、２行目にそれぞれの塊が何マスかを出力する。

Python2

n=int(raw_input())
ans=[str(len(x)) for x in map(str,raw_input().split('W')) if len(x)>0]
print len(ans)
print ' '.join(ans)

他の言語は知らないけどPythonなら'W'を区切り文字にして入力受取すればかなり楽だと思う。

B. Passwords

ざっくりと大意

・Vanyaは正しいパスワードを覚えていないので、n個のパスワードの正解候補の文字列を短いものからすべて試す。
・正解のパスワードは最終行の文字列。
・パスワードを1つ試すのに1秒かかり、k回間違えると5秒待ちのペナルティがある。
・正しいパスワードを入力できる最良と最悪の秒数を出力する。
・サンプル1は正解の文字列がabcで文字列長が3、入力候補の5件もいずれも文字列長は3である。最良は1つ目で正解で1秒、最悪は5つ目になる場合で1,2回続けて失敗+ペナ5秒、3,4回続けて失敗+ペナ5秒で14秒かかった後に5つ目が正解で+1秒かかって15秒。
・サンプル2は正解の文字列が22で文字列長が2、入力候補の4件の中で文字列長の短い3番目の1と4番目の2が優先されて2秒、次に文字列長が2の1つ目と2つ目が入力候補で最良は+1秒、最悪は+2秒。入力が100回になっていないのでペナルティはなし。

Python2

import heapq

n,k=map(int,raw_input().split())
l={}
m=[]
for i in range(n):
    s=raw_input()
    if len(s) in l:
        l[len(s)]+=1
    else:
        l[len(s)]=1
        heapq.heappush(m,len(s))
chk=len(raw_input())
ans=0
cnt=0
while 1:
    tmp=heapq.heappop(m)
    if tmp==chk:
        print (ans/k)*5+ans+1,((ans+l[tmp]-1)/k)*5+ans+l[tmp]
        break
    else:
        ans+=l[tmp]

文字列長しか気にしなかった。入力候補のn件の文字列は同じ長さの文字列が何個あるかを連想配列で管理、文字列長が短いものを優先して使えるようにキーと同じ値をheapqにいれた。正解と同じ文字列長になるまで件数だけ加算し続けて、正解と同じ文字列長のターンになったらそれまでの件数とペナルティを計算したものに正解の入力で+1して最良、最悪はそれまでの件数と同じ文字列長の件数-1の和とペナルティを計算したものに正解の入力で+1したら大丈夫だった気がする。