AtCoder Beginner Contest 260 E,F問題メモ

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

programming_algorithm/contest_history/atcoder/2022/0717_abc260.txt · 最終更新: 2022/07/19 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0