−目次

パナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231) F,H問題メモ
- F - Jealous Two
  - 問題
  - 解法
- H - Minimum Coloring
  - 問題
  - 解法

パナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231) F,H問題メモ

パナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231)

GとH、解法に使う技術はそれなりにわかりやすくても、応用のさせ方がなかなか高度。
（逆に言うと知識の有無が出やすかった？）

F - Jealous Two

問題

$N$ 種類のプレゼント候補があり、太郎と次郎に1個ずつ渡す
- $i$ 番目の候補をもらった時の嬉しさは、太郎は $A_i$ 、次郎は $B_i$
- 2人に同じ種類のプレゼントを渡してもよい
太郎と次郎の少なくとも一方にとって、「相手がもらったプレゼントの自分にとっての嬉しさ」が、「自分がもらったプレゼントの自分にとっての嬉しさ」より大きいと喧嘩になる
プレゼントの渡し方は $N^2$ 通りあるが、喧嘩にならないようなものの個数を求めよ
$1 \le N \le 2 \times 10^5$
$0 \le A_i,B_i \le 10^9$

解法

問題文が少しややこしいが、太郎に $i$ 、次郎に $j$ を渡すとして、喧嘩が発生しないのは以下の条件に言い換えられる。

$(A_i \ge A_j) AND (B_i \le B_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$ を交換することはできないが、全く同じであれば交換も可能なので、そこを数え忘れないようにする。

Python3

$i=j$ の場合、 $(A_i,B_i)$ と $(A_j,B_j)$ が異なる場合、同じ場合、の3つを別々に数える冗長なコードとなっている。

最初に $(A_i,B_i)$ 毎に個数を数え、同じものはまとめて処理すれば、よりスッキリ書ける。

        
          
          
              
              from collections import Counter
from operator import add
 
 
class FenwickTreeInjectable:
    def __init__(self, n, identity_factory, func):
        self.size = n
        self.tree = [identity_factory() for _ in range(n + 1)]
        self.func = func
        self.idf = identity_factory
        self.depth = n.bit_length()
 
    def add(self, i, x):
        i += 1
        tree = self.tree
        func = self.func
        while i <= self.size:
            tree[i] = func(tree[i], x)
            i += i & -i
 
    def sum(self, i):
        i += 1
        s = self.idf()
        tree = self.tree
        func = self.func
        while i > 0:
            s = func(s, tree[i])
            i -= i & -i
        return s
 
    def lower_bound(self, x, lt):
        """
        累積和がx以上になる最小のindexと、その直前までの累積和
 
        :param lt: lt(a, b) で a < b ならTrueを返す関数
        """
        total = self.idf()
        pos = 0
        tree = self.tree
        func = self.func
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k > self.size:
                continue
            new_total = func(total, tree[k])
            if lt(new_total, x):
                total = new_total
                pos += 1 << i
        return pos + 1, total
 
    def debug_print(self):
        prev = 0
        arr = []
        for i in range(self.size):
            curr = self.sum(i)
            arr.append(curr - prev)
            prev = curr
        print(arr)
 
 
n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
points = []
compress = set()
for a, b in zip(aaa, bbb):
    points.append((a, -b))
    compress.add(b)
points.sort()
 
b_dict = {b: i + 1 for i, b in enumerate(sorted(compress))}
 
fwt = FenwickTreeInjectable(n, int, add)
ans = n
for i, (a, b) in enumerate(points):
    bi = b_dict[-b]
    lo = fwt.sum(bi - 1)
    ans += i - lo
    fwt.add(bi, 1)
 
cnt = Counter(points)
for _, c in cnt.most_common():
    if c == 1:
        break
    ans += (c * c - c) // 2
 
print(ans)

            

        
      

H - Minimum Coloring

問題

$H \times W$ のグリッドに、 $N$ 個の白い駒が置かれている
駒 $i$ は $(A_i,B_i)$ に置かれていて、コスト $C_i$ で黒い駒に変更できる
全ての列・全ての行に黒い駒が1個以上ある状態にしたい
必要なコストの和の最小値を求めよ
$1 \le H,W,N \le 10^3$
$1 \le C_i \le 10^9$
最初、白い駒は全ての列・全ての行に1個以上ある

解法

最小流量制約付き最小費用流。

各行各列にちょうど1個の場合

今回の問題設定を少し簡単にすると、典型っぽい問題となる。

行と列の数が同じで、全ての行・列に「ちょうど」1個の黒い駒がある状態にするのは、過去に類題があったと思うが、単純な最小費用流で解ける。

まず、行を表す $H$ 個の頂点、列を表す $W$ 個の頂点、超頂点 $S,T$ を用意する。

駒が $(A_i,B_i)$ にあったら、 $A_i→B_i$ に容量 $1$ 、コスト $C_i$ の辺を張る
$S$ から各行頂点に容量 $1$ 、コスト $0$ の辺を張る
各列頂点から $T$ に容量 $1$ 、コスト $0$ の辺を張る

以上の辺を張ったら、 $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$ の流量を流さなければならない。

これを実現するのが「最小流量制約付き最小費用流」で、少しグラフの作り方を変えると、単純な最小費用流に変換できる。

最小費用流の負辺除去 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

まず、前提として

SとTだけでなく、各頂点に水の過不足 $d_v$ が決まっている
- 正なら余っている（始点となり得る）
- 負なら不足している（終点となり得る）
- 全体を通しての過不足の総和は $0$

というように考え方を拡張する。
この考えのもとでは、上記のグラフは $d_S=H+W,d_T=-(H+W)$ 、他は $d_v=0$ と表現できる。

この上で、流したい辺にはあらかじめ流したように $d_v$ を変更する。
つまり、

$S→行$ に1流す
- $S$ の余剰が1減る（合計 $H$ 減って $d_S=W$ となる）
- 行の余剰が1増える
$列→T$ に1流す
- $T$ の不足が1減る（合計 $W$ 減って $d_T=-H$ となる）
- 列の不足が1増える

最後に、超超頂点¹⁾を $P,Q$ として、

$d_v \gt 0$ （正）の頂点には、 $P→v$ の容量 $d_v$ 、コスト $0$ の辺を張る
$d_v \lt 0$ （負）の頂点には、 $v→Q$ の容量 $|d_v|$ 、コスト $0$ の辺を張る

とし、 $P→Q$ に、 $P$ から出ている辺の容量合計だけ流してやれば、答えとなる。

Python3

上記の説明と $P,Q ↔ S,T$ の意味が逆なので注意

        
          
          
              
              class MinimumCostFlow:
    def __init__(self, n):
        self.n = n
        self.edges = [[] for _ in range(n)]
        self.INF = 10 ** 18
 
    def add_edge(self, from_, to, capacity, cost):
        es, et = self.edges[from_], self.edges[to]
        ls, lt = len(es), len(et)
        es.append([capacity, to, cost, lt])
        et.append([0, from_, -cost, ls])
 
    def _trace_back(self, sink, predecessors):
        p = predecessors[sink]
        while p is not None:
            v, i = p
            yield self.edges[v][i]
            p = predecessors[v]
 
    def flow(self, source, sink, required_flow):
        n = self.n
        edges = self.edges
        INF = self.INF
        trace_back = self._trace_back
 
        res = 0
        while required_flow:
            dist = [INF] * n
            dist[source] = 0
            predecessors = [None] * n
 
            while True:
                updated = False
                for v in range(n):
                    if dist[v] == INF:
                        continue
                    for i, (remain, target, cost, _) in enumerate(edges[v]):
                        new_dist = dist[v] + cost
                        if remain and dist[target] > new_dist:
                            dist[target] = new_dist
                            predecessors[target] = (v, i)
                            updated = True
                if not updated:
                    break
 
            if dist[sink] == INF:
                return -1
 
            aug = min(required_flow, min(e[0] for e in trace_back(sink, predecessors)))
            required_flow -= aug
            res += aug * dist[sink]
            for e in trace_back(sink, predecessors):
                remain, target, cost, idx = e
                e[0] -= aug
                edges[target][idx][0] += aug
        return res
 
 
h, w, n = map(int, input().split())
mcf = MinimumCostFlow(h + w + 4)
p = h + w
q = p + 1
s = q + 1
t = s + 1
INF = 1 << 60
for _ in range(n):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    b += h
    mcf.add_edge(a, b, 1, c)
for i in range(h):
    mcf.add_edge(s, i, 1, 0)
    mcf.add_edge(p, i, INF, 0)
for j in range(h, h + w):
    mcf.add_edge(j, t, 1, 0)
    mcf.add_edge(j, q, INF, 0)
mcf.add_edge(p, q, INF, 0)
mcf.add_edge(s, p, w, 0)
mcf.add_edge(q, t, h, 0)
ans = mcf.flow(s, t, h + w)
print(ans)

            

        
      

¹⁾

語感が前前前世みたい