\(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…