日記，やる気がなさそう．．．
1(水)
2(木)
3(金)
英語ができないので何をやってもダメ 話す練習を始めた．
4(土)
5(日)
6(月)
7(火)
8(水)
9(木)
nagoya university virtual contest #6を解いた．
AOJ 2747 カーテン
$N≦100$であるから，座標圧縮すると$O(N^2)$の領域で窓の塗りつぶしができれば良い． 軸に平行な線分しか扱わないのでY軸に平行な線分を見ているときに左側なら+を，右側なら-をおいてimos法っぽくやれば領域を塗ることができる． カーテンの内部の判定も座標圧縮した値があればできる．カーテンに含まれない領域であれば座標圧縮した値からもとの値を復元して面積を求めれば良い． 実装がぐちゃぐちゃになった．
submissionAOJ 2156 Magic Slayer
全体攻撃と単体攻撃は分けて考えたほうが良さそう．
全体攻撃で敵のHPを$h$だけ減らしたとして問題を解くことができれば嬉しい．
$dp(h):=h$ダメージ与えるために必要な最小消費MPとする．全体攻撃と単体攻撃それぞれでdpを行う．
答えは$dp_all(h)+\sum dp_single(HP(i)-h)$について$h$を全探索した際の最小値．
submission
10(金)
nagoya university virtual contest #7を解いた．
AOJ 1379 Parallel Lines
全探索で押し切る．適当に組合せを全部みると$O(N!*N)$の計算量になる．
ペア$(a, b)$を作る際に$ a < b$としても良いことや，$(1, 3), (2, 4)$と$(2, 4), (1, 3)$は変わらないので括弧の左の変数は未使用の数字のうち最小で固定するように実装すると$N!$ のうち偶数番目の数の計算をパスできる． 最大でも$15*13*11*9*7*5*3*1*16$回計算すれば良く，大体$3*10^7$ぐらいなので間に合う．
bitdpっぽくも解ける．少なくともO$(3^N)$ぐらいで解けるが，同様にスキップすると$O(2^{\frac{3}{2}})$ ぐらいで解ける．(多分)
submissionAOJ 1183 鎖中経路
円が並んでいる順に与えられている．最短路は必ず円の交点を経由するはずなので交点，始点，終点の計2N個の点からそれぞれに到達できれば辺を張ればよい．
sからtに行くとして，間にあるiとi+1番目の円でできる2つの交点からなる線分をsからtへの線分が通過するかどうかをみて，全部の線分を通過すれば必ず到達可能．
名大の競技プログラミング練習会では春からライブラリ禁止縛りにしたので幾何の写経で疲れた．
なぜ幾何でcomplexを使わないかというと，誤差で死ぬ問題を解いた事があるから．
submission