2020-10-04から1日間の記事一覧
AtCoder
AtCoder700点
ARC-D
平均値に関する問題
平均値制約を総和制約に変換する
特殊なmod
格子点をmodごとに分類する
戻すDP
DP
ナップサックDP
DP高速化
DP高速化:いもす法
DP高速化:累積和
前処理
多項式・FPS(形式的冪級数)
個数重複も考慮したナップサックDP
数え上げ問題
各kに対して
Greedy:各要素について独立に考えてよい
入力が定数個
差分更新
in-place DP
黄色diff
K飛ばしで累積和
すごく NTT したくなる 問題へのリンク 問題概要 正の整数 が与えられる。 をそれぞれ 個以上 個以下とってくる方法のうち、平均が となるものの個数を素数 で割ったあまりを、各 に対して求めよ。 制約 考えたこと まず、平均制約を次のように言い換える。…
AtCoder
旧ARC-D
DP
戻すDP
ナップサックDP
クエリ処理問題
前処理
数え上げ問題
個数重複も考慮したナップサックDP
N個のものうち1個を変更・削除したものを解く
補集合を考える
制約条件:総和=K
赤色diff
戻す DP を履修して行く!!! 問題へのリンク 問題概要 個の正の整数 と正の整数 が与えられる。以下の 個のクエリに答えよ。 整数 が与えられる 以下の条件を満たす 0 以上の整数の組 () の個数を 1000000007 で割ったあまりを求めよ 制約 考えたこと この…