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

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

個数重複も考慮したナップサックDP

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

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

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

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

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

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

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

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

AtCoder ARC 028 D - 注文の多い高橋商店 (赤色)

戻す DP を履修して行く!!! 問題へのリンク 問題概要 個の正の整数 と正の整数 が与えられる。以下の 個のクエリに答えよ。 整数 が与えられる 以下の条件を満たす 0 以上の整数の組 () の個数を 1000000007 で割ったあまりを求めよ 制約 考えたこと この…

AtCoder ABC 153 E - Crested Ibis vs Monster (緑色, 500 点)

個数制限なしナップサック!!!!!!! 問題へのリンク 問題概要 種類の魔法を駆使して、HP が のモンスターを倒したい。 番目の魔法は、魔力を だけ消費して、モンスターの HP を だけ減らすことができる モンスターの HP を 0 以下にするのに消費する魔…

diverta 2019_2 D - Squirrel Merchant (青色, 600 点)

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

AOJ 1167 ポロック予想 (ICPC 国内予選 2010 C) (250 点)

いわゆる、重複ありのナップサック問題 問題へのリンク 問題概要 整数 を最小個数の四面体数 (重複あり) の和として表せ。 解法 四面体数は、mC3 の形で表される。 重複ありのナップサックも、うまくやれば、種類数の線形オーダーで効率的に解けることの練習…

AOJ 2370 RabbitWalking (JAG 冬合宿 2010 day3-B) (600 点)

これを解いていたおかげで ARC 099 E - Independence がすぐに思いつけた感はあるかも。むしろ制約的に ARC 099 E の完全上位互換だと言える。 問題へのリンク 問題概要 頂点 辺の無向単純グラフが与えられる。 このグラフが「奇数長のサイクルがない」とい…