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

考え方 回答例 考え方\begin{aligned} &\sum_{i = 1}^{M} i \times A_{k + i} \\ &=\sum_{i = 1}^{M} (k + i) \times A_{k + i} - k\sum_{i = 1}^{M} A_{k + i} \end{aligned}だから，累積和を2種類計算しておけば良い．回答例 N, M = map(int, input().spli…

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

解法1：式変形 考え方 回答例 解法1：式変形考え方愚直に計算する方法を考えて，そのあと計算量を落とすことができるか検討する．$x, y$を全探索すると\begin{aligned} f(x, y) = Lx + \sum_{k = x + 1}^{N - y} A_{k} + yR \end{aligned}の最小値を計算でき…

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

考え方 回答例 考え方クエリごとに$X$と$A_{i}$の差を求めるとTLEする．クエリの計算量$O(Q)$は絶対に必要なので，操作回数を高速に求める必要がある．ここで， $A_{i} $A_{i} \geq X$なら操作回数は$A_{i} - X$ だから，答えは\begin{aligned} \sum_{i (A_{…

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

考え方 回答例 参考 考え方数列$C$の等しい部分に分割して考えて，それぞれの区間での$A_{1},...,A_{M}$の最大値が$O(1)$で求められれば，全体では$O(N)$計算できる．数列$C$の要素が全て$a$である区間を考える．$B,A$の前の区間からの持ち越し分を$b_{0}, a…

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 + 階差 (いもす法?) 考え方 …

解法1 考え方 回答例 解法2 考え方 回答例 解法1考え方例えば，入力例1を考えると，下図の筆算が計算できれば良い．繰り上がりを考えなければ，各桁の足し算は$X$の累積和になっている． 後は，繰り上がりを考慮すれば良い．筆算回答例 import itertools X =…