解法1： 考え方 解法1：考え方（解放のみメモ） N〜1の橋を封鎖したときのツアーの長さを基準にして，順番に隣の橋を封鎖した場合を差分で計算する．$a これに気づくとimos法が使える．アライグマ「D問題は、1とNを結ぶ橋を封鎖したときを基準にすると、「ど…

方法1： 考え方 方法2：座標圧縮+いもす法 考え方 回答例 方法1：考え方$a, b$をイベント発生日としてまとめて扱い，イベント発生日を小さい順に考えると簡単に処理できる． Editorial - AtCoder Beginner Contest 188方法2：座標圧縮+いもす法考え方日をind…

考え方 回答例 考え方区間$[l, r]$を考える（$1 \leq l \leq r \leq M$）．$l$を固定し，$r$を良い数列になるまで動かす．このとき，$r^{\prime} \geq r$に対し，区間$[l, r^{\prime}]$に対応する数列はすべて良い数列なので，個数をカウントする．上を$l=1,…

考え方（いもす法） 回答例 考え方（いもす法）Editorial - Tokio Marine & Nichido Fire Insurance Programming Contest 2022（AtCoder Beginner Contest 256)ログインしている人数をいもす法で求められる． ログイン人数が0→1以上となるところが区間の左端…

考え方 回答例（配るDP & いもす法） 考え方配るDPなら区間への遷移．貰うDPなら区間への遷移．よって，よくある累積和を取りながらのDP． 【類題】 EDPC - M - Candies - 競プロはじめました ABC249E - RLE - 競プロはじめました 回答例（配るDP & いもす法…

EDPC - M - Candies - 競プロはじめましたの類題だが，今回の方がはるかに難しい．．． 配るDP & いもす法 貰うDP & 累積和 配るDP & いもす法文字数が少ない問題に帰着させられそうなので，dpを考える．「dp[i][j]=圧縮前の長さが$i$・圧縮後の長さが$j$の…

ある区間から遷移する問題． 貰うDPなら累積和（ある区間からの遷移），配るDPならいもす法（ある区間への遷移）となる．個人的には，いもす法の方がわかりやすい． 方法1 (貰うDP & 累積和) 考え方 回答例 方法2 (配るDP & いもす法) 考え方 回答例 背景 方…

$\mathrm{dp}$で考える場合， $\mathrm{dp}$を中心に考えると，「貰うDP + 累積和」になり， 累積和（階差）を中心に考えると，「配るDP + 階差 (いもす法)」になる ということだと思う． 貰うDP + 累積和 考え方 回答例 配るDP + 階差 (いもす法?) 考え方 …