AtCoder

ARC057 D - 全域木

問題文 http://arc057.contest.atcoder.jp/tasks/arc057_d 解法 メモ化再帰で解きます. $rec(C) := $連結成分の状態が $C$ であるような状態から始めたときに,条件を満たすような辺の張り方の総数$A[i]$ を小さい方から張って順に張っていくとき,$A[i]$に…

ARC058 E - 和風いろはちゃん

問題文 http://arc058.contest.atcoder.jp/tasks/arc058_c 解法 X, Y, Z が小さいので bitDP でやります. dp[i][S] := i 番目まで見たときに,直前の和が X + Y + Z 以下になるところまでの状態が S であるような場合の数 とします. たとえば,X = 5, Y = …

ARC067 E - Grouping

問題文 http://arc067.contest.atcoder.jp/tasks/arc067_c 解法 dp[i + 1][j] := i 人以下のグループのみを用いて,あと j 人グループ分けされてない人がいるときの場合の数 という dp で解けます. 遷移は,use == 0 または C $$\displaystyle dp[i + 1][j …

Typical DP Contest Q - 連結

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_concatenation 解法 同じ文字列を複数選んでも良いので,何を使ったかを保存する必要はないです. 今作っている文字列の状態がどうか,がわかれば十分.そこで突然ですが,以下のような dp をします. dp[…

Typical DP Contest R - グラフ

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_graph 解法 どう考えても閉路は一つにまとめたいな~という気持ちになるので,とりあえずSCCしたあとのDAGの上で解くことを考えます. 一番端っこから引いていくのが当然良いので,トポロジカルソートして…

Typical DP Contest P - うなぎ

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_eel 解法 木の上でのDPなので,やはり根を適当に決めたあとのDFS木上で,部分木の結果を統合していくのが鉄則となります.根として適当に頂点 0 を選んで,そのDFS木上で考えます. 以下のような dp を考…

Typical DP Contest T - フィボナッチ

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_fibonacci 解法 今なら,通称きたまさ法とよばれている方法でやります. きたまさ法自体の説明は省略します.アイデアとしては,一般項を最初の K 項の線形結合で表そう,というものです. ソースコード #…

Typical DP Contest S - マス目

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_grid 解法 まず,この問題を解くにあたって以下の記事を大いに参考にさせていただきました.ありがとうございます. algoogle.hadrori.jpH が小さいので,それぞれのマスの連結関係をもちながら,列を左か…

Typical DP Contest M - 家

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_house 解法 まず階段を使うまえに,各階で部屋i -> j の移動経路が何パターンあるかを計算します. これは普通に dp[S][i][j] := 今まで訪れた部屋の集合が S である,i -> j の移動パターン とすれば求め…

Typical DP Contest K - ターゲット

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_target 解法 それぞれの円の左端と右端のpairである (x + r, x - r) を昇順ソートする. そのあと,-(x - r) についての最長増加部分列( (x - r) のまま考えるなら,最長減少部分列.右から左の向き)を…

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…

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 解法 まず,一番最初に書き始める辺を定めることを考える. そして,定めた辺を縮約したグラフ上で,以下の問題を解けば良い. 「縮約してできた頂点を根として,そこから辺を生やしていく方法は何通…

ARC065 E - へんなコンパス

問題文 http://arc065.contest.atcoder.jp/tasks/arc065_c 解法 とりあえずマンハッタン距離の有名なテクニックである,45度回転みたいなことをする. すると,a と b の距離は D = max(|x[a] - x[b]|, |y[a] - y[b]|) となり,以降コンパスで点の位置が変わ…

Typical DP Contest H - ナップザック

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_knapsack 解法 まず,色でソートしておく. すると以下の dp が書ける. dp[i][w][j][k] := i 番目まで見たとき,j 種類の色を使っていて,最後に使った色が k であって,重さの総和が w となるときの最大…

ARC081 E - Don't Be a Subsequence

問題文 http://arc081.contest.atcoder.jp/tasks/arc081_c 解法 今見ている位置から後ろの,各アルファベットの最も近い位置を持っておく. すると,今見ている頂点から始めた時,以降の部分列で現れない最小のものを求めることができる. 各アルファベット…

Typical DP Contest L - 猫

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_cat 解法 1 1つは今見ているのが何番目かに使うとして,もう1つを何にするかが問題.自分は,どの猫まで距離1以内に配置するか,と考えた.つまり dp[i][j] := i 番目の猫まで考えた時,i 番目の猫は"自分…

Typical DP Contest I - イウィ

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_iwi 解法 区間DP.dp[l][r] := [l, r) で最大何文字取り除けるか と定義する. まず,dp[l][r] = max(dp[l][i] + dp[i][r]) (i = l, ..., r) という遷移は,明らかだと思う. あとは,s[l...r) が完全に取…

ARC044 C - ビーム

問題文 http://arc044.contest.atcoder.jp/tasks/arc044_c 解法 この問題のポイントは,独立した部分問題に分割してしまう,ということ.よく考えると,縦方向の移動と横方向の移動は完全に独立して扱うことができることがわかる. なので,問題を1次元の同…

ARC054 C - たい焼き

問題文 http://arc054.contest.atcoder.jp/tasks/arc054_c 解法 2部グラフの完全マッチングの個数の偶奇性を問う問題. 当然数え上げるのは無理.しかし偶奇だけなら,行列式でわかる.与えられた隣接行列を Aとする. すると,完全マッチングの個数 M は,A…

ARC050 C - LCM 111

問題文 http://arc050.contest.atcoder.jp/tasks/arc050_c 解法 1 が A 桁続いたものと,1 が B 桁続いたものの最大公約数 G は,1 が gcd(A, B) 桁続いたものになる. 例えば 111111 (A = 6) と 1111 (B = 4) の最大公約数は,1 が gcd(6, 4) = 2桁続いたも…

ARC055 B - せんべい

問題文 http://arc055.contest.atcoder.jp/tasks/arc055_b 解法 dp[i][j][ate_max] := i 番目まで見て,j 個食べていて,現時点で最大のものを食べている(ate_max: bool) 状態から始めたとき,最終的に N を食べられる確率 と定義する. dp[N][j][1] が,確…

JOI 春合宿2015 コピー&ペースト2

問題文 http://joisc2015.contest.atcoder.jp/tasks/joisc2015_a 問題概要 文字列 S が与えられる. S に対して,クエリが N 個投げられる. 各クエリは A, B, C を持ち,これは S の部分文字列 [A, B) を位置 C の直前にコピー挿入することを意味する. 最…

ARC025 C - ウサギとカメ

問題文 http://arc025.contest.atcoder.jp/tasks/arc025_3 解法 制約をみて,なんとなく全頂点を始点としてダイクストラできるなーと検討はつく. とりあえず,目的地を決め打ちしてしまって,目的地を始点にダイクストラする. その後,得られた距離 d[i] …

ARC035 C - アットコーダー王国の交通事情

問題文 http://arc035.contest.atcoder.jp/tasks/arc035_c 解法 頂点数が小さいので,ワーシャルフロイドでよい. ただし,建設するたびにワーシャルフロイドすると間に合わない.よく考えると,x-y 間に橋を作ったときに最短経路が変わるのは,x-yを経由す…

ARC023 C - タコヤ木

問題文 http://arc023.contest.atcoder.jp/tasks/arc023_3 解法 典型 of 典型みたいな問題.L -1 -1 ... -1 R みたいな区間に分けて考えて,R - L を -1 にうまく分配するという問題になる. これはいわゆる重複組合せというやつ.高校数学でも頻出. という…

AGC004 D - Teleporter

問題文 http://agc004.contest.atcoder.jp/tasks/agc004_d 解法 首都が自己辺でなければならないのは,すぐ分かる.(ぱっとわからなくても実験すればわかるようになってる.) あとは制約から,与えられたグラフが首都を根とする木になっていることがわかる…

ARC006 C - 積み重ね

問題文 http://arc006.contest.atcoder.jp/tasks/arc006_3 解法 貪欲解で解くひとが多いと思うので,それ以外の解法を. この問題は,よく考えると「与えられたDAGの最小パス被覆を求めよ」と言い換えられる. 実際,x が y の上に積める,を y -> x という…

Typical DP Contest F - 準急

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_semiexp 解法 dp[i][j] := i 番目の電車まで考えた時,右端が j である (j=0: 停車, j=1: 通過) 場合の数 として更新していく. 右端で停車しない場合は単純に dp[i-1][0] + dp[i-1][1] でよい. 停車する…