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

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

DP高速化

JOIG 春合宿 2023 day2-2 White Light (難易度 8)

セグメント木を用いた DP 高速化! 問題へのリンク editorials 問題概要 'R' と 'G' と 'B' のみからなる長さ の文字列 が与えられる。以下の操作を繰り返し行うことで、"RGB" を繰り返す文字列となるようにしたい。 (操作) 連続する 個以下の文字を消す 目…

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

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

AtCoder ARC 026 C - 蛍光灯 (試験管青色)

セグ木上で DP する問題として、人生で最初に解くべき問題と言えるかもしれない! 問題へのリンク 問題概要 個の区間がある。各区間 は、 で重みは である。 これらの区間からいくつか選ぶ方法のうち、 全体を被覆するものについて、最小重みを求めよ。 制約…

CodeQUEEN 2023 決勝 E - Good Partition

これは学びの深い DP 問題! 問題へのリンク 問題概要 長さ の数列 がある (負値もありうる)。これらの数列をいくつかの連続する区間に分割する。 区間分割の仕方を最適化したときの、各区間における「最大値と最小値の差」の総和として、考えられる最大値を…

AtCoder ABC 318 Ex - Count Strong Test Cases (橙色, 650 点)

コンテスト終了から 8 秒後の AC で泣いた。でも、分割統治 FFT が自力で書けてよかった。想定解法は FPS だった。 問題へのリンク 問題概要 次の問題がある。 の順列 と が与えられる。 これらをもとに次のように、頂点数 、辺数 の有向グラフを作る。 頂点…

Codeforces Round 892 (Div. 2) E. Maximum Monogonosity (R??00)

つい最近 CodeQUEEN 決勝 E 問題でも出てきた「最大値の最大化」典型テクニック!!!! 問題へのリンク 問題概要 長さ の 2 つの数列 と が与えられる。今、互いに disjoint な区間群 をとる ( は自由)。ただし、区間の長さの総和がちょうど となるようにす…

AtCoder ABC 311 F - Yet Another Grid Task (青色, 525 点)

最初、各マスをタスクに見立てて、タスクの依存関係を考える DAG 上で DP できないかなどと考えたけど、うまくいかなかった。普通にグリッドを左から舐めていく DP でよかった! 問題へのリンク 問題概要 のグリッドがある。各マスはすでに白色 (文字 '.') …

AtCoder ABC 265 F - Manhattan Cafe (黄色, 500 点)

次元空間という、いかめしいものが出てくるけど、あまり関係ない。DP 高速化が本質。 問題へのリンク 問題概要 次元空間上に 2 つの格子点 , が与えられる。 これらとのマンハッタン距離がともの 以下であるような格子点の個数を 998244353 で割ったあまりを…

AtCoder ABC 256 G - Black and White Stones (黄色, 600 点)

opt さんの得意系って感じだった! 問題へのリンク 問題概要 一辺の長さが整数 の正 角形がある。 頂点から始めて、周上に距離 1 ごとに黒い石か白い石を置いていく。 石の置き方のうち、各辺上にある白い石の個数が等しくなるようなものの個数を 998244353 …

AtCoder ABC 300 Ex - Fibonacci: Revisited (銅色, 600 点)

「TDPC T - フィボナッチ」の亜種とも言える問題ですね。 問題へのリンク 問題概要 () によって定義される数列を考える。 整数 が与えられので、 AND を満たすすべての非負整数 に対する の総和を 998244353 で割った余りを求めよ。 制約 考えたこと この問…

TDPC (Typical DP Contest) T - フィボナッチ

Boston--Mori 法を履修した! 問題へのリンク 問題概要 () によって定義される数列において、 を 1000000007 で割ったあまりを求めよ。 制約 解法 0-indexed にして考えることにする。つまり、 () によって定義される数列において、 を求めることにする。 こ…

EDPC (Educational DP Contest) M - Candies

DP 高速化に累積和を使う問題! 問題へのリンク 問題概要 人の子ども に、 個の飴を分けることにした。 ただし、子ども に分ける飴は、 個以上 個以下のする必要がある。 各子どもへの飴の分け方の総数を、1000000007 で割ったあまりを求めよ。 制約 解法:…

AtCoder ABC 281 Ex - Alchemy (赤色, 600 点)

この平方分割のやり方はちゃんとマスターしたい 問題へのリンク 問題概要 種類のレベル 1 の宝石がある。各種類のレベル 1 の宝石は無限個ある。 個の宝石を合成することで、レベル の宝石を作ることができる。ただし、その 個の宝石は次の条件を満たす必要…

AtCoder ABC 213 H - Stroll (赤色, 600 点)

オンライン分割統治 FFT 面白いね!! 公式解説がとても丁寧なので、備忘録程度に 問題へのリンク 問題概要 頂点数 のが与えられます。 組の頂点対に対して、次のように無向辺を張っていきます。 組めの頂点対に対しては 長さ 1 の辺が 本 長さ 2 の辺が 本 …

