部内コンテストしました
http://d.hatena.ne.jp/kmc-log/20100928/1285677758
しました．全6問で3時間．
今回は問題とデータセットも上げたんで暇な方はやってみては．
FはDiv1 Medium程度はあると思います．Div1 Hard相当のものは残念ながらないです．
以下，一応解説みたいなもの．(かなり適当ですが…)
A
O(1)であることを想定していましたがO(N)でもできます．
B
閉路を見つけます．
ある頂点からスタートしてジャンプをしていって閉路にたどり着いたとき，そこが今ジャンプして訪れた頂点ならカウントし，過去に訪れた頂点ならカウントしない，ということを各頂点についてやります．
C
実装をがんばりましょう．以下の3つの関数があれば全ての役判定ができるので若干楽になるそうです．
int straight() : ロイヤルストレートなら2, ストレートなら1, そうでないなら0
int flash() : フラッシュなら1, そうでないなら0
int n_of_a_kind(int n) : 同じ数字が手元にn枚以上あるようなカードの個数を返す (たとえばカードが2,2,4,4,8ならn_of_a_kind(2)は2．)
D
DPします．3つの能力値はそれぞれ互いに干渉せず独立なので，独立に考えます．つまりある1つの能力値だけを予算内で最高にするということを，各能力値について考えてやります．答えはそれらの最大値をになります．
このとき，dp[M] := 予算M内でできる能力値の最大 とすると，
dp[M] = 0 or max_{i} dp[M-c[i] ]+v[i] (c[i]はi番目のバイドルを雇う費用，v[i]はi番目のバイドルの能力)
dp[0] = 0
dp[-a] = -∞
などが成り立つのでこれを計算します．(ナップサック問題)
E
- 解の1つを2分探索で必ず1つは見つけられるのでそれをαとすると，f(x)はx-αで割ることができて，あとは2次方程式を解くだけになる．f(x)を割るのは単に係数比較するだけでよい．
- 導関数f'(x)を2次方程式の解の公式で解いて，極値と極値の間，あるいは極値と無限遠と間にある解を2分探索で調べる (これらの間では関数は狭義単調なので2分探索ができる)
- 3次方程式の解の公式をググってそれを貼り付ける
などがあります．誤差の評価に注意．
本番ではBairstow's method というアルゴリズムで解いてる人もいました．
ちなみに，d=0か否かで場合分けをしない場合，解が0にとても近づいてしまうと誤差の評価が面倒になってしまうように見えるのですが，実は解は1/(|a|+|b|+|c|)よりも近づかないということが証明できるので，この問題の場合は少なくとも10^-3よりは0に近づくことはないはずということがいえてしまいます．多分．
F
とりあえず盤面を↓みたいにみなします．
+-+-+-+-+-+ y=0 | | | | | | +-o-o-o-o-+ y=1 | | | | | | +-o-o-o-o-+ y=2 | | | | | | +-o-o-o-o-+ y=3 | | | | | | +-o-o-o-o-+ y=4 | | | | | | +-+-+-+-+-+ y=5
ここでdpをします．
dp[t][x1][x2][x3][x4] := y=tの行にある4つのボタンをそれぞれx1,x2,x3,x4回押すとしたとき，y=tから上の領域の戦闘力を最大にするときの値
とすると，y=tとy=t-1の間にある5つのマスはy=t-1の行にある4つのボタンによってのみ決まるので，y=t-1の4つのボタンをそれぞれu1,u2,u3,u4回押すものとすればとりあえず5つのマスについては決まります．y=t-1より上の部分についてはdp[t-1][u1][u2][u3][u4]が最大となっています．
よって dp[t][x1][x2][x3][x4] = max_{u1,u2,u3,u4} ((y=t,y=t-1のボタンを決めたときの5つのマスの戦闘力の合計)+dp[t-1][u1][u2][u3][u4]) となり，計算できます．
計算量は，dpの要素の個数が4*4^4個程度で，1つの要素を計算するのに4^4程度かかるので全体で4^9程度の計算量になります．
初期条件を dp[0][0][0][0][0]=0, dp[0][x1][x2][x3][x4]=-∞ (x1+x2+x3+x4>0) として，答えをdp[5][0][0][0][0]によって求めると実装が楽です．
