VK Cup 2016 - Round 1 (Div.2 Edition)

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

A. Bear and Reverse Radewoosh

ざっくりと大意

・LimakとRadewooshはn問のアルゴリズムコンテストで競う。
・i番目の問題のスコアは当初は\(p_i\)、難易度順に並んでいて解いた時間は\(t_i\)である。1分ごとにスコアの減少する定数はc。

Python2

n,c=map(int,raw_input().split())
ans=[0]*2
p=map(int,raw_input().split())
t=map(int,raw_input().split())
p2=[i for i in p[::-1]]
t2=[i for i in t[::-1]]
def sol(a,b):
    x=z=0
    for i in range(n):
        z+=b.pop()
        x+=max(0,a.pop()-(c*z))
    return x
ans[0]=sol(p,t)
ans[1]=sol(p2,t2)
print 'Radewoosh' if ans[0]>ans[1] else 'Tie' if ans[0]==ans[1] else 'Limak' 

点数獲得をシミュしてスコアの大小を調べる。

B. Bear and Displayed Friends

ざっくりと大意

・熊のLimakには友達がn人いる。n人とのそれぞれの友情度は\(t_i\)である。
・友人のオンラインを確認する表示領域の最大はk人分で人数を超えると友情度の低いのを消す。
・クエリがq件あり、idが1ならオンライン追加の情報、idが2ならk窓内に見えるかの問い合わせをYES,NOで処理する。

Python2

import heapq

n,k,q=map(int,raw_input().split())
t=map(int,raw_input().split())
d={a+1:i for a,i in enumerate(t)}
chk=[]
for i in range(q):
    a,b=map(int,raw_input().split())
    if a==1:
        if len(chk)<k:
            heapq.heappush(chk,d[b])
        else:
            heapq.heappushpop(chk,d[b])
    else:
        print 'YES' if t[b-1] in chk else 'NO'

久しぶりにheapq使った。友人熊と友情度は連想配列で対応させて、友情度をキューに放り込んだ。毎回sortedで友情度の高低を管理してもTLEにならなかったらしい。