パナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231)
GとH、解法に使う技術はそれなりにわかりやすくても、応用のさせ方がなかなか高度。
(逆に言うと知識の有無が出やすかった?)
問題文が少しややこしいが、太郎に i、次郎に j を渡すとして、 喧嘩が発生しないのは以下の条件に言い換えられる。
(Ai,Bi) を二次元座標と捉えると、条件を満たす位置関係が把握しやすくなる(気がする)。
サンプル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
これは、点全体を Ai 基準でソートするとよい。
Ai の小さい方からFenwick Treeなどのデータ構造に登録していくと、 「今まで登録した中で、Bi 以上の点の個数」を数えればよいことになり、 これは O(logN) で高速に求められる。
Ai が同じ点については、境界も含まれるので
今回は Bi の大きい方から先にデータ構造に登録されていなければならない。
最初のソート順に気をつける。
また、Ai,Bi とも全く同じ点が k 個あったとしたら、
それらはどう渡してもよいので、k2 個の渡し方が存在する。
Ai,Bi の一方でも異なれば、条件を満たしつつ 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 の流量を流さなければならない。
これを実現するのが「最小流量制約付き最小費用流」で、 少しグラフの作り方を変えると、単純な最小費用流に変換できる。
まず、前提として
というように考え方を拡張する。
この考えのもとでは、上記のグラフは dS=H+W,dT=−(H+W)、他は dv=0 と表現できる。
この上で、流したい辺にはあらかじめ流したように dv を変更する。
つまり、
最後に、超超頂点1)を P,Q として、
とし、P→Q に、P から出ている辺の容量合計だけ流してやれば、答えとなる。