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

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