目次

AtCoder Beginner Contest 260 E,F問題メモ

AtCoder Beginner Contest 260

E - At Least One

E - At Least One

問題

解法

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

連続した整数列の部分列なので、区間のように考えてよく、左右端の数字 $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

なので、上例の場合は、$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$ も用意しておく。

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

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

Python3

F - Find 4-cycle

F - Find 4-cycle

問題

解法

全てを列挙するのは難しいが、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が取れなかった。

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

このようなケースでイメージしやすいのが、平面上に「互いに平行でない $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