AtCoder Beginner Contest 260 E,F問題メモ

E - At Least One

問題

  • NN 枚のカードがあり、ii 枚目には一方の面に整数 AiAi、その裏に BiBi が書かれている
  • 以下の条件を全て満たす数列の個数を、その長さ別に求めよ
  • 条件
    • MM までの正整数の列 (1,2,3,...,M)(1,2,3,...,M)連続部分列である
    • 各カードの向きを適切に決めれば、全てのカードの表面の数字が、数列の中に現れる状態にできる
  • 1N2×1051N2×105
  • 2M2×1052M2×105
  • 1Ai<BiM1Ai<BiM

解法

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

連続した整数列の部分列なので、区間のように考えてよく、左右端の数字 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<BiiiAiAi
    • BiRBiRiiBiBi
    • を取ってきて、その中の最小値が LL の最大値
    • これより LL を小さくする分にはいくらでも可能だが、大きくはできない

なので、上例の場合は、i=1,3i=1,3AA(それぞれ 4,34,3)、i=2i=2BB55)を取ってきて、 その中の最小値である 33 が、R=7R=7 の時に LL として設定できる最大値となる。

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

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

RRBiBi を超えたら 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) と表現するとして、
      • キュー先頭の要素が無効(XSiXSi)であり続ける限り、pop
      • 有効なキュー先頭の XX が、求める値
  • 答えを加算するパート
    • RX+1RX+1 が最小の長さ、RR が最大の長さとなる
    • ans[RX+1]ans[RX+1]11ans[R+1]ans[R+1]11 を加算

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

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

Python3

F - Find 4-cycle

問題

  • 2つのグループがそれぞれ S,TS,T 頂点、辺が MM 辺からなる二部グラフが与えられる
  • 長さ4のサイクルを、どれでもいいので1つ見つけよ
  • 存在しなければ 11 を出力せよ
  • 1S3×1051S3×105
  • 1T30001T3000
  • 1M3×1051M3×105

解法

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

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

誤った解法

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(T1)2T(T1)2 個、実際はこれは SS を超えるので、それが上限となる。

路線は他のほぼ全ての路線と交わるので、2つの路線に駅は T1T1 個ずつあり、そこから交点駅の他に共通する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(T1)2T(T1)2 回だめでへとへとになっても、 T(T1)2+1T(T1)2+1 回目は何か変わるかもしれない。
もとい、必ず見つかる。

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

Python3

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