問題文 https://atcoder.jp/contests/abc137/tasks/abc137_f 解法 想定解はかなり頭がいいが、今回は汎用的なラグランジュ補間で解く。 今 \(n\) 次の多項式 \(P(x)\) が \(P(x_i) = y_i ~(i = 0, \ldots, n)\) を満たすとする。このとき、$$P(x) = \sum_{i …

問題文 https://atcoder.jp/contests/ddcc2019-final/tasks/ddcc2019_final_d 解法 区間同士でうまくマージできるような形であればセグ木に乗せることができるので、とりあえずその方針で考えてみる。 2つの区間 A, B があって、それらをマージしたときに "D…

問題文 https://agc001.contest.atcoder.jp/tasks/agc001_c 解法 解説と（ちょっとだけ）違ったので一応書いておきます． まずBFSで全点対最短路を求めておいて，頂点 v から K より離れた頂点の数を sz[v] とします． あとは sz[v] の大きい方から貪欲に削…

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_cat 解法 1 1つは今見ているのが何番目かに使うとして，もう1つを何にするかが問題．自分は，どの猫まで距離1以内に配置するか，と考えた．つまり dp[i][j] := i 番目の猫まで考えた時，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) が完全に取…

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

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

問題文 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桁続いたも…

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

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

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

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

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