格子点をmodごとに分類する
個置きに累積和をとるの、3 ヶ月前の僕だったら思いつかなかったかもしれない。 問題へのリンク 問題概要 整数 が与えられる。また、長さ の 0 と 1 のみからなる文字列 が与えられる。文字列 に対して以下の操作を行うことができる。 文字列 中の文字 "0" …
AtCoder
AtCoder700点
ARC-D
平均に関する問題
平均値制約を総和制約に変換する
特殊なmod
格子点をmodごとに分類する
戻すDP
DP
ナップサックDP
DP高速化
DP高速化:いもす法
DP高速化:累積和
前処理
多項式・形式的冪級数
個数重複も考慮したナップサックDP
数え上げ問題
各kに対して
各要素ごとに独立
入力が定数個
差分更新
in-place DP
黄色diff
K飛ばしで累積和
すごく NTT したくなる 問題へのリンク 問題概要 正の整数 が与えられる。 をそれぞれ 個以上 個以下とってくる方法のうち、平均が となるものの個数を素数 で割ったあまりを、各 に対して求めよ。 制約 考えたこと まず、平均制約を次のように言い換える。…
ちょっと問題を理解するのが大変かもしれない 問題へのリンク 問題概要 ロボットと 回ジャンケンをする。ロボットの出す手はあらかじめすべてわかっている。 グーを出して勝つと 点 チョキを出して勝つと 点 パーを出して勝つと 点 が得られる。ただし 回目…
AtCoder
AtCoder800点
条件の言い換え
二分探索
二次元平面上のN点の問題
いもす法
二次元いもす法
格子点をmodごとに分類する
集計処理
ある量を固定して考える
累積和
二次元累積和
赤色diff
ARC-like
すごく詰め切るのに時間かかった 問題へのリンク 問題概要 (意訳) 二次元平面上に 個の座標 (格子点) が与えられる。正の整数 が与えられる。 まず、各座標について「 座標を だけ増減する」「 座標を だけ増減する」という操作を好きなだけ繰り返す。ただし…