AOJ2638 Hyperrectangle
考察に3時間ぐらいかかった気がするのでコンテスト中に解けなさそう．．．
解法
まず，全てのについて
の場合について考えると，2次元なら長さsの正三角形，3次元なら正三角錐，，，d次元の正三角錐（三角錐かどうかは怪しい）になります．
次に，十分に大きいsについて，である場合を考えると，先ほどの長さsのd次元の三角錐から長さ1の三角錐をd個削った形になります．
イメージとしては，長さsの正三角錐のそれぞれ角からの長さの正三角錐を削り取った形が最終的に削り取る形になります．
角から削っていくと，重複して削られる部分が出てきます．ちょっと考えると重複して削られる部分の形も正三角錐になることがわかります．
また，d次元長さsの三角錐の体積（？）はとなります．
これらを冷静になって一般化すると，包除原理を使って，
(
の部分の体積)
(
かつ
の部分の体積)
(
かつ
の部分の体積)
...
(
かつ
かつ
の部分の体積)
(
かつ
かつ
の部分の体積)
...
となることがわかります．
このままだと状態数がなのですが，
落ち着いて考えると，lをK個選んで
となる
の組み合わせとすると，このDPは
で求められ，答えは
の総和となります．
このままだとTLEですが，Kの部分については偶奇にしか興味がないのでmod2の値のみ保持すればよいです．
ので，これを使うとで答えが求められます．
ソースコード
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1959399#1
考察中はこんなスッキリした包除原理の式が出てこなくて，無限に三角錐を書いていたら思いつきました．
d=3
l=1,2,3
s=4
のケースを紙に書いてみると三角錐うんぬんが分かりやすいかもしれません
こんな感じの図になります（黒い部分が重複している部分
AOJ2312 魔法少女さやかちゃん
多分勉強会の問題の中で開いてから解くまでが最速だった．（これは罠で，日本語の問題だからという説がある
解法
輪というのが考えにくいのでなんとか区間というか数を一列に並べる問題にならないか考えてみます．
試しにの位置を固定してみると，
の間に二本の数列が存在していることが分かります（長さ0の数列もありうる)
この二つの数列について，の値をどちらの数列に割り振るか決めたとき，どちらの数列も単調増加になるように並べると最適になることがわかります．
単調増加な数列を2本作ればよいので，Kの値を事前にソートしておいてDPをします．
片方の数列の最後尾がiでもう片方の最後尾がkであるときに必要な精神力の和の最小値
とすると各状態の遷移は累積和を使えばO(1)でできるのででできます．
空間計算量もdpの配列を使いまわしていけばになります．
AOJ2538 Stack Maze
勉強会の問題がICPCっぽく（悪い意味で）なってまいりました．
問題文
Stack Maze | Aizu Online Judge
日本語訳が欲しい方は「mayoko stack maze」とかで検索するとよいです．
解法
最初に思いつくのはdp(r,c,今持っている宝石のスタック)というDPだと思いますが，多分間に合いません．
書くのが面倒なのでとします．
すると，次に思いつくのはの次のようなDPだと思います．
からスタートして
までスタート時点で積まれているスタックに影響を与えずに稼ぐことのできる得点の最大値
とすると全体で全ての長方形で取得できるスコアを計算でき，最終的に
が答えになります．
これのやり方についてはが宝石と穴の対になっているかで場合分けをしてごにょごにょします．
上記の解法では間に合わないのでもう少し考えます．
宝石と穴の関係について，一つのデータセットには同じアルファベットが最大10までしか存在しないので，宝石，穴の組み合わせについてはでほぼNの最大値と一致します．先ほどのDPについて考えると，考えるべき座標の対
は宝石と穴のペアとスタート，ゴールだけでよさそうです．
よって状態数がに落ちて，各状態の更新を
でやれば全体
ぐらいでできるはずです．
具体的にどういう実装をしたかというと，メモ化再帰を行いました．
について，始点Sから終点Tまでいくつスコアを稼ぐことができるかという配るDPを行います．
今見ているマスが通常マスならそのまま右下への遷移を行い，宝石マスなら長方形内の穴との対を全探索し，DPの表に反映させます．
これをメモ化再帰によってで求めています．
実際は宝石と穴とのペアの探索で高々10回のループを回しているので，ぐらいの計算回数になると思います．
AOJ2296 Quest of Merchant
頑張るだけ
解法
色々眺めていくとナップサック以外考えられなくなると思うのでナップサックで考える．
まず初めの考察として，原点から出発して再び原点に返ってくる操作を1セットとできそう．
では1セットにしてどうするか．どう見てもが怪しい．
1セットで訪れる町の集合を個別に考える．町の集合は通り．
訪れる町の集合が決まると，その町の集合を全部通って原点に帰るまでの最短時間はTSPもどきでまとめてで求められる．
また，町の集合ごとに取得できる商品についてナップサックDPを行うことで，1セット(重量上限W)で持ち帰れる最大の商品価値をで求めることができる．
つまりここまでで，各訪れる町の集合ごとに，(所要時間,商品の合計価値
)という情報が得られる．
あとはこれを使ってナップサックDPを行い，時間T以内に取得できる商品価値の最大値を求めてやればよい．
AOJ2224 Save your cats
薔薇園の魔女に比べたら11454倍楽
解法
閉路を含まなくするためにできるだけ少ない長さの辺を削りたい．
すなわち，できるだけ辺の総和が長くなるように閉路を含まないグラフを作りたい
よって最大全域森を作ればよい．
AOJ2310 薔薇園の魔女
二度と解きたくない
解法
全探索をします．
といっても直線を引く候補が無限個あるので，少し考察をします．
最適解の直線があったとして，分割する数を減らさないように少しずつ直線の角度をずらしていくと，直線とある格子点がぶつかるところで動かせなくなります．
このことを考えると，格子点を通る直線をほんのわずか左右に動かしたものだけを候補として考えればよく，本の直線だけ考えればいいことが分かります．
直線を決めたら，その直線が何回境界をまたぐかを求めてやるといくつに分割できるかが求められます．つまり直線と線分の交差判定ができればよいです．
サンプル2から，角をちょうど貫通する直線は角の生命体を分離しないっぽいです．いやこれどう見ても4つに分割してるでしょ．．．
あとはあとは線分と直線の交差判定をでやりたいので，直線を偏角ソートして順に探索していけば
で解けます．
探索上では格子点を通る直線の探索をしているので，格子点を通る場合は左右にずらした場合の線分の交差について，2通りのカウントが必要になります．
AOJ2168 Luigi's Tavern
マッチングかー，フローっぽいなあ，どう見てもフローじゃん
みたいな感じだった
解法
パーティーを沢山作りたいので，各パーティーに役職はそれぞれ高々一人でいいことが分かります．
それで，人を頂点，友好関係を辺として張ってみると各頂点を高々一回ずつ使ってマッチングを沢山作ってくださいみたいな問題に見えてくると思います．
とりあえず簡単化のために，各パーティは必ず4つの役職全てを含む場合を考えてみましょう．
各頂点を高々一回というのは，頂点を入り口用と出口用の頂点二つに分割して，入り口と出口を流量1の辺で繋げば実現できます．
これでこのケースはグラフを構築してフローを流すだけで解けることが分かりました．
では各役職が欠けてもいい場合について考察してみましょう．
ある役職が欠けてる場合は，フローを流すときその役職をスキップしてフローを流すことができると考えることができます．
スキップする回数も制限がありますが，スキップするために使う頂点をその役職のダミーの人であると考えると，
ダミーの人がそれぞれ人いると考えることができます．
そしたら同様に入り口と出口を分けてその間に人数分の流量の辺を張るだけになります．
グラフの構築ですが，自分で番号を決めるのではなく，どの役職の何番目の人=何番目の頂点みたいに変数として保存して置き，sz++ のようにして自動で割り当てていくと比較的楽になると思います．