AtCoder Beginner Contest 260 E,F問題メモ

AtCoder Beginner Contest 260

E - At Least One

問題

$N$ 枚のカードがあり、$i$ 枚目には一方の面に整数 $A_i$、その裏に $B_i$ が書かれている
以下の条件を全て満たす数列の個数を、その長さ別に求めよ
条件
- $M$ までの正整数の列 $(1,2,3,...,M)$ の連続部分列である
- 各カードの向きを適切に決めれば、全てのカードの表面の数字が、数列の中に現れる状態にできる
$1 \le N \le 2 \times 10^5$
$2 \le M \le 2 \times 10^5$
$1 \le A_i \lt B_i \le M$

解法

尺取法などでも解けるが、以下、優先度付きキューを使った解法。

連続した整数列の部分列なので、区間のように考えてよく、左右端の数字 $L,R$ を決めれば数列は一意に決まる。
そこで、$R$ を固定して $R$ ごとに考える。

その時の $L$ の取り得る値は？というと、

                       R
i\   1  2  3  4  5  6  7  8  9 10 11 12 ...
1             A              B
2       A        B
3          A                          B

$R \lt A_i$ なる $i$ が1つでもあったら条件を満たすような数列はない
そうでない場合
- $R \lt B_i$ な $i$ は $A_i$
- $B_i \le R$ な $i$ は $B_i$
- を取ってきて、その中の最小値が $L$ の最大値
- これより $L$ を小さくする分にはいくらでも可能だが、大きくはできない

なので、上例の場合は、$i=1,3$ は $A$（それぞれ $4,3$）、$i=2$ は $B$（$5$）を取ってきて、その中の最小値である $3$ が、$R=7$ の時に $L$ として設定できる最大値となる。

今回は、数列の長さ毎に個数を数える必要があるので、 imos法などを使って、最小の長さ $5$～最大の長さ $7$ に一律 $1$ を加算してやればよい。

では、$R=1,2,...,M$ と走査していく中で、その時々の $A_i$ または $B_i$ の最小値を求めるにはどうしたらよいか。
優先度付きキューを使えばよい。

$R$ が $B_i$ を超えたら $A_i$ は無効になるので、「各 $i$ につき、今、何の値が有効か」を管理する配列 $S$ も用意しておく。

優先度付きキューを更新するパート
- $A_i=R$ となる $i$ があったら、$(A_i, i)$ をキューに追加、$S_i=A_i$ に更新
- $B_i=R$ となる $i$ があったら、$(B_i, i)$ をキューに追加、$S_i=B_i$ に更新
最小値を求めるパート
- $R \lt max(A_1,...,A_N)$ ならスキップ
- キューの要素のタプルを $(X,i)$ と表現するとして、
  - キュー先頭の要素が無効（$X \neq S_i$）であり続ける限り、pop
  - 有効なキュー先頭の $X$ が、求める値
答えを加算するパート
- $R-X+1$ が最小の長さ、$R$ が最大の長さとなる
- $ans[R-X+1]$ に $1$、$ans[R+1]$ に $-1$ を加算

一番最後に $ans$ の累積和を取ったら、それが答え。

$2N$ 個の要素が1回ずつ優先度付きキューに出したり入れたりされるので、優先度付きキューを使う部分の計算量は $O(N \log N)$。
imos法の部分は $O(M)$ で、まとめて $O(M + N \log N)$ となる。

Python3

from collections import defaultdict
from heapq import heappush, heappop
from itertools import accumulate

n, m = map(int, input().split())
events = defaultdict(list)
max_a = 0
for i in range(n):
    a, b = map(int, input().split())
    events[a].append((0, i))
    events[b].append((1, i))
    max_a = max(max_a, a)

hq = []
available = [0] * n
ans = [0] * (m + 2)

for r in range(1, m + 1):
    if r in events:
        for t, i in events[r]:
            if t == 0:
                heappush(hq, (r, i))
            else:
                heappush(hq, (r, i))
            available[i] = r

    if r < max_a:
        continue

    while hq[0][0] != available[hq[0][1]]:
        heappop(hq)

    l = hq[0][0]
    min_len = r - l + 1
    max_len = r
    ans[min_len] += 1
    ans[max_len + 1] -= 1

print(*accumulate(ans[1:m + 1]))

