読者です 読者をやめる 読者になる 読者になる

君はまるで砂漠に咲く、一輪の花。

僕はその花に引き寄せられる蝶。

Codeforces Round #382 (Div.2)

はい。
http://codeforces.com/contest/735

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から取り出す。要素数が多いほど減り幅?も大きいので、最大化のためにはより大きな値はより要素数の少ない方に含める必要があるため。