\(O(N )\) で解きます。 問題 リンクはこちら 概要 $$ \sum _ {l = 1} ^ N \sum _ {r = l} ^ N \mathrm{min} \left( a _ l, a _ {l + 1} , \ldots , a _ r \right) $$ を求めなさい。 解法 editorial解は平衡二分木を用いたものです。Pythonの標準ライブラリ…

\(O( \log N )\) で解きます。 問題 リンクはこちら 解法 editorialのDP解法をベースに考えます。 \(i\) 文字目を決める際の遷移は \(i\) の値によらず常に固定なので、漸化式を行列の累乗に落とし込むことができます。64次元線形空間の行列を手書きで入力す…

\(O(N)\) で解きます。 問題 リンクはこちら 概要 $$ \underset{P}{\min} \sum _ {i=1} ^ {N} (X _ i - P) ^ 2 $$ を求めなさい。 解法 制約が \( N \leq 100,\ X _ i \leq 100\) と小さいので、 \(X\) の取りうる範囲すべてを調べても \(O(NA) \, (A = \max…

\(O(N \log K )\) で解きます。また、本問題の「与えられたグラフが巡回置換に分解できる」という特性をほとんど用いていないので、 \(P\) が順列でない場合でも少し書き換えるだけで解くことができます。 問題 リンクはこちら 解法 ダブリングで前処理をし…