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しないはず。