AOJ埋め2

サマーウォーズやってたらしいけどテレビ付けずに普通に問題解いてた．

1285 Grey Area

やるだけ．なるだけ高速に解きたい系．

1286 Expected Allowance

期待値計算．
2変数でDPっぽくやった．そのままやるとメモリが足りないのでちょっと工夫する．
計算量の見積もりがあまり分からなかったのだけど，nm*m^nが1億以下なのでそこまでひどいことにはならないっぽい．

1287 Stopped Watches

問題文が微妙に長い．
長針，短針，秒針がすべて同じ形をしている時計が複数与えられるので，それらを無理やり解釈して時間の幅を最小化しなさいという問題．
hh:mm:ss <-> s t u の対応付けを作ればいいが，回転分があると結構メモリや計算量を圧迫するので，s=0と固定するといい感じになる．
時間の幅を最小化するのは，下限となる時間を決めて次に上限を決めるようにすれば2乗オーダーくらいでできる．

1288 Digits on the Floor

難しそうだけど，できる問題．
とりあえず線分のアレンジメント(かみ合っている線分を交点で二つに割る操作)を施しておく．
次に線分をもとにグラフを作る．
線分は交わるとすればかならず直行するということが問題文に記されているので，線分の向きを第1象限〜第4象限に分けて考えてグラフを構築した． (v[r][j] := 点jが，自分から見て第r象限に向かって伸びる点とつながっているならその点のid，そうでないなら-1 みたいな)
そして，グラフを連結成分でdfsして見てやる．これで1つのdigitを判別することができるはずである．
digitはよく見ると2,5以外はすべて次数が違うということが分かるので，次数だけ取って判別することができる．
2,5については，次数1の点から時計回りでつながっているのか，反時計回りでつながっているのかで判別できる．

1289 Spherical Mirrors

3次元幾何．3次元ベクトルの基本的な操作(四則演算，内積，ノルム)ができれば可能．valarrayがよい．
レーザーが球にぶつかるかどうかについては，半直線と円が交わる条件について立式すると2次方程式が現れるので，それを解けばいい．それで交点も求まる．
レーザーの反射については射影ベクトルとかを使って求める．

1290 Traveling Cube

普通にBFSするだけなのだけどダイスなので実装がめんどい．
ダイスの実装は，向かい合う面の和を一定にするだとか，ちょっとメモリが無駄になるけどtop,south,eastの3面を状態として保持するようにすると回転らへんの実装は楽になる．

1291 Search of Concatenated Strings

5000*2^12でDPなのだけど普通にやったらAOJのメモリリミットに引っかかって難儀した．
計算式の構造上，答えがfalseのときに時間がかかるので，falseのときだけメモ化してtrueの時は毎回計算するとかにするとACを頂けた．