$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解は単純にすべてのペアについて調べるだけ…