競技プログラミング問題精選: 考察技法と実装(ICPC/APIO/NOI対策)
P6880 JOI 2020 Final オリンピックバス
有向グラフが与えられる。辺を通るコスト \(C_i\)、1本の辺を反転させるコストを \(D_i\) とする。頂点 \(1\) から \(n\) へ、さらに \(n\) から \(1\) へ移動するとき、辺の反転を高々1回まで許したときの最小コスト和を求めよ。
全ての辺に対して反転を試すのは非効率なので、影響を解析する。\(f(s,t)\) を元のグラフでの \(s\) ...
6月3日 16:05 投稿
USACO 2021年オープンコンテスト金問題の解法アプローチ
問題1: 農場の統一された牛群
各要素の前後で最初に現れる同一要素の位置をprevおよびnext配列で管理します。区間[l, r]が有効となる条件は、next[l] > rかつprev[r] < lを満たすことです。
左端点lを固定し、右端点の有効性をセグメント木で管理します。prev[r] < lを満たすrを二重ポインタで追跡しながら、セグメント木の対応位置をインクリメントします。各lで ...
6月2日 17:58 投稿