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

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

ナップサックDP

AtCoder ABC 327 E - Maximize Ratin (水色, 475 点)

式がいかめしくて戸惑うけど、DP 自体は比較的単純 問題へのリンク 問題概要 個の値 が与えられる。 これらの中から順序を保っていくつか選ぶ。選び方のスコアは、 個の整数 を選んだとしたとき、 で与えられる。このスコアの最大値を求めよ。 制約 考えたこ…

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

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

AtCoder ABC 322 E - Product Development (緑色, 475 点)

chokudai さんの思想が詰まった問題 問題へのリンク 問題概要 個の開発案がある。これらの開発案によって上昇し得るパラメータが 種類ある。 開発案 () を採用すると、パラメータ () の値が だけ上昇する。その分、 のコストがかかる。 すべてのパラメータを…

AtCoder ABC 321 F - #(subset sum = K) with Add and Erase (青色, 525 点)

「戻す DP」または「FPS」で! 問題へのリンク 問題概要 最初、箱は空である。以下の操作を 回行う。各操作後において、以下の値を答えよ。 箱に入っているボールをいくつか選ぶ方法であって、ボールに書かれた数値の総和が となる方法の個数を 998244353 で…

AtCoder ABC 320 F - Fuel Round Trip (黄色, 550 点)

少し重たかった。でもいい問題。JOI にありそう。 問題へのリンク 問題概要 数直線上に 箇所の燃料補給所がある。 番目の補給所は次のようになっている。 座標 にある 補給すると、現在の HP が であるとき、HP が になる (コストとして を支払う) 今、高橋…

CodeQUEEN 2023 決勝 E - Good Partition

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

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 でよかった! 問題へのリンク 問題概要 のグリッドがある。各マスはすでに白色 (文字 '.') …

AOJ 0461 奇数の精と偶数の精 (PCK 2021 予選 問題 9)

少し前処理が面倒な DP。PCK の予選突破ライン上の問題のようですね! 問題へのリンク 問題概要 個の整数 が黒板に書かれている (各整数は 100 桁までありうる)。 奇数の精と、偶数の精がいる。 奇数の精は、黒板に書かれている数字がすべて奇数となるように…

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

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

AtCoder ABC 303 D - Shift vs. CapsLock (茶色, 400 点)

ランレングス圧縮をする問題に一瞬見えるかもしれない。でもそんなことしないで、最初から最後まで綺麗に DP で殴れる! 問題へのリンク 問題概要 文字 'a' と 'A' のみからなる長さ の文字列 が与えられる。 以下のキーボード操作を繰り返すことで、この文…

EDPC (Educational DP Contest) M - Candies

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

AtCoder ABC 281 D - Max Multiple (緑色, 400 点)

部分和問題の応用問題! 問題へのリンク 問題概要 個の非負整数 が与えられれる。 これらの整数から 個選んで、総和が の倍数となるようにする。その値として考えられる最大値を答えよ。 の倍数にするのが不可能な場合は -1 を答えよ。 制約 前提知識 この問…

AtCoder ABC 245 C - Choose Elements (茶色, 300 点)

EDPC C - Vacation と良く似た問題だと思う!! あと、幅が狭いグリッドでは DP が疑われることが結構多い! 問題へのリンク 問題概要 長さが の数列が 2 つ ( と ) 与えられます。 各 に対して、 と のいずれかを選ぶことで、新たに数列 を作ります。 こう…

TDPC (Typical DP Contest) G - 辞書順

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

AtCoder ABC 049 C - 白昼夢 (ARC 065 C) (緑色, 300 点)

ABS (AtCoder Beginner Selection) の 9 問目に選んだ問題! 問題へのリンク 問題概要 英子文字からなる長さ の文字列 が与えられます。 をいくつかの連続する文字列に分割して、かつそれらの文字列がすべて "dream", "dreamer", "erase", "eraser" のいずれ…

JOI 本選 2011 B - 古本屋 (AOJ 0561, 難易度 6)

こういうのは DP! ジャッジページ AOJ の問題文 問題概要 冊の古本があって、 番目の本のベース価格は 円である。またこれらの本は 10 種類のジャンルに分かれており、 番目の本のジャンルは で与えられる。 これらの本から 冊を古本屋で売りたい。ただし同…

