パナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231)
GとH、解法に使う技術はそれなりにわかりやすくても、応用のさせ方がなかなか高度。
(逆に言うと知識の有無が出やすかった?)
問題文が少しややこしいが、太郎に $i$、次郎に $j$ を渡すとして、 喧嘩が発生しないのは以下の条件に言い換えられる。
$(A_i, B_i)$ を二次元座標と捉えると、条件を満たす位置関係が把握しやすくなる(気がする)。
サンプル1 3 | x 2 | x 1 | x 0 +------------ 50 100 150
ある点を太郎に渡す $i$ と固定した場合、そこより↖にある点が、$j$ として条件を満たす。
3 | x | 2 | _________x (150, 2) を i とすると 1 | x j はラインより↖の範囲にある点。 0 +------------ (ただし境界を含む) 50 100 150
これは、点全体を $A_i$ 基準でソートするとよい。
$A_i$ の小さい方からFenwick Treeなどのデータ構造に登録していくと、 「今まで登録した中で、$B_i$ 以上の点の個数」を数えればよいことになり、 これは $O(\log{N})$ で高速に求められる。
$A_i$ が同じ点については、境界も含まれるので
今回は $B_i$ の大きい方から先にデータ構造に登録されていなければならない。
最初のソート順に気をつける。
また、$A_i,B_i$ とも全く同じ点が $k$ 個あったとしたら、
それらはどう渡してもよいので、$k^2$ 個の渡し方が存在する。
$A_i,B_i$ の一方でも異なれば、条件を満たしつつ $i,j$ を交換することはできないが、 全く同じであれば交換も可能なので、そこを数え忘れないようにする。
最小流量制約付き最小費用流。
今回の問題設定を少し簡単にすると、典型っぽい問題となる。
行と列の数が同じで、全ての行・列に「ちょうど」1個の黒い駒がある状態にするのは、 過去に類題があったと思うが、単純な最小費用流で解ける。
まず、行を表す $H$ 個の頂点、列を表す $W$ 個の頂点、超頂点 $S,T$ を用意する。
以上の辺を張ったら、$S→T$ に流量 $H$ を流す最小コストを求めれば答え。
1つの行・列に何個でも置いてよい(その方がコストが安いなら)。
上記の辺の張り方で、$S→行$ と $列→T$ の容量上限が $1$ ではなくなる。
また、最終的に $S→T$ にいくら流せば良いか(駒を何個置くのが最適か)もわからない。
それでもまぁ、容量上限は INF とするとして、 流量もまぁ多くとも $H+W$ 流せば十分で残りを流すためのバイパスを作るとして、 以下のような最小費用流グラフ(仮)が作れる。
行 列 ,_--③ -, S→行: 容量INF,コスト0 _,- ① \ 行→列: 容量1 ,コストCi H+W → ⓢ `---④ ---ⓣ → H+W 列→T : 容量INF,コスト0 |`--- ②----' /| | `---⑤ -' | `-----------------' ←バイパス(容量INF,コスト0)
ただしこのままだと、当然コスト $0$ のバイパスに全部流れてしまう。
「$S→行$」「$列→T$」の各辺には、それぞれに少なくとも $1$ の流量を流さなければならない。
これを実現するのが「最小流量制約付き最小費用流」で、 少しグラフの作り方を変えると、単純な最小費用流に変換できる。
まず、前提として
というように考え方を拡張する。
この考えのもとでは、上記のグラフは $d_S=H+W,d_T=-(H+W)$、他は $d_v=0$ と表現できる。
この上で、流したい辺にはあらかじめ流したように $d_v$ を変更する。
つまり、
最後に、超超頂点1)を $P,Q$ として、
とし、$P→Q$ に、$P$ から出ている辺の容量合計だけ流してやれば、答えとなる。