2017-08-22から1日間の記事一覧

Typical DP Contest G - 辞書順

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

Typical DP Contest O - 文字列

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

AOJ 0627 Train Fare (鉄道運賃)

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

Typical DP Contest J - ボール

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_ball 解法 期待値を求める問題.bitDP か線形方程式を解くところだが,|S| = 1024 なので後者は厳しい.なので bitDP でやる.dp[S] := すでに倒れたものが S の状態である時からはじめて,すべてのものを…

Typical DP Contest N - 木

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