TDPC (Typical DP Contest) A - コンテスト

部分和問題とほとんど一緒なのだけど、意外と詰まるかもしれない。 問題へのリンク 問題概要 個の正の整数 の中からいくつか選んで総和をとる。作ることのできる整数が何通りあるか求めよ。 制約 考えたこと この問題とよく似た部分和問題とは次のような問題…

JOI 春合宿 2008 day2-1 Nile.Com (難易度 6)

いかにも ABC-E にありあそうな DP!! ジャッジへのリンク 問題文へのリンク これとか似てる atcoder.jp 問題概要 個の店がある。 日間にわたって、いずれか 1 つの店で買い物をする。 日目に 番目の店で買い物をしたときの値段は で与えられる (10 の倍数)…

JOI 本選 2012 C - 夜店 (AOJ 0573, 難易度 6)

左右からナップサックした結果を前処理する系! (他の解法もあり) 問題へのリンク editorial 問題概要 (意訳) (実際の問題文は時刻に関する問題) 個の品物がある。それぞれ の番号がついている。番号が の品物は 価値が 重さが となっている。これらを 2 つ…

JOI 予選 2014 D - 部活のスケジュール表 (AOJ 0595, 難易度 6)

J, O, I の 3 人しかいないと、意外と bit DP を発想しづらいかもしれない。でもこういうのめっちゃ見るね。 問題へのリンク 問題概要 J 君と、O 君と、I 君の 3 人が所属する部活動がある。 日間の活動が行われる。それぞれの日において責任者が誰なのかが…

JOI 本選 2014 B - IOI饅頭 (AOJ 0599, 難易度 6)

まさにナップサック問題!!! 問題へのリンク 問題概要 個の饅頭がある。それぞれ 円で売り出そうとしている (全部売るとは限らない)。 饅頭を得るための箱をいくつか購入することにした。箱は 種類あって、 番目の箱は 饅頭を 個まで詰められる 仕入れるの…

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

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

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

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

AOJ 2638 Hyperrectangle (JAG 夏合宿 2014 day2-J) (550 点)

りんごさんセット!!! 問題へのリンク 問題概要 次元空間において () を満たす部分の体積を とすると は整数値となる。この整数値を 1000000007 で割ったあまりを求めよ。 制約 考えたこと 最初は色々迷走していた。三次元の場合を考えていて思っていたの…

AtCoder ARC 058 E - 和風いろはちゃん (橙色, 700 点)

5 + 7 + 5 = 17 なの、よくできてる! 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の数値からなる長さ の数列 であって、以下の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 整数 が存在して、 の区間 の総和が の区間 の…

AOJ 2566 Restore Calculation (JAG 模擬地区 2013 B) (350 点)

これが生まれて初めての作問だった!!! AOJ-ICPC で ☆4 個ついてて嬉しい! 問題へのリンク editorial 問題概要 虫食算が与えられる。解の個数を 1000000007 で割ったあまりを求めたい。 より正確には長さ の 3 個の文字列 が与えられる。これらは '?' か …

AOJ 2333 僕の友達は小さい (JAG 夏合宿 2010 day2-D) (500 点)

これ面白い!! 問題へのリンク editorials 問題概要 個の正の整数 と、正の整数 が与えられる。 個の整数の中からいくつか選ぶ方法のうち、以下の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 選んだ数の総和は 以下である 選んだ数の総…

CODE FESTIVAL 2016 Final F - Road of the King (橙色, 1000 点)

面白かった!!!DEGwer さんの pdf より。 問題へのリンク 問題概要 頂点のグラフが与えられる。初期状態では 1 本も辺が張られていない。 このグラフに、頂点 1 を始点とする長さ のウォークをとり、ウォークに沿って有向辺を張っていく。有向辺の張られた…

AOJ 2955 Two Colors Sort (HUPC 2019 day2-D)

これ好き!!! 問題へのリンク editorial 問題概要 の順列が与えられる。これらの順列のうち、 個を赤く塗り、 個を青く塗る方法であって、次の条件を満たすようにするものは存在するか、判定せよ。 赤い要素同士を swap することを好きな順序で好きな回数…