UVaに寝返り3
世間がクリスマスイブでも関係なしに解きまくり．
112 - Tree Summing
数Iと2分木が与えられるので，文字をパースして2分木を構成し，根から葉に至るまでのパスで和がIになるようなものが存在するか答えよ，という問題．
構文解析，グラフの構築と面倒くさそうな要素が詰まっているので難しそうに感じていたのだけど，少し調べると非常に簡潔に解けるらしいことが判明．(リンク：http://d.hatena.ne.jp/yaneurao/20051127#p1
scanfを上手く利用すれば木を作るまでもなく入力を再帰的に読み込んでいくだけで簡潔に解くことが出来る．
(実は↑のURLのコードのままではコーナーケースが存在するので少し工夫しなければならない)
113 - Power of Cryptography
入力のサイズを見て「うわ多倍長専用とか解けねー」と思ったものの，実はdoubleで近似的に解くことができるという問題．
解が必ずintに収まるサイズになることから，まずdoubleにN,kを入力し，数学関数でpの値をdoubleで出し，その±3の値で候補を出し，誤差が最も小さいものを解とすれば良い．
114 - Simulation Wizardry
単純なシミュレーション．実装するよりもわかりにくい英語を読む方が難しいと思った．
壁orバンパーにあたると座標は変わらずに右に90度曲がるという奇想天外な挙動をすることや，継続条件がlife > 0ではなくlife > 1であることに注意したい．
115 - Climbing Trees
木の2点の関係を答える問題．
入力に長い文字列があるが，名前→idのmap(map
クエリに答えていく際には，木の2点p,qに対し共通の親rを求める関数common(p,q)と，根をレベル0とした各点のレベルを前もって求めておけば楽に答えていける．
116 - Unidirectional TSP
DP．
入力サイズの関係上，各マスに至るログはstringではなくvector
117 - The Postal Worker Rings Once
グラフが与えられるので，全ての辺を通った上で元の頂点に戻るのにかかる最小コストを求めよ，という問題．
全ての頂点を通るわけではないのに注意．
グラフは必ずオイラーor準オイラーであると記されているので，簡単になる．
オイラーの場合は一筆書きがあるので単に辺のコストの総和を返せば良い．
準オイラーの場合，奇数次数の点から出発してもう一方の奇数次数の点へ移動し，その後元の奇数次数の点へ最小コストで移動すれば良い．
最小コストの算出にはダイクストラ法やワーシャル・フロイド法を使うと良い．
118 - Mutant Flatworld Explorers
単純なシミュレーション．
制約に「前のロボットが落ちた場所から落ちてしまうような移動がある場合，その移動は無視する」とあるが，これの解釈を誤るとWrongAnswerを喰らう．
119 - Greedy Gift Givers
シミュレートするだけ．
120 - Stacks of Flapjacks
Flipという動作によりソートを実行する問題．
最適解が求められているわけではないので，好きに処理すると良い．(ただし，「既にソートされてしまっている場合はそれ以上Flipしてはいけない」という条件に気をつける)
多少無駄があってもO(n^2)程度のアルゴリズムなら余裕で間に合うはず．
121 - Pipe Fitters
敷き詰めの制約が簡単なので，計算して最大値を出すだけ．
…のはずが，妙にWrongAnswerで詰まった．
計算式でfloorを使っていたのだが，floorの式が負数になったときに誤作動をしてしまっていたのが原因だった．
(たとえばfloor(-0.1)=-1.0なので，この値が負になることを想定していない場合が漏れてしまう)
具体的には，skewの場合に高さを求める式をfloorを使って求めていたのだけど，これがたまに負数になってそこでバグが発生していた．
