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

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

DP

KUPC 2019 E - 根付き森二人用ゲーム

200 点となってるけど、他の 300 点と同じくらいに感じた! 頭の整理が大変だった...けど、面白い 問題へのリンク 問題概要 個の根付き木が与えられる。それぞれの木の頂点数は となっている。これらの木を使って、ゲームを行う。 最初、駒がスタート地点 (…

AtCoder ABC 143 E - Travel by Car (500 点)

この Floyd--Warshall は天才すぎる! 問題へのリンク 問題概要 頂点 辺の重み付き無向単純グラフが与えられる。容量 の燃料タンクがあって、長さ の辺を通ると、タンクの燃料残量が だけ減少する。 各頂点では燃料を補給できて、補給すると満タン (容量 の…

AOJ 2439 箱根駅伝 (JAG 夏合宿 2012 day3aF)

sky さんの提唱した、代々伝わる名問題!!! 問題へのリンク 問題概要 人の選手が箱根駅伝を走っている。テレビの放送では中継所で各チームの通過順位と共に前の中継所からの順位変動が表示される。 ある中継所を 番目に通過したそれぞれの選手について、前…

AtCoder ABC 142 E - Get Everything (500 点)

個人的には bitDP は「順列を全探索するもの」というイメージがあるけど、今回はそれとはまた違う bitDP という感じ! 問題へのリンク 問題概要 個の宝箱がある。宝箱を開けるための鍵が 個あって、それぞれの鍵はいくつかの宝箱に対応している。鍵 を用いる…

Educational Codeforces Round 73 D. Make The Fence Great Again (R1700)

いかにも Greedy にできなさそうなので DP!!! 問題へのリンク 問題概要 長さ の整数数列 が与えられる。今、数列の各項の値を整数分だけ増加させるなどして、数列のどの隣り合う二項も値が異なるようにしたい。 項目を 1 増加させるのに要するコストは で…

Codeforces Round #586 E. Tourism (R2200)

結構好き...だけど、完全既出だったらしい 問題へのリンク 問題概要 頂点 辺の連結な単純無向グラフが与えられる。各頂点 には重み が付いている。頂点 を始点としたウォークであって、ウォーク上のどの辺 に対してもその直後が ではない (直前に通った辺を…

はじめての DP の練習用問題まとめ ~ フィボナッチな DP ~

DP

0. DP のはじめの一歩 ふと、人生で初めて「この問題は DP だよ」という状況に直面した方が、DP へのはじめの一歩を踏み出すのに良さそうな問題たちをまとめたくなった。 DP のはじめの一歩な問題として、どんな問題がふさわしいかについて、AtCoder Educati…

Codeforces Round #584 - Dasha Code Championship F. Koala and Notebook (R2600)

勉強になった!!!!! 「辺番号または頂点番号が辞書順最小な最短路」を求める考え方が炸裂する感じ。 最短路として使われうる辺を列挙しておく (この考え方自体が典型) その辺をうまいこと活用しながら探索する という典型の流れになっている。 問題への…

AtCoder ABC 141 E - Who Says a Pun? (500 点)

もう文字列は怖くないっ!!! 文字列検索に関するライブラリが充実していれば怖いものがない。でも文字列のことを知らなくても実は DP でも解ける!!! Suffix Array Z-algorithm (editorial 解) ロリハ + 二分探索 「ロリハ + 二分探索」の高速化 (editor…

Codeforces Round #584 - Dasha Code Championship E. Rotate Columns (R2400)

すんごく横長な行列に関する問題だけど、実は横の長さを縦の長さ以下にできるというタイプ。 そうすれば の問題に帰着できて、。あとは の bit DP...なのだが、TLE がとれなかった。微妙に詰めが甘かった。。。 問題へのリンク 問題概要 の行列があたえられ…

AtCoder ARC 074 E - RGB Sequence (800 点)

わかってる...!わかってるんだ!!!この問題が超ド典型だってことくらい!!!!!!!! でも典型だからって、そんなパッと解けるわけじゃない。すごく苦手なんだこういうの。。。 問題へのリンク 問題概要 マスを RGB の三色で塗り分ける 通りの方法のう…

AtCoder ABC 132 F - Small Products (600 点)

こういう風にルートが出てくるの、こどふぉだとよく見るね。 ありがちなのが、長さ の線分を整数長ごとに分割するとき、分割の中に登場する長さの種類は 通りしかないとか、そういう形でよく出てくる。 問題へのリンク 問題概要 整数 が与えれる。 長さ の正…

CPSCO 2019 session2 E - Mogu Mogu Gummi (600 点)

二乗の木 DP のいい練習問題!!!!! ついでに DP で最適化したい対象を入れ替えるタイプの問題でもある。そのようなタイプとして難しい問題としては、以下がある。 drken1215.hatenablog.com 問題へのリンク 問題概要 頂点の重みつきの根つき木が与えられ…

AtCoder ABC 130 E - Common Subsequence (500 点)

共通部分列に関する問題!!!!! 最長共通部分列問題は有名だけど、今回は共通部分列を数え上げる問題。 問題へのリンク 問題概要 2 つの数列 が与えられる。 と の共通部分列が何通りあるかを求めよ。 ただし、 や から抜き取ってできる文字列が同じもの…

AOJ 3048 Averaging (AUPC 2018 day2-J)

二乗の木 DP の例題として、すごくいい感じ!!! 問題へのリンク 問題概要 頂点のツリーが与えられて、各頂点 には 人がいる。いま、人を移動させて、各頂点の人数の最大値と最小値との差が 1 になるようにしたい。 1 人が辺 1 個分を移動するのに必要なコ…

AtCoder ARC 101 E - Ribbons on Tree (900 点)

すごく典型的な「二乗の木 DP」!!!!! そして包除原理との組み合わせ。 問題へのリンク 問題概要 を偶数とする。 頂点の木が与えられる。 頂点を 組の 2 つペアにする方法のうち、各ペアを結ぶパスをすべて考えたときに全辺が被覆されるようなものの個数…

diverta 2019_2 F - Diverta City (900 点)

冷静になれば自然な構成ではあるね...企業コンのラス問だと身構えてしまうのがよくない 問題へのリンク 問題概要 頂点からなる重みつき無向単純完全グラフであって、 通り考えられるハミルトンパスに対して始点と終点が同じものを同一視して得られる 通りの…

diverta 2019_2 E - Balanced Piles (800 点)

最初は絶望感がヤバイタイプの問題。とても解ける問題には見えない。でも落ち着くと解ける。 こういう問題を作れるのはすごい。 問題へのリンク 問題概要 個のマスに積み木を重ねていく。最初はどのマスも 0 段である。以下の操作を繰り返して、最終的にすべ…

diverta 2019_2 D - Squirrel Merchant (600 点)

操作が複雑な順序性をもつ問題だけど、こういうのは「操作の流れを単純化して、こういうものだけ考えればよい」という考察を狙うのが常だとは思う。 問題へのリンク 問題概要 問題画像そのままを 解法 1: 自分のやつ 僕が最初に考えたことは、例えば 「最初…

AtCoder ABC 129 E - Sum Equals Xor (500 点)

まさにこの考え方で解ける問題 drken1215.hatenablog.com 今回の問題も桁 DP でもよいのだが、実は桁 DP しなくても解ける。 問題へのリンク 問題概要 正整数 が二進数表記で与えられます。 以下の条件を満たす非負整数 の組がいくつ存在するか求めてくださ…

AtCoder ABC 129 C - Typical Stairs (300 点)

いわゆる本当に最初の入門という感じの DP だね。 問題へのリンク 問題概要 段の階段があって、現在は 0 段目にいる。 高橋君は一歩で 1 段か 2 段上がることができる。ただし 段目は壊れていて、そこに足を踏み入れることはできない。 高橋君が 0 段目から …

Chokudai SpeedRun 002 L - 長方形 β (600 点)

面白かった 問題へのリンク 問題概要 個の長方形がある。各辺の長さは整数値である。 この長方形から何個か選んでマトリョーシカを作りたい。最大で何重にできるか? 長方形の縦と横をひっくり返してもよい。 制約 考えたこと もし長方形が縦横ひっくり返す…

AtCoder AGC 007 D - Shik and Game (1200 点)

すごく典型的な問題。 現代なら企業コンの 800 点問題とかに出そうな雰囲気だね。このころはまだあまり典型じゃなかったのかな。 問題へのリンク 問題概要 一直線上に 個の点 があってこの順に並んでいる。さらに左側に 、右側に がある。 からスタートする …

AtCoder ABC 126 D - Even Relation (400 点)

とても教育的なツリーの探索問題。 問題へのリンク 問題概要 頂点の重み付き無向グラフが与えられる。このグラフの各頂点を白黒に塗る方法であって 同色に塗られた 2 頂点はどれを選んでも、その間のパスの長さは偶数である という条件を満たすものを求めよ…

AtCoder AGC 002 F - Leftmost Ball (1600 点)

すごく楽しかった。 問題へのリンク 問題概要 色 のボールがそれぞれ 個ずつあります。 個のボールを好きな順序で並べ、各色について最も左側にあるボールを色 へと塗り替えました。 最終的な色の並びとして考えられる個数を 1000000007 で割ったあまりを求…

AtCoder ABC 114 D - 756 (400 点)

editorial は「75」という整数の特徴をフル活用している。 そして 75 という整数の特徴を活用しない DP による方法もあると説いている。 ここでは 75 という整数の特徴も活用せず、DP もしない (といっても DP への改良は容易) 愚直な全探索でも通った。 問…

diverta 2019 E - XOR Partitioning (800 点)

時間かかりすぎた。シンプルで面白い。 問題へのリンク 問題概要 要素からなる 0 以上の整数列 が与えられる。 これをいくつかの連続した部分列に分割する 通りの方法のうち、各連続区間の XOR 和が互いに等しくなるものが何通りあるか、1000000007 で割った…

AtCoder AGC E - Go around a Circle (1500 点)

本番これを間に合わせられなかったのが悔しい 問題へのリンク 問題概要 円周を 等分して、それぞれの弧を赤か青に塗る方法のうち、 'R' と 'B' のみからなる長さ の文字列 が与えられて 円周上のどの端点から出発しても弧を順番に左右どちらかに 回たどって…

AtCoder ARC 085 D - ABS (500 点)

何も考えずにゲーム DP 毎ターン「実質的に取れる選択肢が二通りしかない」というパターン という包畜を含む教育的問題。 問題へのリンク 問題概要 先手と後手は初期状態で と と書かれたカードを持っている。 枚の山札があってそれぞれ の数値が書かれてい…

AtCoder AGC 033 D - Complexity (1000 点)

これを解けなかったのが強い敗北感。 DP 配列が巨大になりそうなときに、最適化する対象を入れ替えるテクは今までなんども見ているのにそれが思いつかない思考の硬さを思い知らされた。 問題へのリンク 問題概要 0 と 1 のみからなる行列の複雑度を すべて同…