Codeforces Round #298 (Div.2)
はい。
http://codeforces.com/contest/534
A. Exam
ざっくりと大意
・n人の学生が普段は通し番号のように並んで座っていたのを並ばないように最大人数を座らせる??
方針のようなもの
・そうだ、解説を読もう。
n=int(raw_input()) odd,even=[],[] for i in range(1,n+1,2): odd.append(i) odd=odd[::-1] for i in range(2,n+1,2): even.append(i) even=even[::-1] for i in even: if abs(i-odd[-1])!=1: odd.append(i) print len(odd) print ' '.join(map(str,odd))
方針が立たなかったので解説を先に見に行ってしまった。。解説では偶数奇数を分けてというような事があったのでソレに合わせて書いて2,3回微調整してなんとかAC。確かに番号が続かないようにというなら最低限の2だけ離せば、偶数奇数で分けて処理して後で結合すればみたいなのは思いつくべきだった。。
B. Covered Path
ざっくりと大意
・初めが速度\(v_1\)で終わりが\(v_2\)、1秒で変更出来る速度は±dの範囲。移動総時間はtで移動できる最大距離はいくつか??
・サンプル1は速度5,7,8,6で移動して総距離26になる。最大の2加速の後で終わりを6にするためには7までしか加速できなくて、6が終わり速度になる。
方針のようなもの
・\(v_2\)に調整出来るギリギリまで加速する??
v1,v2=map(int,raw_input().split()) t,d=map(int,raw_input().split()) ans=0 for i in range(t): ans+=min(v1+d*i,v2+d*(t-i-1)) print ans
可能な限り早く加速して減速は後回しにすれば最大距離に出来そうな気はしてたけど書き方が思いつかなくて解説を見てしまった。。 min(v1+d*i,v2+d*(t-i-1))
これは左の要素は\(v_i\)にd・iを加算するのでi秒経過した時の可能な最大速度である。右の要素の\(v_2\)にd・(t-i-1)を加算するのは終わりの速度\(v_2\)に対して残り秒数とdの積を加算するのでi秒経過時の出しても良い、コレより加速してると\(v_2\)まで減速が間に合わないギリギリの速度。この2つの値の小さい方の値がそれぞれの秒毎に出すことの出来る最大速度になり、それの和が最大距離になる。