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

codeforces

はい。 oo--- (0/0) 1300(+105)
http://codeforces.com/contest/580
ACも多く出てるし難易度が低い回だったんじゃないかなー、と思う。

A. Kefa and First Steps

ざっくりと大意

・n日間で\(a_i\)が非減少である最長の部分の長さがいくつか？？

方針のようなもの

・先頭から最後まで確認する。

python

n=int(raw_input())
a=map(int,raw_input().split())
ans=tmp=1

for i in range(1,n):
    if a[i-1]<=a[i]:
        tmp+=1
        ans=max(ans,tmp)
    else:
        tmp=1
print ans

非減少のときはtmpを加算し続けてmax(ans,tmp)で最長部分を記録しておく、減少が発生したらtmpを1に戻す。これで調べられるはず。

B. Kefa and Company

ざっくりと大意

・Kefaがn人の財力:mで満足度:sの友人たちと食事に行く。
・食事に行くメンバーで財力差がd以上とあると友人たちが気にして楽しめないので、そうなるメンバーは招待しない。
・財力差をdより小さいでメンバーを選んで最大の満足度はいくつか。

方針のようなもの

・dが最大109で大きすぎるから連想配列でごまかそう。

python

n,d=map(int,raw_input().split())
bl={}
for i in range(n):
    m,s=map(int,raw_input().split())
    if bl.has_key(m):
        bl[m]+=s
    else:
        bl[m]=s
ls=[]
for i in bl:
    ls.append((i,bl[i]))
ls.sort()
ans=tmp=b=0
lst=len(ls)
for i in range(lst):
    tmp+=ls[i][1]
    if ls[i][0]-ls[b][0]>=d:
        while 1:
            tmp-=ls[b][1]
            b+=1
            if ls[i][0]-ls[b][0]<d:
                break
    ans=max(ans,tmp)
print ans

財力が同じである友人を別々に保存しておく必要がなさそうだったので財力をキーにして満足度は合算してしまった。あとで取り出して財力でソートして財力が小さい方から満足度を加算していって、財力差がd以上になったらdより小さくなるまで該当の満足度を減らしてという感じで終了8分前くらいに提出でAC。。頑張った方です。最初の方ではC++11で友人たちをメモする配列を109確保してたら配列が大きすぎてなのか上手くいかなかったのでC++11は全然わからん。
あと、C問題は深さ優先でD問題はBitDPらしい。いやー、残念ながらcodeforcesは2015/09/23の17:35ころ時点で結構前からジャッジキュー貯まりっぱなしなので惜しい。