文字列に含まれる文字の種類数を $σ$ とおきます。 $O(N2^{σ})$ で解きます。 問題 リンクはこちら 解法 $σ = 1$ まずは $σ = 1$ の場合を考えてみましょう。このとき答えは明らかに $2^{N} - 1$ です。これをDPで解いてみることにします。配列 $g[i] \colon…

$O(N)$ で解きます。$O(N \log N)$ はこちら 問題 問題ページ 概要 $$ \max _ {1 \leq l \leq r \leq n} \left\lbrace (r - l + 1) \cdot \min _ {l \leq i \leq r} a _ i \right\rbrace $$ 解法 前回の続きです。今回は皿の大きさ順ではなく、シンプルに左…

$O(N \log N)$ で解きます。$O(N)$ はこちら 問題 問題ページ 概要 $$ \max _ {1 \leq l \leq r \leq n} \left\lbrace (r - l + 1) \cdot \min _ {l \leq i \leq r} a _ i \right\rbrace $$ 解法 以下では、載っているミカンが多い皿を「大きい皿」、少ない…

$O(N+M)$ で解きます。 問題 リンクはこちら 概要 $N$ 頂点 $M $ 辺の有向グラフが与えられる。極小のサイクルを一つ見つけよ。 解法 問題文に書かれている条件は「概要」のように言い換えることができます。editorialでは 最小のサイクルを見つける サイク…

$ O(M ^ 2) $ (一般の $N, M $ については $ O(NM ^ 2) $ ) で解きます。 問題 リンクはこちら 概要 $N$ 個のスイッチと $M $ 個の電球がある。$i$ 番目のスイッチ $ (1\leq i\leq N) $ は $ k _ i $ 個の電球 $s _ {i1},s _ {i2},\ldots,s _ {ik _ i}(1 \le…

\(O(N \log N)\) で解きます。 問題 リンクはこちら 概要 与えられる点の集合 \(S\) の中から二点を選ぶとき、それらを結んだ直線の傾きが \(-1\) 以上 \(1\) 以下になる組み合わせはいくつあるか？ 解法 editorial解は単純にすべてのペアについて調べるだけ…

\(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\) が順列でない場合でも少し書き換えるだけで解くことができます。 問題 リンクはこちら 解法 ダブリングで前処理をし…

\(O(\sqrt N )\) で解きます。 問題 リンクはこちら 概要 $$ \sum _ {i=1} ^ {N} i \cdot \mathit{d}(i) $$ を求めなさい。 解法 公式editorialの \(O(N)\) 解法を高速化することを考えたいです。結局、 \(S[k] := \sum _ {i=1} ^ {k} i\) として $$ \sum _ …