AOJ埋め9
某イベント2日目だったらしいですね．某イベントことばっか書いてるな最近．
今回は2001年のセット．全完できるセットだと思う．
Starship Hakodate-maru
最初に全部求めておけばいい．
e-market
実装するだけだけど結構面倒くさい．
Fishnet
n小さいのでやるだけ．直線の交点と4角形の面積求められればそれでいい．
77377
DPでやった.
まず，入力値を，たとえば press なら 77377 のように変換した形で保持しておく．そこで， vector
…なんだけど，AOJのジャッジに問題がある(Special Judgeでないといけないはずなのに通常Judgeになっている)のか，WAしか出ない!!
しょうがないので Live Archive でsubmitしたらAC．なんじゃそら．
とりあえずAOJにジャッジ方式変えろとの趣旨のメールを送って放置．
Beehives
回転パターン(回転6通り×鏡像2通り)を全部試す．
set
Young, Poor and Busy
4種類くらいのDPでやった．
dp[0][id][t] := Hakodateから出発して時刻t以内に頂点idに着くのにかかる最小コスト
dp[1][id][t] := Tokyoから出発して時刻t以内に頂点idに着くのにかかる最小コスト
dp[2][id][t] := 頂点idから時刻t以降に出発してHakodateに着くのにかかる最小コスト
dp[3][id][t] := 頂点idから時刻t以降に出発してTokyoに着くのにかかる最小コスト
みたいな感じ．計算量は大してかからないっぽい．
Nim
適当にDP．
dp[S][n] := 石の個数S，開始するプレイヤーnから始めて，自分が勝つなら1，相手が勝つなら0 としてごにょごにょ．
Super Star
a[i]を入力座標，wを3次元ベクトルとして
f(w)=max_{0<=i<N} |a[i]-w|
に対し，min f(w) を求める問題．
fは下に凸な関数である．1変数関数なら3分探索するだけだけど，3変数関数なのでどうするのかよく分からない．
x座標で3分探索 → y座標で3分探索 → z座標で3分探索 → x座標で… を繰り返せばどうにかなるかなーとか思ったのだけどそれだとどうも駄目らしい．うーむ．
小手先でx,y,z方向に動かすようにするようにしたけどWA．
分からないのでiakasTさんの記事を参考に山登り法を書いてAC．
山登り法において，近傍の解を求める際にそれが最適じゃなくて微妙に駄目な解の場合どういう挙動になるのかよくわかってないのだけど，あれでいいもんなのか．あんまりまだよく分かってない．
解じゃないところで詰まってしまったり，十分解に近づいていないのに終了することが無ければいいのだろうか．