F - Find 4-cycle

問題

2つのグループがそれぞれ $S,T$ 頂点、辺が $M$ 辺からなる二部グラフが与えられる
長さ4のサイクルを、どれでもいいので1つ見つけよ
存在しなければ $-1$ を出力せよ
$1 \le S \le 3 \times 10^5$
$1 \le T \le 3000$
$1 \le M \le 3 \times 10^5$

解法

全てを列挙するのは難しいが、1つ見つけるだけなら高速な方法があるということ。
そして $T$ のサイズが小さいことを利用するのだろう、ということが読み取れる。

グループをそれぞれ $A,B$ とおくと、ある $A$ 側の2頂点 $u,v$ から繋がる $B$ 側の頂点に、同じペア $(w,x)$ があれば、$u-w-v-x-u$ というサイクルができるので、これを見つければよい。

誤った解法

$A$ 側の1頂点 $u$ を固定し、そこから繋がった $B$ 側の頂点につき、全ペアを回す。
あるペアにつき、そこから繋がる $A$ 側頂点の中に、$u$ 以外の共通項があればよい。

一見、$O(ST^2)$ となりそうだが、実際は1つ見つかったら打ち切ってよい。

$u$ から繋がった $B$ 側頂点のペアに1つも $u$ 以外の共通項がない、ということが様々な $u$ に対して成り立つケースは結構作るのが難しく、間に合うんじゃないかなあ（希望）

と思ったが、1ケースTLEが取れなかった。

後から考えると、以下のようなケースで計算量がやばくなることがわかる。

$A$ 側の頂点を駅、$B$ 側の頂点を電車の路線、辺を「その駅にその路線が通っている」と考える
長さ4のサイクルとは、ある2駅が、2本の異なる路線で繋がっている、という状態である
つまり「全ての路線は、他の各路線とたかだか1つの駅でしか交わらない」ようなケースは、長さ4のサイクルが見つからないまま全ての状態を調べてしまう

このようなケースでイメージしやすいのが、平面上に「互いに平行でない $T$ 本の直線があり、交点に駅がある」場合である。
交点は $\dfrac{T(T-1)}{2}$ 個、実際はこれは $S$ を超えるので、それが上限となる。

路線は他のほぼ全ての路線と交わるので、2つの路線に駅は $T-1$ 個ずつあり、そこから交点駅の他に共通する1駅があるかを調べるのは工夫しても $O(T)$ かかる。

これが $S$ 個の全ての駅で行われた場合、全体で $O(ST)$ となってしまう。

（まぁ、時間ギリギリまで調べて見つからなかったら-1を出力したら通ったけど、本質じゃないね）

正解法

鳩の巣原理を用いる。

$A$ 側の頂点を $u$ とし、$u$ から繋がった全ての “$B$ 側頂点のペア $(w,x)$” に対して「$(w,x)$ の両方に繋がってるのは $u$ でっせ」という情報を記録していく。

その時、既に $(w,x)$ の両方に繋がった他の頂点 $v$ が記録されていれば、$u,v,w,x$ が答えとなる。

新規で記録されるのはたかだか $B$ 側頂点のペア数なので、
$\dfrac{T(T-1)}{2}$ 回だめでへとへとになっても、 $\dfrac{T(T-1)}{2}+1$ 回目は何か変わるかもしれない。
もとい、必ず見つかる。

よって、グラフの入力を合わせても $O(S+M+T^2)$ で見つけるか、存在しないことを判定できる。

Python3

def solve(s, t, links):
    checked = [[-1] * t for _ in range(t)]
    for a, adj in enumerate(links):
        adj.sort()
        for i, b in enumerate(adj):
            for c in adj[i + 1:]:
                if checked[b][c] == -1:
                    checked[b][c] = a
                else:
                    return checked[b][c] + 1, a + 1, b + s + 1, c + s + 1
    return -1, -1, -1, -1


s, t, m = map(int, input().split())
links = [[] for _ in range(s)]
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= s + 1
    links[u].append(v)

res = solve(s, t, links)
if res[0] == -1:
    print(-1)
else:
    print(*res)

目次

AtCoder Beginner Contest 260 E,F問題メモ

E - At Least One

問題

解法

F - Find 4-cycle

問題

解法

誤った解法

正解法