AOJ埋め15
去年のJAGのセットの続き+α．だいぶうまってきた．
2156 Magic Slayer
使う魔法の順番を変えても結果は変わらないので，全体魔法を先に全部使って，単体魔法を後で使うという風にする．
すると， dp1[x]:=全体魔法を使って少なくともHPをxだけ削るのに必要な最小のコスト，dp2[x]:=単体魔法を使って少なくともHPをxだけ削るのに必要な最小のコストとすると，
全体のコストは 全体魔法で全体からUだけHPを削ったコストdp1[U]＋残りのHPを単体魔法で削るコストΣdp2[hp[i]-U] となる．
dp1,dp2は割と簡単にもとまるので，あとはこの総コストが最小になるようなUを調べればよい．
最初∞の扱いがちょっとまずくてWAを出してしまう．
2157 Dial Lock
回転操作は順番に依存しないので，左端から順にそろえてやればよい．
10!くらいの再帰書いた．
2160 Voronoi Island
凸カット+面積ライブラリで瞬殺．
2161 Defend the Bases
2分探索＋マッチング．
最初題意を勘違いして最小費用流かと思ってええーと思ってしまったのだけど，よく見たら最小化すべきなのはもっともコストが高い辺のコストだったので，最大流で流してやるだけでよい．
2162 Galaxy Wide Web Service
LCM(1,2,3,..,24)は大きいので全部ループで試すのはまずい．
しかし，周期がもし素数ならかならずどれともマッチするはずだし，13,17,19,21を除いたLCMは6万程度なので普通にループでできるので，この4数の場合だけ特別扱いして，それ以外の数なら素直に6万回ループで回してみてやればよい．
4数の場合は基本的にもっとも大きいものを取ればよいが，同じ周期のものが2つ以上来た場合はその重ね合わせを考えないといけないことに注意．
たとえば
13 0 1 1 1 5 1 1 1 1 1 1 1 1 1
13 0 1 3 1 1 1 1 1 1 1 1 1 1 1
13 0 1 1 1 1 1 4 1 1 1 1 1 1 1
なら，重ね合わせると
13 0 3 4 3 6 3 5 3 3 3 3 3 3 3
となるから，もっとも大きいものは6である．それぞれででかいのを取って5+3+4=12みたいにしない．
設問者のミスなのかt[i]に関する説明がないが，これはオフセットであると思われる．
2172 Queen's Case
ゲーム木．千日手が無いならdfsで見てやればいいが，千日手があるためにそうもいかなくなっている．
クイーンの位置をQ，軍の位置をAなどとする．このとき，state(Q,A):=Qが勝つなら+1，Aが勝つなら-1，千日手なら0 と定義する．
すると，
- state(Q,A)=-1 (Q=A),
- state(Q,A)=+1 (QがEにいてA≠Q)
が初期条件として存在し，ゲーム木の条件：
- state(Q,A)=+1 ⇔ ∃Qの次の手Q'，∀Aの次の手A'，state(Q',A')=+1
- state(Q,A)=-1 ⇔ ∀Qの次の手Q'，∃Aの次の手A'，state(Q',A')=-1
が成り立つ．
上記で+1，-1に分類されないものは千日手であると判定できる．
初期条件からスタートし，BFSで次々にゲーム木の条件に沿う状態についてstateを確定していくことで与えられた状態がどれなのかが判定できる．
2210 Star Watching
前のUTPCで解けなかった問題．
日付のパースがちょっと面倒だけど悩む要素はそんなにないはず．サンプルも親切だし．うるう年に注意．
3次元幾何の部分については，回転軸となる直線(北極星と半球の中心を結ぶ直線)をx軸で回転してz軸と合うようにすれば回転操作はz軸を中心とする回転だけで済むし，あとはx軸で回転させたものを元に戻せばそのとおりになる．
x軸とz軸を中心とする回転操作さえできればいいがこれはお決まりの回転行列を y,z成分 | x,y成分 にかけるだけでできるから楽．
幾何ライブラリは要らない．
2211 Stray Cats, Run...
同じくUTPCで解けなかった問題．小一時間考えて全然分からなかった記憶がある．
難問じゃないかと思うんだけどいろんな人に解かれてる．
全然分からないので基本的には解説スライドを写しただけ．
最大値の最小化であるから基本的には2分探索＋DPなんだけど，DPの方が厄介．
2分探索により決まった猫の上限値をlimとかとする．またえさ入れを左から順に0,1,2,...とインデックス付けしておく．
そこで，dp[i]を
dp[i] := えさ入れiを使うときに右半分からやってくる猫の最小数，ただしこの値はlim以下でなくてはならないし，iより右にある部分についても整合性が取れていないといけない．もしそのようなものがないなら∞とする
とおく．(解説のスライドが分かりやすい)
すると，右半分の猫の数がlim以下であるかは単純に総和を取れば分かるし，整合性が取れているかどうかは，iの次に取ると仮定したえさ入れの番号をjとして， (i,jを2つに分けたときの右部分にいる猫の数)+dp[j]<=lim が満たせていればよいことになる．
dp[i]はO(M)で計算できるんで全体ではO(M^2logM)で計算できる．
この問題で面倒なのは境界部分(えさ入れのもっとも左，もっとも右のところ)をどう実装するかというところになるのではないかと思う．
実は端にあるえさ入れ2つについては必ず取ってもいいことが分かるので，左右の端のえさ入れから溢れた位置にある猫は端のえさ入れと同じ位置にあると仮定していいことになる．(なので無理やり移動させてやる)
その仮定の下でdp[M-1]=0としてやってよいし，またインデックス0のえさは取ってもいいと仮定していいことから，dp[0]<=limならばlimで可能，そうでないなら不可能というのが分かる．
なお，僕は解いているときにはそのことには最後まで気づかなかった*1ので，右のえさ入れについては，無限に遠くにあるえさ入れを追加してやって，そのインデックスをMとして，dp[M]=0としてやった．どっちでも実装しやすいほうでやればいいんでなかろうか．
*1:どうやって可能かどうか判定するんだろう… とか思ってた
