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

はい。 oox-- (0/0) 1217(+21)
http://codeforces.com/contest/735
Bから見て解読に手間取って、一旦はAにAはすぐ解読出来たけどAだけ出来ても仕方ないので保留。 次にCを見に行ってなんとなく出来そうな気がしてサンプルも合ったので提出したらWA。Noteを読むと誤読してるっぽかったので即Cは捨てる。 何が何でもでBを解読したら割りとあっさりなんとかなったので提出してPreが通る。その後にTLEが不安になったが手元PCで適当な最大ケースで大して時間がかからなかったので大丈夫だろうと判断。 することがなくなったが寝落ちする前にAをロックして同部屋を全員確認してYESをYesにしてるとかチョロいのいないか期待するもいなかった。まぁいないですよね。

A. Ostap and Grasshopper

ざっくりと大意

・Gからバッタがkマスずつジャンプを開始して、障害#マスに着地することなくTにたどり着けるか。

　 Python2 　

n,k=map(int,raw_input().split())
s=raw_input()
if s.index('T')<s.index('G'):
    s=s[::-1]
s+='..'*k

cnt=s.index('G')
while cnt<=n:
    if s[cnt+k]=='T':
        print 'YES'
        exit()
    elif s[cnt+k]=='#':
        break
    elif s[cnt+k]=='.':
        cnt+=k
print 'NO'

Tの方のindexが小さかったら::-1でリバースした。Tからスタートでも良かったのかもしれないけど。スタートからkずつ障害にぶつかるか、はみ出すか、Tに丁度着地するかを調べた。

B. Urbanization

ざっくりと大意

・i番目の都市の富は\(a_i\)に等しい。
・都市をaの中から\(n_1\)個と\(n_2\)個選んで、平均の和が最も大きくなるようにする。

Python2

n,n1,n2=map(int,raw_input().split())
a=map(int,raw_input().split())
a.sort()
x=y=0
for i in range(min(n1,n2)):
    x+=a.pop()
for i in range(max(n1,n2)):
    y+=a.pop()
print x*1.0/min(n1,n2)+y*1.0/max(n1,n2)

aをソートして先にn1,n2の少ない方の個数分だけaから最大値を取り出し続けて、次に多い方の個数だけaから取り出す。要素数が多いほど減り幅？も大きいので、最大化のためにはより大きな値はより要素数の少ない方に含める必要があるため。