けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

DP値を利用して状態復元

AtCoder ABC 325 G - offence (黄色, 575 点)

o......f...(.....)... のようなパターンで、(.....) の中身が消せるような場合を最初見落とした。 問題へのリンク 問題概要 長さ の文字列 に対して、次の操作を好きな回数だけ行える。操作後の文字列の長さとして考えられる最小値を求めよ。 が連続する部…

AtCoder ABC 325 F - Sensor Optimization Dilemma (青色, 500 点)

個の区間を、プチ区間たちを用いて、最小コストですべて被覆しようという問題。DP 状態の持ち方を工夫することで計算量を小さくしたい。 問題へのリンク 問題概要 個の区間があって、長さが である。これらすべてを 2 種類の区間で被覆したい。 長さが であ…

TDPC (Typical DP Contest) G - 辞書順

いわゆる部分列を扱う DP ですね。経路復元も含んでいて少し難しい問題です。 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられます。 の部分列 (連続でなくてもよい) として考えられる文字列をすべて考えたとき、その中で辞書順で 番…

JOI 本選 2014 D - フクロモモンガ (AOJ 0601, 難易度 8)

dp の値そのものを用いて現在状態を復元する系の問題。 問題へのリンク editorial 問題概要 個の木 があって、それぞれ高さは である。 フクロモモンガは最初は、木 1 の高さ の地点にいる。フクロモモンガは木を飛び移りながさ、最終的に木 の頂上にたどり…

JOI 二次予選 2021 C - イベント巡り (AOJ 0693, 難易度 8)

これはアレだ!!! DP の最適値そのものの値を利用して次の遷移を作る系。フクロモモンガなんかもそういう系の問題だった覚えがある。 問題へのリンク 問題概要 2 つの町 (1 と 2) がある。 個のイベントがあって、それぞれ町 において発生し、時刻 に始ま…

AISing Programming Contest 2019 E - Attack to a Tree (橙色, 600 点)

二乗の木DPの問題にようやく出会えました! 問題へのリンク 問題概要 頂点のツリーがあって、各頂点には値 が割り振られている。今ツリーのエッジを何本か取り除いて何個かの連結成分に分けたとき 連結成分内に含まれる全ノードの頂点の重みの和が負の値 連…

AOJ 2370 RabbitWalking (JAG 冬合宿 2010 day3-B) (600 点)

これを解いていたおかげで ARC 099 E - Independence がすぐに思いつけた感はあるかも。むしろ制約的に ARC 099 E の完全上位互換だと言える。 問題へのリンク 問題概要 頂点 辺の無向単純グラフが与えられる。 このグラフが「奇数長のサイクルがない」とい…

AtCoder AGC 004 D - Teleporter (黄色, 800 点)

こういう系の問題、なかなか提出が怖くなるやつ。こういうのは背水の陣状態じゃないと躊躇してしまいそう... 問題へのリンク 問題概要 頂点数 、辺数 の有向グラフが与えられる。 どの頂点から出る辺数も 1 どの頂点から出発しても必ずノード 1 (root) にた…

yukicoder 733 分身並列コーディング

一見 な bitDP だけど、これはアレだ!!! よくある にできるやつだ!!!!! 問題へのリンク 問題概要 個の数 がある。これを最小個数のグループに分けて、各グループの合計値が 以下となるようにせよ。 制約 解法 とりあえず一見 な bitDP に見える。AGC…

AtCoder AGC 026 F - Manju Game (銀色, 2000 点)

ふと考えてみた。区間 DP っぽく にはなるな...なんて思っていたけどそこから落とせなかった...いやこれ何を食べたらこんな二分探索思いつけるようになるの!?!?!?!??? なにかこういう場面で二分探索すると上手く行くよ、というパターン的なものが…

TopCoder SRM 694 DIV1 Easy - TryShell

いい問題だった。 問題概要 0 以上 255 以下の整数が n 個与えられる。 この n 個の整数を 3 組に分ける方法のうち、各組の xor 和の総和が最大となるものを求めよ。(制約) ・3 解法 dp[ i+1 ][ j ][ k ] := i 番目までみたとき、二組の和がそれぞれ j, k の…