またしても、in-place DP のいい練習になった！！！ 最初は絶望感が漂うのだけど、これも結局「必要条件を列挙したら十分条件になっていた」系な気もする。 問題へのリンク 問題概要 個のロボットと、 個の穴が一直線上に並んでいる。ロボットは穴に重なると…

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

これまたちょっと重たい。。。 問題へのリンク 問題概要 折れ線グラフが与えられる。これは に対して () を結んでいる。あらゆる水平な直線を考えたときの、折れ線グラフのうち直線の上に来ている部分を連結成分ごとに分解したとき、連結成分の個数として考…

「 番目の値を求めよ」「メディアンを求めよ」といった問題では、二分探索法が有効なことが多々ありますね。 問題へのリンク 問題概要 長さ の数列 が与えられます。 この数列の連続する区間として考えられるものは 個あります。そのそれぞれの区間について…