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

codeforces

はい。 oxx-- (0/0) 1183(-15)
http://codeforces.com/contest/681
A,Bはpre通して、Cはサンプルにだけ合わせただけでWA。問題Bを誤読してsysで無駄に落としたのが痛かった。

A. A Good Contest

ざっくりと大意

・2400以上はレッドコーダーである。
・beforeのレーティングが既にレッドコーダーで、afterのレーティングがbeforeより1以上増加している人が1人以上いるか？？

方針のようなもの

・全員調べる。

python

n=int(raw_input())
for i in range(n):
    h,b,a=map(str,raw_input().split())
    if int(b)>=2400 and int(b)<int(a):
        print 'YES'
        exit()
print 'NO'

全員調べると言っても入力を受け取りながらチェックして条件を満たした人が出てきたら即’YES'で終了、最後まで出てこなかったら’NO'という感じでも大丈夫。

B. Economy Game

ざっくりと大意

・nが1234567,123456,1234のいずれかを1回以上使って、余りがなければ'YES'になる。余りがある場合は’NO'になる。

方針のようなもの

・全部調べる。

python

n=int(raw_input())
a,b,c=1234567,123456,1234
for i in range(810):
    btmp=n-i*a
    brtmp=btmp/b
    for j in range(brtmp+1):
        ctmp=btmp-b*j
        if ctmp>=0 and ctmp%c==0 and (i+j+ctmp/c)>0:
            print 'YES'
            exit()
print 'NO'

全部調べると言ってもそれほどキツイ計算量ではないようです。あと割りと適当でもACになったのは優しい設定になっているのだと思う。
本当にやりたかったことは入力の最大値109に対して1234567が最大であり得るaの使用回数は810回まで確認するはずだった。だが上記コードだと0から809回までしかみてません。。。
入力nに対して1234567の使用回数を0からn以下で最大になる1234567 * aの使用回数、入力nから1234567 * aの使用回数を引いた残りがまた123456 * bの使用回数である。a,bを見た後の余りが1234で割り切れるor既に0の場合はYESとなる。コンテスト中はa,b,cそれぞれが最低でも1回以上使うと誤読したが実際にはa,b,cのいずれかが最低1回で余りが0になるならば使用回数0のものがあっても良いようである。

C. Heap Operations

ざっくりと大意

・Heap操作の情報が一部抜け落ちた状態で与えられる。
・insertは入力、getMinは最小値確認、removeMinは最小値削除という感じかな？
・サンプル1ではinsert 3で3を入力の後に最小値確認でgetMin 4となって最小値が4になっているのでremoveMinで3を削除してinsert 4すると、最小値確認のgetMin 4で4が出てくるのが正しい状態となる感じ？？

方針のようなもの

・多分シミュレートする。実際に解いてみるのはあとで