ferinの競プロ帳

競プロについてのメモ

ARC

エイシング プログラミング コンテスト 2019 E - Attack to a Tree

問題ページ 解法 木DPをする。dp[v][i][j] = (頂点vを根とする部分木でi回辺を切っていて頂点vの連結成分以外は問題文の条件を満たし、頂点vの連結成分が全てバッテリー(j=0)orそれ以外(j=1)のときの連結成分の頂点の重みの和の最小) とする。不可能な場合は…

ARC029 D - 高橋君と木のおもちゃ

問題ページ 二乗の木DPの練習として解いた。 解法 Mステップで使う玉は置かないという選択もできる。木の深い頂点から順番に置いていけば置いた玉が捨てられることはない。したがって、木の頂点にi個置くときはM個中の大きい方i個だけを置くとするのが最善の…

ARC 081 E - Don't Be a Subsequence

問題ページ arc081.contest.atcoder.jp 解法 まず、dp[i] = (区間[i, s.size())の部分文字列に含まれない最短の文字列の長さ)としたDPを考える。文字cがi番目以降ではじめて現れる位置をnext(i, c)と表記することにすると、このDPはdp[i] = min{dp[next(i, …

ARC079D Decrease (Contestant ver.)

問題ページ D - Decrease (Contestant ver.) 解法 n=50で考える。 k=0のとき 49 49 49 … 49 とする。 k=1のときは1回操作してこの数列になればよいので 99 48 48 … 48 k=2でも同様に 98 98 47 47 … 47 これを繰り返していくと、 k = 50 で 50 50 50 … 50 k =…

ARC079 C Cat Snuke and a Voyage

問題ページ C - Cat Snuke and a Voyage dijkstraで殴った

ARC023 B問題-謎の人物X

arc023.contest.atcoder.jpD回移動した後にたどり着ける点はD回移動の範囲内に収まり偶奇が一致する点です。したがってたどり着ける点についての全探索でO(RC)で解けます。

ARC022 B問題-細長いお菓子

arc022.contest.atcoder.jp重複した数が存在しない最大の領域を求める問題です。重複した数が存在するかどうかの判定ををunordered_setで行いました。unordered系のデータ構造はじめて使ったんですが衝突さえしなければO(1)でできるの便利ですね… 解いている…