AtCoder ABC 212 H - Nim Counting (橙色, 600 点)

コンテスト中にアダマール変換を思い出せたのはよかった! 問題へのリンク 問題概要 整数 と 個の整数 が与えられます。次の条件を満たすような Nim をすべて考えます。 山の個数は のいずれかである 各山の石の個数は のいずれかである このような Nim の盤…

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

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

JOI 春合宿 2010 day1-3 Stairs (難易度 6)

区間分割していく DP を普通にやると になる (オレンジの出荷もそう)。それを累積和を用いて高速化する。 ジャッジページへのリンク 問題文へのリンク 問題概要 (意訳) 個の正の整数 が与えられる。これらをいくつかの連続した区間に分割していく。ただしど…

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

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

AtCoder AGC 049 D - Convex Sequence (橙色, 1000 点)

最初は二次元 FFT が必要な気分になっていて右往左往していた。個数制限なしナップサック問題になるのは面白かった! 問題へのリンク 問題概要 正の整数 が与えられる。長さ の非負整数列 であって という条件を満たすものの個数を、1000000007 で割ったあま…

AtCoder ABC 183 E - Queen on Grid (水色, 500 点)

三乗の解法はすぐに出てくるので、それを上手に高速化する! 問題へのリンク 問題概要 のグリッドが与えられる。"." マス (通路) には行けるが "#" マス (壁) には行けない。左上のマスから右下のマスへと行きたい。毎回のターンで以下のいずれかの行動をと…

AtCoder AGC 045 C - Range Set (橙色, 800 点)

面白かった!! 問題へのリンク 問題概要 すぬけくんは長さ の文字列 を持っている。最初、 のすべての文字は 0 である。 すぬけくんは,以下の 2 種類の操作を好きな順序で好きな回数行うことができます. の連続する 文字を選んで,それらをすべて 0 にす…

AtCoder AGC 046 C - Shift (黄色, 800 点)

こういう問題めっちゃ好き!!! 問題へのリンク editorial 問題概要 '0' と '1' のみからなる長さ の文字列が与えられる。以下の操作を 回以上 回以下まで行うことができる。 i < j であって S[ i ] = '0'、S[ j ] = '1' であるような (i, j) を選ぶ S[ j ]…

Codeforces Round #681 (Div. 1) D. Sum (R2800)

から落とせる気がまったくしなかった... 問題へのリンク 問題概要 個の広義単調増加数列 が与えられる。 それぞれの数列から、先頭から 個ずつとってきた値の総和の最大値を求めよ。ただし でなければならないものとする。 制約 考えたこと 個数に関する con…

AtCoder ARC 107 D - Number of Multisets (黄色, 600 点)

いろんな DP が考えられそう! 問題へのリンク editorial 問題概要 正整数 が与えらる。以下の条件を全て満たす有理数の多重集合は何種類存在するか、998244353 で割ったあまりを求めよ。 多重集合の要素数は 多重集合の要素の総和は 多重集合の要素は全て (…

KUPC 2020 E - Sequence Partitioning

近年非常によく見る DP 高速化系問題!! 問題へのリンク 問題概要 長さ の 3 つの数列 が与えられる。 いま、数列 をいくつかの連続する部分列に分割することを考える。 分割 に対して、スコアを、各区間についての以下の値の最小値として定める。 その区間…

AOJ ???? Numbers on Papers (KUPC 2020 B)

DP 高速化系問題 問題へのリンク 問題概要 のグリッドが与えられる。各マス には数値 が書かれている。 各行から 1 個ずつ数値を選んで行順に並べてできる数列を考える。そのような数列は 通り考えられるが、そのうち広義単調増加なものが何通りあるか、1000…

yukicoder No.1068 #いろいろな色 / Red and Blue and more various colors (Hard)

(x - a)(x - b) ... (x - z) みたいなやつの計算 問題へのリンク 問題概要 個の箱がある。箱 には色 のボールが入っている。以下の 個のクエリに答えよ。 各クエリは 以下の整数 が与えられる 各箱から 個ずつボールを取り出す方法であって、取り出されたボ…

AtCoder ABC 178 D - Redistribution (緑色, 400 点)

総和が一定値になるような数列の数え上げ、最近よく見る! 問題へのリンク 問題概要 整数 が与えられる。 すべての項が 3 以上の整数で、その総和が であるような数列の個数を 1000000007 で割ったあまりを求めよ。 制約 解法 (1):素直に DP まずは素直な D…

AtCoder ARC 104 D - Multiset Mean (黄色, 700 点)

すごく NTT したくなる 問題へのリンク 問題概要 正の整数 が与えられる。 をそれぞれ 個以上 個以下とってくる方法のうち、平均が となるものの個数を素数 で割ったあまりを、各 に対して求めよ。 制約 考えたこと まず、平均制約を次のように言い換える。…

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

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