Codeforces Round #219 (Div. 2) - 君はまるで砂漠に咲く、一輪の花。

A. Collecting Beats is Fun

ざっくりと大意

・CucumberはKyubeatという音楽ゲームで遊ぶ。
・Kyubeatは4*4の16個のパネルをタイミング良く押すものである。
・Cucumberは片手でk箇所のパネルをタッチ可能を両手を使ってパーフェクトプレイできるか？？

方針のようなもの

・同じ数がk*2以内なら大丈夫っぽい？

k=input()
h=''
for i in xrange(4):
    h+=raw_input()
chk=0
for i in range(1,10):
    s=h.count(str(i))
    chk=max(chk,s)
print 'YES' if chk<=k*2 else 'NO'

B. Making Sequences is Fun

ざっくりと大意

・(m,m+1,m+2,...)の数列を出来る限り長く作りたい。
・コストが桁数*kを必要として、予算はwまでしかない。

方針のようなもの

・1ずつ加算すると多分TLE。
・桁が増えるまでの1~9、10~99などの間のコストは一定なので、(桁数k)個数のコストがw未満なら更に桁を増やして前回まで数えたコストと合わせてみていく。
・最後は残り予算/(桁数*k) で終わりに。

w,m,k=map(int,raw_input().split())
ans=0
chk=m
while 1:
    dig=len(str(chk))
    digb=int('9'*dig)
    digs=max(int('1'+'0'*(dig-1)),chk)
    nk=digb-digs+1
    abl=w-ans
    if abl>(dig*k)*nk:
        ans+=(dig*k)*nk
        chk=digb+1
    elif abl==(dig*k)*nk:
        chk=digb+1
        break
    else:
        digs+=abl/(dig*k)
        chk=digs
        break
print chk-m

微妙に1ズレて合わなかったりを調整するのが凄い時間がかかった。しかも時間掛かったけど汚いしムダに長いと思う。

C. Counting Kangaroos is Fun

ざっくりと大意

・とあるカンガルーは自分より倍以上の大きさのカンガルーの中に隠れることが出来るので見えてるカンガルーの数nが減る。
・もっとも効率的に隠すとnは最小で幾つになるか？？？

方針のようなもの

・カンガルーはどうやっても半分までにしか減らないのでsortして半分に分けて探していいらしい。
・TLE解消しないので後で。

#test 9でTLE
n=input()
l=[]
for i in range(n):
    l.append(input())
l.sort()
ans=n
x=n/2
a=l[:x]
b=l[x:]
chk=1
ak=bk=p=0
al=x
bl=n-x
while 1:
    if chk==0:
        break
    chk=0
    if bl==0:
        break
    mb=max(b)
    while bk<bl:
        if a[0]*2>mb:
            break
        if a[0]*2<=b[bk]:
            a.pop(0)
            b.pop(bk)
            chk=1
            ans-=1
            bl-=1
            break
        bk+=1
print ans