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

考え方 回答例 考え方以下を愚直にやってみた． 計算をミスらないように実装するのが大変．．．アライグマ「F問題は算数なのだ……。行ごとの和を考えると、奇数行目と偶数行目がそれぞれ等差数列になってるから、和の公式を使ってO(1)で求められるのだ！」htt…

考え方 回答例 考え方\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}の最小値を計算でき…

考え方 回答例 考え方$B(x)$の最高次か最低次から順番に決めていくことができる． （「$C(x)$の最高（低）次数＝$A(x)$の最高（低）次数×$B(x)$の最高（低）次数」であるため，一意に決まる）制約でゼロでないのは最高次なので，次数が高い順に決めていく．…

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

【関連】 ABC230E - Fraction Floor Sum - 競プロはじめました 方法1：エラトステネスの篩（ふるい） 考え方 回答例 方法2：等差数列の和 考え方 回答例 方法3：和を√Nで分割 考え方 回答例 方法1：エラトステネスの篩（ふるい）考え方約数を考える問題では…

【関連】 ABC172D - Sum of Divisors - 競プロはじめました 考え方 回答例 参考 考え方$[x]$は他の問題では$\lfloor x \rfloor$で表すことが多いので，こちらを使う．もちろんそのまま計算しては間に合わないので，$\biggl\lfloor \dfrac{N}{i} \biggr\rfloo…