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

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

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

Codeforces Round #381 (Div.2)

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

A. Alyona and copybooks

ざっくりと大意

・Alyonaの手元には最初にn個ある。個数を追加するのに1個でaルーブルか、2個でbルーブルか、3個でcルーブルのパターンが有る。
・いずれかを最安になる方法で合計数を4で割り切れるようにする。

Python2

IS=float('inf')

n,a,b,c=map(int,raw_input().split())
if n%4==0:
    print 0
    exit()
ans=chk=IS
for i in range(10):
    for j in range(10):
        for k in range(10):
            if (n+i+j*2+k*3)%4==0:
                ans=min(ans,i*a+j*b+k*c)
print ans

適当にheapqで最安状態を取り出してa,b,c全パターン足したのをheapqに戻すことしてたら、nが奇数、a,cが金額大きいの、bが1ルーブルといったケースで奇数のものに延々と2個足し続けてTLEくらった。 けども実際にはループとか要らないようです。。 http://codeforces.com/contest/740/submission/22461314 最安に出来る組合せを絞れなく3重ループしても間に合うのでそれはそれ。

B. Alyona and flowers

ざっくりと大意

・Alyonaの母はn種類の花を持っていて、それらのムードは\(a_i\)である。
・m件の花の選び方候補で1から2、4から5、3から4、1から4といった選び方がある。
・それらの花の選び方を使ってムードが最高になるようにする(1つも選ばない場合あり)。

Python2

n,m=map(int,raw_input().split())
a=map(int,raw_input().split())
x=[0]*(n+1)
x[1]+=a[0]
ans=chk=0
for i in range(1,n):
    x[i+1]=x[i]+a[i]
for i in range(m):
    l,r=map(int,raw_input().split())
    ans+=max(0,x[r]-x[l-1])
print ans

おそらくスライスをsumするとTLEになる。TLE対策には数列aの累積和?でムードが分かるようにする。
例えばサンプル1では数列aの累積で[0,1,-1,0,3,-1]といった数列があると、1から2は2番目と0番目の差で-1、4から5は5番目と3番目の差で-1ということがわかる。そんなのでl,r間の和を求めるようにするとTLEしないはず。