AtCoder Beginner Contest 260 E,F問題メモ
E - At Least One
問題
- NN 枚のカードがあり、ii 枚目には一方の面に整数 AiAi、その裏に BiBi が書かれている
- 以下の条件を全て満たす数列の個数を、その長さ別に求めよ
- 条件
- MM までの正整数の列 (1,2,3,...,M)(1,2,3,...,M) の連続部分列である
- 各カードの向きを適切に決めれば、全てのカードの表面の数字が、数列の中に現れる状態にできる
- 1≤N≤2×1051≤N≤2×105
- 2≤M≤2×1052≤M≤2×105
- 1≤Ai<Bi≤M1≤Ai<Bi≤M
解法
尺取法などでも解けるが、以下、優先度付きキューを使った解法。
連続した整数列の部分列なので、区間のように考えてよく、左右端の数字 L,RL,R を決めれば数列は一意に決まる。
そこで、RR を固定して RR ごとに考える。
その時の LL の取り得る値は?というと、
R i\ 1 2 3 4 5 6 7 8 9 10 11 12 ... 1 A B 2 A B 3 A B
- R<AiR<Ai なる ii が1つでもあったら条件を満たすような数列はない
- そうでない場合
- R<BiR<Bi な ii は AiAi
- Bi≤RBi≤R な ii は BiBi
- を取ってきて、その中の最小値が LL の最大値
- これより LL を小さくする分にはいくらでも可能だが、大きくはできない
なので、上例の場合は、i=1,3i=1,3 は AA(それぞれ 4,34,3)、i=2i=2 は BB(55)を取ってきて、 その中の最小値である 33 が、R=7R=7 の時に LL として設定できる最大値となる。
今回は、数列の長さ毎に個数を数える必要があるので、 imos法などを使って、最小の長さ 55~最大の長さ 77 に一律 11 を加算してやればよい。
では、R=1,2,...,MR=1,2,...,M と走査していく中で、その時々の AiAi または BiBi の最小値を求めるにはどうしたらよいか。
優先度付きキューを使えばよい。
RR が BiBi を超えたら AiAi は無効になるので、 「各 ii につき、今、何の値が有効か」を管理する配列 SS も用意しておく。
- 優先度付きキューを更新するパート
- Ai=RAi=R となる ii があったら、(Ai,i)(Ai,i) をキューに追加、Si=AiSi=Ai に更新
- Bi=RBi=R となる ii があったら、(Bi,i)(Bi,i) をキューに追加、Si=BiSi=Bi に更新
- 最小値を求めるパート
- R<max(A1,...,AN)R<max(A1,...,AN) ならスキップ
- キューの要素のタプルを (X,i)(X,i) と表現するとして、
- キュー先頭の要素が無効(X≠SiX≠Si)であり続ける限り、pop
- 有効なキュー先頭の XX が、求める値
- 答えを加算するパート
- R−X+1R−X+1 が最小の長さ、RR が最大の長さとなる
- ans[R−X+1]ans[R−X+1] に 11、ans[R+1]ans[R+1] に −1−1 を加算
一番最後に ansans の累積和を取ったら、それが答え。
2N2N 個の要素が1回ずつ優先度付きキューに出したり入れたりされるので、
優先度付きキューを使う部分の計算量は O(NlogN)O(NlogN)。
imos法の部分は O(M)O(M) で、まとめて O(M+NlogN)O(M+NlogN) となる。
F - Find 4-cycle
問題
- 2つのグループがそれぞれ S,TS,T 頂点、辺が MM 辺からなる二部グラフが与えられる
- 長さ4のサイクルを、どれでもいいので1つ見つけよ
- 存在しなければ −1−1 を出力せよ
- 1≤S≤3×1051≤S≤3×105
- 1≤T≤30001≤T≤3000
- 1≤M≤3×1051≤M≤3×105
解法
全てを列挙するのは難しいが、1つ見つけるだけなら高速な方法があるということ。
そして TT のサイズが小さいことを利用するのだろう、ということが読み取れる。
グループをそれぞれ A,BA,B とおくと、ある AA 側の2頂点 u,vu,v から繋がる BB 側の頂点に、 同じペア (w,x)(w,x) があれば、u−w−v−x−uu−w−v−x−u というサイクルができるので、これを見つければよい。
誤った解法
AA 側の1頂点 uu を固定し、そこから繋がった BB 側の頂点につき、全ペアを回す。
あるペアにつき、そこから繋がる AA 側頂点の中に、uu 以外の共通項があればよい。
一見、O(ST2)O(ST2) となりそうだが、実際は1つ見つかったら打ち切ってよい。
uu から繋がった BB 側頂点のペアに1つも uu 以外の共通項がない、ということが 様々な uu に対して成り立つケースは結構作るのが難しく、間に合うんじゃないかなあ(希望)
と思ったが、1ケースTLEが取れなかった。
後から考えると、以下のようなケースで計算量がやばくなることがわかる。
- AA 側の頂点を駅、BB 側の頂点を電車の路線、辺を「その駅にその路線が通っている」と考える
- 長さ4のサイクルとは、ある2駅が、2本の異なる路線で繋がっている、という状態である
- つまり「全ての路線は、他の各路線とたかだか1つの駅でしか交わらない」ようなケースは、長さ4のサイクルが見つからないまま全ての状態を調べてしまう
このようなケースでイメージしやすいのが、平面上に「互いに平行でない TT 本の直線があり、交点に駅がある」場合である。
交点は T(T−1)2T(T−1)2 個、実際はこれは SS を超えるので、それが上限となる。
路線は他のほぼ全ての路線と交わるので、2つの路線に駅は T−1T−1 個ずつあり、そこから交点駅の他に共通する1駅があるかを調べるのは工夫しても O(T)O(T) かかる。
これが SS 個の全ての駅で行われた場合、全体で O(ST)O(ST) となってしまう。
(まぁ、時間ギリギリまで調べて見つからなかったら-1を出力したら通ったけど、本質じゃないね)
正解法
鳩の巣原理を用いる。
AA 側の頂点を uu とし、uu から繋がった全ての “BB 側頂点のペア (w,x)(w,x)” に対して 「(w,x)(w,x) の両方に繋がってるのは uu でっせ」という情報を記録していく。
その時、既に (w,x)(w,x) の両方に繋がった他の頂点 vv が記録されていれば、u,v,w,xu,v,w,x が答えとなる。
新規で記録されるのはたかだか BB 側頂点のペア数なので、
T(T−1)2T(T−1)2 回だめでへとへとになっても、 T(T−1)2+1T(T−1)2+1 回目は何か変わるかもしれない。
もとい、必ず見つかる。
よって、グラフの入力を合わせても O(S+M+T2)O(S+M+T2) で見つけるか、存在しないことを判定できる。