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

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

DP高速化:セグメント木

AtCoder EDPC W - Intervals

まさに、「DP 配列をセグメント木に載せる」というセグ木上の in-place DP ですね!!! 一部の競プロ界隈では、俗に実家 DP などと呼ばれてたりしていたものです。 問題へのリンク 問題概要 0 と 1 のみからなる長さ の文字列を 0-1 文字列と呼ぶことにしま…

AtCoder EDPC Q - Flowers

まさに重み付き LIS ともいうべき問題ですね。 問題へのリンク 問題概要 本の花が横一列に並んでいます。 左から 番目の花の高さは で、美しさは です。 太郎君は何本かの花を抜き去ることで、次の条件が成り立つようにしようとしています。 「残った花を左…

AtCoder ARC 115 E - LEQ and NEQ (黄色, 700 点)

間に合わなかった!!!悔しい!!! 問題へのリンク 問題概要 長さ の数列 が与えられます。以下の条件を満たすような、長さ の数列 の個数を 998244353 で割ったあまりを答えよ。 制約 考えたこと という条件は扱いづらいので、包除原理でやると良さそう。…

パ研合宿2020 第1日「SpeedRun」 N - 背の順

面白かった!セグ木を使ったけど、区間を複数個にする必要がないことから、しゃくとり法で線形でできるね! 問題へのリンク 問題概要 の順列 が与えられる。以下の操作を繰り返すことで、単調増加となるようにしたい。 区間 の要素をすべて削除する (コスト…

AtCoder ARC 108 E - Random IS (赤色, 700 点)

変なところでハマらないようにしたい... 問題へのリンク 問題概要 の順列 が与えられる。いま、これらの順列の各要素に印をつけていくことを考える。ただし、「印のついた要素が左から順に単調増加となるように並んでいる」という条件を常に満たす必要がある…

ACL Beginner Contest D - Flat Subsequence (水色, 400 点)

LIS を求める in-place DP を応用すればできる! でも、400 点問題で「DP 配列をセグ木に乗せて」「in-place に更新することで高速化する」という問題が出るとは思わなかった! in-place DP に馴染みのない方は先にこっちを qiita.com 問題へのリンク 問題概…

AOJ 3196 Increasing Sequence (AUPC 2020 day1-D)

in-place な DP にもっと慣れていきたい 問題へのリンク 問題概要 個の数列がある。 個目の数列は 個の要素からなる。 個目の数列の 番目の要素は と表す。 個目の数列から 1 個以下の要素を選び、選んだ要素を元の数列の順番通りに並べた数列を とする。 数…

yukicoder No.973 余興

Deque に似てる。けど、Deque と違って、先手と後手がとりうる選択肢は常に一緒 (最初、先手は左から、後手は右からと誤読した)。 問題へのリンク 問題概要 長さ の数列に対し、先手は左から順に、後手は右から順にとっていく。どのターンもとった値の合計値…

AtCoder ARC 101 F - Robots and Exits (赤色, 900 点)

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

AtCoder ARC 085 F - NRE (赤色, 1000 点)

実家なんだと思うけど...意外とはまりやすい問題な気 がします 問題へのリンク 問題概要 マスの値が最初はすべて 0 に固定されている。以下の 種類の操作の中からいくつか選んで操作する。その結果と、 とのハミング距離の最小値を求めよ。 番目の操作では、…

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

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

AOJ 2941 LISum (RUPC 2019 day1-E)

最長増加部分列 (LIS) がセグ木上のインライン DP で求められることを思い出せば、それを少し頑張るとできる。 問題へのリンク 問題概要 長さ の数列 が与えられる。数列 の最長増加部分列 (狭義単調増加) のうち、その総和の最大値を求めよ。 制約 考えたこ…