【ABC469D】
条件を満たす組み合わせ

1. 問題 The Big Two

• $N$ 人のプレイヤーでトーナメントが $M$ 回行われ、$m$ 回目の決勝に進んだのは $A_m$ と $B_m$ です。
• $1 \le x < y \le N$ のうち、どのトーナメント戦においても、プレイヤー x とプレイヤー y の少なくとも一方が決勝に勝ち上がっている組（x, y）の個数を求めます。
• 制約は $2 \le N \le 2 \times 10^5$、$1 \le M \le 2 \times 10^5$、$1 \le A_i < B_i \le N$ で、すべて整数です。
• 入力は 1 行目に $N\ M$、続く $M$ 行に $A_i\ B_i$ が与えられ、答えを 1 行で出力します。

2. 素朴なコード（AC11 TLE20）

まずは、素朴に x y の組み合わせを総当りでチェックしてみます。

x, y がすべての組のどれかに含まれていれば条件を満たすことになります。

(defun candidate-p (x y pairs)
  (loop for (a b) in pairs
        always (or (= a x) (= a y) (= b x) (= b y))))Code language: Lisp (lisp)

ただし、これは非効率なため、時間内に計算できません。

;;(candidates/naive 10 '((1 2) (1 3) (2 4)))
;;=> ((1 4))
;;(candidates/naive 7 '((2 4) (1 3) (1 7) (1 3) (1 2) (1 6) (1 5) (1 3)))
;;=> ((1 2) (1 4))
(defun candidates/naive (n pairs)
  (loop for x from 1 to (1- n)
        append (loop for y from (1+ x) to n
                     when (candidate-p x y pairs)
                       collect (list x y))))

(defun candidate-p (x y pairs)
  (loop for (a b) in pairs
        always (or (= a x) (= a y) (= b x) (= b y))))

(defun read-pairs (m)
  (loop repeat m
        collect (list (read) (read))))

(defun main ()
  (let* ((n (read))
         (m (read))
         (pairs (read-pairs m)))
    (princ (length (candidates/naive n pairs)))))
(main)
Code language: Lisp (lisp)

3. 場合分けによる解答（AC17 WA3 TLE11）

全部を調べるのは大変なので、１つ目の結果を元に、A1がBig 2である場合、B1がBig 2である場合に場合分けをして、他方の候補を求めることにしました。

(defun candidates/case (n pairs)
  (loop for x in (car pairs)
        append (candidates/when n x (cdr pairs)) into lst
        finally (return (remove-duplicates lst :test #'equal))))

(defun candidates/when (n x rest-pairs)
  (loop for y from 1 to n
        when (candidate-p x y rest-pairs)
        collect (list (min x y) (max x y))))Code language: Lisp (lisp)

1試合目の決勝に出たのは、$A_1$ と $B_1$ の2人だけです。
組 (x, y) が条件を満たすなら、この試合でも x か y のどちらかが決勝に上がっていなければいけません。
x も y も $A_1$ でも $B_1$ でもないとしたら、その時点で条件は破れます。

つまり、答えになる組は必ず $A_1$ か $B_1$ を含みます。
候補は $(A_1, y)$ か $(B_1, y)$ の形だけ。
y の取り方は N 通りなので、調べる組は多くても 2N 個です。

素朴なコードが調べていた組は $N(N-1)/2$ 個で、N が $2 \times 10^5$ なら約 $2 \times 10^{10}$ 組。
ここを 2N に落とすのが、この問題の入口でした。

正解は、11から17に増えましたが、WA3 TLE11。
非効率だけでなく、見落としの問題も残っています。

(defun candidate-p (x y pairs)
  (loop for (a b) in pairs
        always (or (= a x) (= a y) (= b x) (= b y))))

(defun read-pairs (m)
  (loop repeat m
        collect (list (read) (read))))

(defun candidates/when (n x rest-pairs)
  (loop for y from 1 to n
        when (candidate-p x y rest-pairs)
        collect (list (min x y) (max x y))))

(defun candidates/case (n pairs)
  (loop for x in (car pairs)
        append (candidates/when n x (cdr pairs)) into lst
        finally (return (remove-duplicates lst :test #'equal))))

(defun main/2 ()
  (let* ((n (read))
         (m (read))
         (pairs (read-pairs m)))
    (princ (length (candidates/case n pairs)))))
(main/2)
Code language: Lisp (lisp)

3.1. x = y の場合は除外しないと（AC20 TLE11）

まず、気づいたのは x = y の場合を除外できていないことです。

(defun candidates/when (n x rest-pairs)
  (loop for y from 1 to n
        when (and (/= x y)
                  (candidate-p x y rest-pairs))
        collect (list (min x y) (max x y))))
Code language: PHP (php)

これで、不正解の3つはクリアできました。

4. 候補になる数字をペア集合から探す（AC25 WA6）

関数candidates/whenの探し方は、1〜nまでの数字を巡回して、ペアから適合する数値 y を判定しています。
O(n×m)になっています。

しかし、候補 y はペアで使われている数字から絞り込めます。
そうすれば、O(m)にできます。

１つ目の候補に x を選んだとき、まずは、すべてのペアリストから x が含まれないペアリストを探します。

(defun exclusive-pairs (x pairs)
  (remove-if (lambda (pair)
               (or (= x (first pair))
                   (= x (second pair)))) pairs))

すると、2つ目の候補 y は、このペアリストのすべてに入っている数になります。
ただし、すべてのペアリストに x が含まれているなら、y は x 以外のすべての数値を取りうることになります。

(defun always-in-pairs (x pairs)
  (loop for (a b) in pairs
        always (or (= x a) (= x b))))

(defun candidates/when-exclusive (n x rest-pairs)
  (let* ((ex-pairs (exclusive-pairs x rest-pairs)))
    (cond ((null ex-pairs)
           (loop for y from 1 to n
                 when (/= x y)
                   collect (list (min x y) (max x y))))
          (t (loop for y in (car ex-pairs)
                   when (always-in-pairs y ex-pairs)
                     collect (list x y))))))Code language: PHP (php)

すると、正答は25に増え、誤答が 6 残りました。

(defun exclusive-pairs (x pairs)
  (remove-if (lambda (pair)
               (or (= x (first pair))
                   (= x (second pair)))) pairs))

(defun always-in-pairs (x pairs)
  (loop for (a b) in pairs
        always (or (= x a) (= x b))))

(defun candidates/when-exclusive (n x rest-pairs)
  (let* ((ex-pairs (exclusive-pairs x rest-pairs)))
    (cond ((null ex-pairs)
           (loop for y from 1 to n
                 when (/= x y)
                   collect (list (min x y) (max x y))))
          (t (loop for y in (car ex-pairs)
                   when (always-in-pairs y ex-pairs)
                     collect (list x y))))))

;; (candidates/case-exclusive 7 '((2 4) (1 3) (1 7) (1 3) (1 2) (1 6) (1 5) (1 3)))
;;=> ((2 1) (4 1))
(defun candidates/case-exclusive (n pairs)
  (loop for x in (car pairs)
        append (candidates/when-exclusive n x (cdr pairs)) into lst
        finally (return (remove-duplicates lst :test #'equal))))

(defun read-pairs (m)
  (loop repeat m
        collect (list (read) (read))))

(defun main/3 ()
  (let* ((n (read))
         (m (read))
         (pairs (read-pairs m)))
    (princ (length (candidates/case-exclusive n pairs)))))
(main/2)
Code language: Lisp (lisp)

4.1. x < y になるように（AC31 136ms）

練習問題の3で誤答になっていたので、確認してみました。

(candidates/case-exclusive 7 '((2 4) (1 3) (1 7) (1 3) (1 2) (1 6) (1 5) (1 3)))
;;=> ((1 2) (1 4) (2 1))Code language: PHP (php)

すると、(1 2)と(2 1)をダブルカウントていることがわかりました。

(defun candidates/when-exclusive (n x rest-pairs)
  (let* ((ex-pairs (exclusive-pairs x rest-pairs)))
    (cond ((null ex-pairs)
           (loop for y from 1 to n
                 when (/= x y)
                   collect (list (min x y) (max x y))))
          (t (loop for y in (car ex-pairs)
                   when (always-in-pairs y ex-pairs)
                     collect (list (min x y) (max x y)))))))Code language: PHP (php)

collect listの部分で、ちゃんと min x y, max x y を取る必要がありました。

これで、全部クリアすることができました。

;;(exclusive-pairs 2 '((2 4) (1 3) (1 7) (1 3) (1 2) (1 6) (1 5) (1 3)))
;;((1 3) (1 7) (1 3) (1 6) (1 5) (1 3))
(defun exclusive-pairs (x pairs)
  (remove-if (lambda (pair)
               (or (= x (first pair))
                   (= x (second pair)))) pairs))

(defun always-in-pairs (x pairs)
  (loop for (a b) in pairs
        always (or (= x a) (= x b))))

(defun candidates/when-exclusive (n x rest-pairs)
  (let* ((ex-pairs (exclusive-pairs x rest-pairs)))
    (cond ((null ex-pairs)
           (loop for y from 1 to n
                 when (/= x y)
                   collect (list (min x y) (max x y))))
          (t (loop for y in (car ex-pairs)
                   when (always-in-pairs y ex-pairs)
                     collect (list (min x y) (max x y)))))))

;; (candidates/case-exclusive 7 '((2 4) (1 3) (1 7) (1 3) (1 2) (1 6) (1 5) (1 3)))
;; ((1 2) (1 4))
(defun candidates/case-exclusive (n pairs)
  (loop for x in (car pairs)
        append (candidates/when-exclusive n x (cdr pairs)) into lst
        finally (return (remove-duplicates lst :test #'equal))))

(defun read-pairs (m)
  (loop repeat m
        collect (list (read) (read))))

(defun main/3 ()
  (let* ((n (read))
         (m (read))
         (pairs (read-pairs m)))
    (princ (length (candidates/case-exclusive n pairs)))))
(main/3)
Code language: Lisp (lisp)

5. 【効率解】ペアの判定を集計値で求める（89ms）

求めたい組 (x, y) は、「どの試合でも x か y の少なくとも一方が出ている」組でした。

x が出た試合の集合 $S_x$ と、y が出た試合の集合 $S_y$ を考えます。
条件は $|S_x \cup S_y| = M$ です。

和集合の大きさは $|S_x| + |S_y| – |S_x \cap S_y|$ で、$S_x \cap S_y$ は x と y が同時に出た試合、つまり x 対 y の試合そのものです。

集計を先に済ませておくと、判定1回が配列参照3回で終わり、候補が 2N 個あっても $O(N)$ です。

;;(count-degrees 7 '((2 4) (1 3) (1 7) (1 3) (1 2) (1 6) (1 5) (1 3)))
;;=> #(0 5 2 3 1 1 1 1)
(defun count-degrees (n pairs)
  (let ((deg (make-array (1+ n) :initial-element 0)))
    (loop for (a b) in pairs
          do (incf (aref deg a))
             (incf (aref deg b))
          finally (return deg))))

;;(count-opponents 7 1 '((2 4) (1 3) (1 7) (1 3) (1 2) (1 6) (1 5) (1 3)))
;;=> #(0 0 1 3 0 1 1 1)
(defun count-opponents (n x pairs)
  (let ((cnt (make-array (1+ n) :initial-element 0)))
    (loop for (a b) in pairs
          do (cond ((= a x) (incf (aref cnt b)))
                   ((= b x) (incf (aref cnt a))))
          finally (return cnt))))

;; 組 (x y) が全試合を覆うか
(defun cover-p (x y m deg vs)
  (= m (- (+ (aref deg x) (aref deg y)) (aref vs y))))

;;(count-covers 7 '((2 4) (1 3) (1 7) (1 3) (1 2) (1 6) (1 5) (1 3)))
;;=> 2
(defun count-covers (n pairs)
  (let* ((m (length pairs))
         (deg (count-degrees n pairs))
         (a1 (first (first pairs)))
         (b1 (second (first pairs)))
         (ac (count-opponents n a1 pairs))
         (bc (count-opponents n b1 pairs)))
    (+ (loop for y from 1 to n
             count (and (/= y a1)
                        (cover-p a1 y m deg ac)))
       (loop for y from 1 to n
             count (and (/= y a1) (/= y b1)
                        (cover-p b1 y m deg bc))))))

(defun read-pairs (m)
  (loop repeat m collect (list (read) (read))))

(defun main/4 ()
  (let* ((n (read))
         (m (read))
         (pairs (read-pairs m)))
    (princ (count-covers n pairs))))
(main/4)Code language: Lisp (lisp)

5.1. 各版の計算量

素朴版は、$N^2$ 組それぞれについて M 試合を見るので $O(N^2 M)$。
場合分け版は候補を 2N 個に絞りましたが、1組ごとに M 試合を走査するため $O(NM)$ です。
$N = M = 2 \times 10^5$ なら $4 \times 10^{10}$ で、これでは足りない。

ペア集合から候補を探す版で、y の候補が最大2個に減って $O(M)$ になりました。
集計版は、前処理が $O(N + M)$ で、1組の判定が配列参照3回。

136ms と 89ms の差は、次数の違いではなく定数倍の差です。