Codeforces Round #248 (Div. 2)
はい。
http://codeforces.com/contest/433
A. Kitahara Haruki's Gift
ざっくりと大意
・n個のりんごを2人の友人に同じ重量になるように分けられるか??
方針のようなもの
・分け方をシミュレートするか分けられない条件の判定式を考える。
n=int(raw_input()) l=[int(x) for x in raw_input().split()] o=l.count(100) t=l.count(200) if (sum(l)/100)%2 or n==1 or (t%2==1 and o==0): print 'NO' else: print 'YES'
きっと多分分けられない条件
りんごの合計の重さが200で割り切れない時(e.g. 合計300gの時は余り100で2人で同じ重さにすることは出来ない)。
りんごが1つしかない時。
りんごの合計が200で割り切れても200gだけで奇数個の時(e.g. 合計が600gでも200gのりんごが3つの時は2人で同じ重さにすることは出来ない)。
一応はAC出たけど上記で本当に正しい判定が出来ているかは保証しないです。
B. Kuriyama Mirai's Stones
ざっくりと大意
・n個の数列\(v_i\)とm個のtype,l,rが与えられる。
・type1なら元々の\(v_i\)のl,rの範囲の総和、type2は昇順でソートしたもののl,rの範囲の総和。
方針のようなもの
・sumは使わないで総和は求めておく。
n=int(raw_input()) v=[int(x) for x in raw_input().split()] v.insert(0,0) u=sorted(v) for i in range(1,n+1): v[i]=v[i]+v[i-1] for i in range(1,n+1): u[i]=u[i]+u[i-1] m=int(raw_input()) while m: m-=1 t,l,r=map(int, raw_input().split()) if t==1: print v[r]-v[l-1] else: print u[r]-u[l-1]
sumは遅いので数列を先頭からループで1つ前までの総和と加算し続けた数列に書きなおしてl,rの範囲の総和はr番目のものから1つ手前のl-1番目のものの差でl,rの範囲の総和になる。