DP高速化:いもす法
区間分割していく DP を普通にやると になる (オレンジの出荷もそう)。それを累積和を用いて高速化する。 ジャッジページへのリンク 問題文へのリンク 類題とか drken1215.hatenablog.com 問題概要 (意訳) 個の正の整数 が与えられる。これらをいくつかの連…
AtCoder
AtCoder800点
AGC-C
黄色diff
数え上げ問題
操作
操作後の結果の数え上げ
操作によって作れるものの集合を考える(判定関数を考える)
変数変換して扱いやすい同型な問題を見出す
条件の言い換え
DP
操作:circular_shift
0と1の問題
操作をK回まで行える
DP高速化
DP高速化:いもす法
DP高速化:累積和
グラフ・盤面・数列の個数の数え上げ
こういう問題めっちゃ好き！！！ 問題へのリンク editorial 問題概要 '0' と '1' のみからなる長さ の文字列が与えられる。以下の操作を 回以上 回以下まで行うことができる。 i < j であって S[ i ] = '0'、S[ j ] = '1' であるような (i, j) を選ぶ S[ j ]…
AtCoder
AtCoder700点
ARC-D
平均に関する問題
平均値制約を総和制約に変換する
特殊なmod
格子点をmodごとに分類する
戻すDP
DP
ナップサックDP
DP高速化
DP高速化:いもす法
DP高速化:累積和
前処理
多項式・形式的冪級数
個数重複も考慮したナップサックDP
数え上げ問題
各kに対して
各要素ごとに独立
入力が定数個
差分更新
in-place DP
黄色diff
K飛ばしで累積和
すごく NTT したくなる 問題へのリンク 問題概要 正の整数 が与えられる。 をそれぞれ 個以上 個以下とってくる方法のうち、平均が となるものの個数を素数 で割ったあまりを、各 に対して求めよ。 制約 考えたこと まず、平均制約を次のように言い換える。…
AtCoder
AtCoder400点
ABC-D
DP
DP高速化
DP高速化:累積和
累積和
いもす法
DP高速化:いもす法
数え上げ問題
部分和
多項式・形式的冪級数
級数和を求める
形式的冪級数の高等演算
水色diff
DP 高速化系問題。こういうのが緑 diff になるようになったんかーー (水色 diff にアップグレードした！) 問題へのリンク 問題概要 マスからなるマス目が与えられる。また、 個の互いに disjoint な区間 が与えられる。この区間に属する整数からなる集合を …
