Codeforces Round #119 (Div.2)
はい。
http://codeforces.com/contest/189
A. Cut Ribbon
ざっくりと大意
・Polycarpusは長さnのりボンをカットする
・切断後の長さはa,b,cのいずれかで、より多く最大に切り分けたい
方針のようなもの
・価値は全部同じで重さがそれぞれ違って何度でも使えるようなナップサック問題なイメージかな??
・DP問題で自力は無理なのでパクろう
3080063のfish_ballさんのパクリ
n,a,b,c=map(int,raw_input().split()) dp=[0] + [-1]*n for i in xrange(n): if dp[i]>-1: for j in (a,b,c): if i+j<=n: dp[i+j]=max(dp[i+j], dp[i]+1) print dp[-1]
うーん、、もっと練習しないとダメだな。。。
B. Counting Rhombi
ざっくりと大意
・2つの正の数w,hからある特性のあるひし形を数える
・正の数の領域で、頂点が整数である
・頂点は(0,h),(0,0),(w,0),(w,h)の内部か境界上にある
・対角線は軸と平行である
方針のようなもの
・w,hが両方共偶数でないと頂点が整数で取れなくなることは気づいたけどあとはよくわからん
4432259のlovefly1983さんのパクリ
w,h=map(int,raw_input().split()) ans=chk=0 for i in range(h): chk+=(h-i)/2 for j in range(1,w/2+1): ans+=j*chk ans*=2 print ans if w%2 else ans-(w/2*chk)