問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_lexicographical 解法 まず， next_pos[i][c] := i番目以降で，文字 c があらわれる一番前の位置 とします． ここで，dp[i] を dp[i] := i 番目の文字を「使った上で」，i 番目以降のユニークな文字列は何…

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_string 解法 dp[i][j] := i 番目の文字まで見た時，同じ文字が連続している場所が j 箇所あるような場合の数 とする． 例えば，AABBBCDEE なら，連続している箇所は4箇所と数える．次に追加する文字が f[i…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0627 解法 まず首都からの最短経路を求めるほかどうしようもないので，BFSで最初に求めておく． このとき，任意の頂点について，すべての最短経路でのその頂点の親と子を求めておく． 経路…

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_ball 解法 期待値を求める問題．bitDP か線形方程式を解くところだが，|S| = 1024 なので後者は厳しい．なので bitDP を疑う．ただし、このためには遷移をDAGにしないといけない。dp[S] := すでに倒れたも…

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_tree 解法 まず，一番最初に書き始める辺を定めることを考える． そして，定めた辺を縮約したグラフ上で，以下の問題を解けば良い． 「縮約してできた頂点を根として，そこから辺を生やしていく方法は何通…