問題文 http://codeforces.com/contest/789/problem/D 解法 まず，同じ辺を2回通るパスという時点でオイラーツアーが思い浮かびます． 自己辺を考えるのはめんどうなので，とりあえずない場合を考えると，条件を満たすパスがあるかどうかは，「一度のDFSによ…

問題文 http://codeforces.com/contest/785/problem/E 解法 平方分割 + 2次元BITで解いた．[0...m] x [0...n] で二次元．m は n / sqrt(n)． l[i] から r[i] の間に完全に含まれているブロックは BIT 上で計算し，端っこの部分は生で持っている配列を使って…

問題文 http://codeforces.com/contest/785/problem/D 解法 条件に合う部分列の，一番右端の "(" の位置を総当りして計算します． その位置から左に（その位置自体も含めて）"(" が $x$ 個あり，右に ")" が $y$ 個ある時，求める答えは $\displaystyle \sum…

問題文 http://codeforces.com/contest/884/problem/F 解法 最小費用流で解ける． まず，各アルファベットに対応する26個の頂点と，N / 2 個からなる文字列の前半（ないし後半）に対応する頂点をもつグラフをつくる． それぞれのアルファベットから，文字列…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2294 解法 ゴールから見るDPでやります．dp[i][j][k] := 高さ (H から) i まで見た時に，位置 j にいて，それまでに猫が k 本引いているような確率とします． 高さ 1 から i までに，うさ…