AOJ埋め7

某イベント前日らしいですね．

1240 Unreliable Message

逆順にやるだけ．

1241 Lagrange's Four-Square Theorem

典型的なDP(dp[あと使える平方数の個数][作りたい平方数][使える平方数の上限]でやる) だけど普通にやったらメモリリミットに引っかかったので，[作りたい平方数]のところを8000くらいまでだけメモ化するようにした．
ほかの人のsubmissionみたらメモリそんなに使っていない上に結構速いので，もっといい方法があるのかもしれない．

1242 Area of Polygons

めんどうくさい系．
y=aとy=a+1 (a=-2000,-1999,...,2000) で囲まれる領域に区切って見ていく．
多角形をy=a,y=a+1で区切ったら，多角形が閉じた図形であることから，必ず偶数個の線分が得られるはずなので，それをソートして偶数個ごとに束ねてやれば，台形領域の左端と右端座標が分かる．

あとは，台形領域の左端，右端を左から順に走査していって，区切った領域における面積を求めてやればよい．

1243 Weather Forecast

グラフ作ってDFSするだけなんだけど，題意取り違えたりしょーもないところ間違えたりで2時間くらい詰まってしまった．なんてこったい．
条件に「7日連続で雨が降っていないセルがあってはいけない」というのが少し面倒臭そうだが，よく考えると隅の4つのセルについてだけ見ればいいということが分かるので，隅の4つのセルに何日連続で雨が降っていないかを保持すればいいことになる．
(ちなみに自分の場合，雨が降っていないセルがあってはいけないというのを雨が7日連続で降っているセルがあってはいけないというのに取り違えて，そこでさらに雨雲が7日連続で動かないことがあってはいけない… という風に取り違えて結構ハマってしまっていた．問題文本当によく見間違えちゃうなぁ…．)
結果として状態は [今何日目か(365通り)][雲がどの位置にいるか(9通り)][隅の4セルに何日連続で雨が降っていないか(7^4通り)] で特定できるので，これでDFSして最終状態に到達できるか調べればよい．
初期条件がちょっと面倒なのに注意．

1244 Molecular Formula

化学式が与えられるので，その物質量を求める．
先頭から構文解析すればいい．

1246 Concert Hall Scheduling

DPっぽい問題．
予約をa_k,b_k,w_kとして，これらは適切な順番でソートされているとする．

まず，あまり深く考えずにやると，
A[L][i][j] := 部屋1がi日目以降使えて，部屋2がj日目以降使えるとき，番号L以上の予約を使うときの最大利益
と定義して，
A[L][i][j] = max_{k>=L} { A[k+1][b_k][j]+w_k (ただしa_k>=i) , A[K+1][i][b_k]+w_k (ただしa_k>=j) }
とすると答えはA[0][0][0] で求まることが分かる．
しかし，これだとメモリ容量が1000*365^2 程度必要になるし，計算量はそれよりさらに掛かってしまうので，これでは間に合わない．
そこで，この式の右辺を良く見ると，
B[k][j] := A[k+1][b_k][j]
とおけば，Bだけの閉じた式が得られるというのが分かる．(A[L][i][j]=A[L][j][i]なることに注意．)

あとはBをDPで求めればよい．
これも他の人のsubmissionみたらメモリ使用Low，時間00:00で通してる人が結構いるので，DP以外の解法があるのかも．(あるいはもっと簡単なDPがあるとか?)