UVaに寝返り2

UVa

敏腕アルゴリズマーへの道は険しい．

104 - Arbitrage

最短経路問題の類…と見せかけてDP．
D[a][b][k]に，点a->点bにk本の辺を辿っていった際に得られる最高値を格納しておく．
ログ取りも忘れずに．

105 - The Skyline Problem

素直に左から順番に見て行くだけ．
各長方形の左端と右端をvectorに入れてソートして，今見ている長方形を追加したり除外して，
最も高い辺のものを出力する．

106 - Fermat vs. Pythagoras

原始的なピタゴラス数を生成する式があるので，1000000以下の原始的なピタゴラス数を全部列挙する．
1つ目の出力については，列挙した配列をcの値でソートして2分探索すれば終わり．(upper_boundを使う)
2つ目の出力については，あらかじめ1000000までのjについて，j以下の原始的とは限らないピタゴラス数の組で登場する数の個数を，
配列に保持させてカウントしていく．
原始的とは限らないものも数えなければならないのが面倒で，最初この数え上げをsetでやっていたらどうしてもTLEになるので数十分悩んだ．

107 - The Cat in the Hat

数論．
H=(N+1)^h, W=N^h が与えられるので，W-1/N-1, (N+1)*H-N*W を計算する．
(問題文が分かりにくいのが難点)
N=1のときに注意する．
Nを求める際に記述が十分な書き方でなかったためにWrongAnswerを喰らってしばらく理由が分からなかった．

108 - Maximum Sum

DP．
D[h][a][b] (a<b) に，左下(h,a)，右下(h,b)となる長方形で，和が最大となる値を格納していく．
O(n^3)だがn<=100なので間に合う．

109 - SCUD Busters

幾何問題．
凸包作成+点が凸包内部にあるかの判定＋凸包の面積 の3本立て．
某所のライブラリを使って瞬☆殺．

110 - Meta-Loopless Sorts

ソートを実行するコードを出力せよというへんな問題．
やることはN!回のループ構成なのでそれほど難しくないが，Presentation Errorが出て焦る．
(最後の改行に問題があるのが原因だった．)
UVaとかPKUはわざわざ改行にまでケチ付けてくるところが嫌ですね…