AOJ埋め17
生活リズムが乱れてるせいで1日中眠かった．
明後日は朝からTopCoderなんでちゃんと生活リズム戻しておきたい．
特に埋めたいところもなくなってきたので埋めれそうなところをてきとーに埋めていった．
2202 X-Ray Screening System
もっとも上にあるもの(完全な長方形を成しているもの)があればそれを取り出して#とか適当な文字で置換して，次の長方形を見ていく．
dfsで連結成分を見るとか最初やっていたのだけどそれではまずい(長方形が重なって分離するケースがありうる)ので，W*Hを見てやるのがよい．
2050 Dig or Climb
dpっぽく解く．
dp[i]:=頂点iから村へ行くのにかかる最短時間 とすればdp[i]はO(N)で計算できるので，全体でO(N^2)で計算できる．
穴掘りは式を立てると分かるけど，穴掘り可能な範囲の一番下のところか一番上のところでやるのがもっとも高速なので，この2つだけを見てやればよい．(時間関数がどの高さhから掘るかに関して1次式になるため)
式周りがちょっと面倒だけど頑張る．
2057 The Closest Circle
分割統治．
面倒だったので適当な平面走査(最悪O(N^2))で間に合わないかな? かな? とか思って最初書いたのだけど普通に駄目駄目だったのでちゃんと書いた．
円の半径がいずれも R〜2R であることから普通の最近点対問題っぽく解けるっぽい．(参考：普通の最近点対問題)
にしてもこの問題，やけにほかの人のコードが短いような気がするのだけど気のせいだろうか．
2081 Save the Energy
空間上の2直線の距離＋ワーシャル・フロイド．
直線同士の距離はちょっと面倒だけど頑張って計算したら出る．平行な場合にちょっとだけ注意．
なぜか誰も解いてないけどそんなに難しくないと思う．3次元幾何はやはりvalarrayが強力．
2086 !
ググりにくいタイトル．
N!をB進数で表したときにゼロがいくつ続くかを求める問題．
基本的には10進数のときと同じようにやればいい(N!を素因数分解したときpの指数はいくらになるか求める)けど，答えが最大ケースのときかなり大きくなるので注意．
2090 Repeated Subsequences
Nが300以下なんでN^3だと微妙のように思えたのだけど，定数倍が利いていればN^3でもいいはず! と勝手に思ってそれっぽいdpを組んだ．
stringでごにょごにょしてたらギリギリでTLEを食らったので定数倍高速化をしてギリギリでACもらった．
にしてもNが300以下って条件，どういう計算量を期待してつけてるんだろう．O(N^2log^2N)とか?
2091 Petoris
実装ゲー．
積むブロックの空白行/空白列はあらかじめ削っておいたほうがいい．
幅が64以下なので，行の情報はunsigned long longで保持するようにした．その方が消去判定とかの実装も楽だし，速度も速くなる．
2097 Triangles
適当に計算したら出る．
