URL https://community.topcoder.com/stat?c=problem_statement&pm=13747&rd=16416
概略 大きさの異なるパンケーキをランダムに積む．自分より小さいパンケーキの上には積むことができず，積めなくなった時点で美味しさの総和が計算される．総和の期待値を求める．
方針 dp[i][j] := 一番上の大きさがiで既にj個積んでいる確率とします．パンケーキは大きい順に見ると遷移が簡単です．
個数が $j$ で一番上が $k$ である山に積む場合を考えます．パンケーキ $i$ を引く確率は $\dfrac{1}{n - j}$ なので，dp[i][j + 1]について，$\sum_{k}^{i - 1}$ dp[k][j] / (n - j)です．
また $i$ を積む場合の確率はこれで網羅できていることになるので，その期待値は $\sum_{j}$ dp[i][j] * d[i]です．
[展開する] 反省 確率DPは配るDPのほうが良いと思っているのに，なんで貰うDPにしたのか謎．
URL https://community.topcoder.com/stat?c=problem_statement&pm=14811
概略 有向木の頂点に石を置いていくゲームを行う．葉には無条件で置いてよい．親に置くためには，その直接の子すべてに石が置かれていなければならない．また，任意のタイミングで石を取り除くことができる．根に石を置いた時点でゲームは終了する．
各頂点には重み $w$ が付いている．石が置かれている頂点 $i$ について $W = \sum w_i$ が逐一計算され，ゲームのスコアは $\max W$ である．スコアの最小値を求める．
方針 操作を先読みしたいときにはメモ化再帰が有効です．
dp[i] := iに石を置く操作をするときのスコアの最小値とします．頂点iの子がL，Rであるとき，iに石を置く操作には以下の工程が考えられます．
Lに石を置く dp[L] Rに石を置く dp[R] Lに石を置く操作を一通り行った後，Rに置く操作を行う．またはその逆．これは小さい方を選択できる． min(w[L] + dp[R], w[R] + dp[L]) LとRの両方に石が置かれていて，iに石を置く w[i] + w[L] + w[R] dp[i]はこのうちの最大値を取ります．子が0, 1つの場合も同様に計算できます．
[展開する] 反省 操作順を親と子の重みだけで評価できると思って時間を溶かす．そんなわけない．
URL https://community.topcoder.com/stat?c=problem_statement&pm=14010
概略 泣き顔とは，2つのセミコロンでアンダースコア1つ以上を囲んだもののことを言う．正規表現では;_+;である．
与えられたmessageをいくつかの部分列に分ける分け方のうち，過不足なく泣き顔が作れる分け方は何通りあるか．
方針 dp[i][a][b] := iまで見て使っていない";"がa個，";_+"がb個とします．過不足なく使うことを考えると，解はdp[|message|][0][0]です．
kmjpさんのブログの言葉を借りて，;_+;は「閉じている」，;_*は「開いている」と表現すると次のような遷移が考えられます．
セミコロンが来たとき 新たに開く dp[i][a][b] += dp[i - 1][a - 1][b] 1つ閉じる dp[i][a][b] += dp[i - 1][a][b + 1] * (b + 1) アンダースコアが来たとき 開いている;のみの状態に追加する dp[i][a][b] += dp[i - 1][a + 1][b - 1] * (a + 1) 開いている;_+の状態に追加する dp[i][a][b] += dp[i - 1][a][b] * b [展開する] 反省 最初，普通に数学をして壊滅した．DP解に目標を絞るも，dp[i][a][b] := iまで見て使っていない';'がa個，'_'がb個からなかなか進まなかった．;，;_のような区別の仕方は典型なので，気づけなかったのは反省．
参考 ABC104D - We Love ABC
URL https://community.topcoder.com/stat?c=problem_statement&pm=15257
概略 単純無向グラフ $G$ が与えられる．$G$ の橋を含まないような誘導部分グラフのうち，頂点数が最大となるものを求める．
方針 要は，$G$ から橋だけを残したグラフについての最大独立集合問題である．このグラフは明らかに森であるから，木DPが使える．
参考 制約が甘いので橋の検出にはUnionFindを使う．各辺ごとにそれを除いたグラフを構築し，端点の連結性を判定する．
[展開する] 反省 本番では橋の検出までしかできなかった．最大独立集合問題であることにはなんとなく気付いていたが，名前だけが先走った．「NP困難じゃん…」
dp等の初期化も忘れずに．