ABC 365 G — AtCoder Office

考察

入退室が少ない二人の質問は、その場で区間を突き合わせればよい。入退室が多い人については、その人と全員の同時在室時間をまとめて前計算する。区間の総数は入退室記録の半分なので、前計算が必要な人の数を抑えられる。

以下では入退室の記録数を T=MT=M と書く。記録に付いた時刻 TiT_i と、記録数 TT は別の量である。各人は最初も最後も室外にいるので、その人の1回目と2回目、3回目と4回目の記録を組にすると、在室した半開区間の列 SpS_p が得られる。各列は時刻順で、同じ人の区間同士は重ならない。人数 NN と記録数 TT に大小関係はなく、一度も入室しない人の列は空になる。

二人の答えは、二つの区間列の共通部分の長さの合計である。現在見ている区間を [l1,r1),[l2,r2)[l_1,r_1),[l_2,r_2) とすると、足す長さは

max⁡(0,min⁡(r1,r2)−max⁡(l1,l2))\max(0,\min(r_1,r_2)-\max(l_1,l_2))

となる。その後、右端の早い区間のポインタを進める。同じ右端なら両方を進めてよい。これで二列の長さの和に比例する時間で答えられるが、区間の多い二人を繰り返し質問されると、1質問あたり O(T)O(T)、全体で O(QT)O(QT) になりうる。逆に、質問されない組も含めて全員の組を前計算すると、N2N^2 個の表が必要になる。

そこで正整数の閾値 CC を設け、∣Sp∣≤C|S_p|\leq C の人を light、それより多い人を heavy と呼ぶ。両者が light なら上の走査は O(C)O(C) で済む。一方、heavy の人数を HH とすると、区間の総数はちょうど T/2T/2 だから

H(C+1)≤∑p=1N∣Sp∣=T2,H≤⌊T2(C+1)⌋H(C+1)\leq \sum_{p=1}^{N}|S_p|=\frac{T}{2}, \qquad H\leq \left\lfloor\frac{T}{2(C+1)}\right\rfloor

である。人数からではなく、各 heavy が少なくとも C+1C+1 個の区間を消費することから上界を得る。

本解説では、各 heavy と NN 人全員の答えを、長さ NN の配列1行として保存する。表を ans[h][p]\mathrm{ans}[h][p] と書き、heavy の人番号から行番号を引く配列も持つ。この方式なら heavy を含む質問は表の1要素を読むだけになる。以下の計算量では、記録に現れない人の分も含む配列の初期化・保存を数える。

heavy の一人と全員の答えを求める

heavy の人 hh を固定する。hh が入退室するたびに、その時点の全在室者を更新すると再び遅くなる。代わりに、相手の在室区間の端点だけで答えを求められないかを考える。

Ch(t)C_h(t) を「時刻 00 から tt までに hh が在室していた時間の合計」と定義する。これは hh が在室中だけ進む専用の時計である。相手 pp が [a,b)[a,b) に在室したなら、その間に時計が進んだ量

Ch(b)−Ch(a)C_h(b)-C_h(a)

が、二人の同時在室時間になる。例えば pp が [1,10)[1,10)、hh が [3,7)[3,7) に在室した場合、Ch(1)=0,Ch(10)=4C_h(1)=0,C_h(10)=4 なので差は4である。pp の入退室時に hh が不在でも、間の出入りが時計へ反映される。

この時計を全記録の時刻順の走査で計算する。各人の在室フラグ、入室時の時計の値を保存する配列、回答表の今回の行を0で初期化し、時計の値と直前時刻も0にする。各記録 (t,p)(t,p) では次の順に処理する。

  1. 直前の記録から今の時刻まで hh が在室していたなら、その時間差を時計へ足す。直前時刻を tt に更新する。
  2. pp の入室なら現在の時計を保存する。退室なら、現在の時計から保存した値を引いて ans[h][p]\mathrm{ans}[h][p] へ足す。
  3. pp の在室フラグを反転する。p=hp=h のときも、時計を進め終えてから反転する。

1記録あたり定数時間で、全記録を走査すると1行が完成する。ただし長さ NN の行と作業用配列の初期化もあるため、heavy 一人の費用は O(N+T)O(N+T) である。完成した行は表に残し、作業用配列は次の heavy に再利用する。

全質問は先に読み、N,T,QN,T,Q を見て閾値を決める。人別の区間列を作って heavy を分類し、全 heavy の行を前計算したら、質問ごとに heavy の側の行を参照する。どちらも light なら二つの区間列を走査する。質問の番号の大小によって heavy 側が決まるわけではなく、両方が heavy ならどちらの行でもよい。

典型の発動条件

sqrt decompositionによるheavy-light分類

要素ごとの出現数が偏り、二者間の質問を多数処理するときに使える。軽い組はその場で処理し、重い要素だけ一括前計算する。重い要素の数は、分類に使った量の総和から評価する。さらに「一人あたり全記録を読む費用」と「全員分の配列を作る費用」の両方を掛ける。

sorted区間列のintersection

互いに重ならず時刻順に並んだ二つの区間列なら、右端の早い側を進めるだけで共通部分の長さを求められる。一方の区間数だけではなく、両列の長さの和が走査回数の上界になる。

問題固有の要素

各人の記録数が偶数で、全員が最初も最後も室外にいるため、全区間数を正確に T/2T/2 と数えられる。また、heavy 専用の累積在室時間を作れば、相手の入退室端点での差だけで交差長を集計できる。この二点が、heavy の人数と一行の計算費用をそれぞれ抑えている。

この方式では記録のない人も表の列を占める。閾値を固定の平方根で決める前に、時間の二項に加えて「何行を何人分保存するか」を数える必要がある。

正当性

Ch(t)C_h(t) は、hh が在室している時間だけ増える。時刻差を加えてからフラグを反転するので、各記録の処理時に持つ時計の値は Ch(t)C_h(t) と一致する。したがって相手の在室区間 [a,b)[a,b) について、入室時に保存した値を退室時の値から引くと、区間内で hh も在室していた時間をちょうど得る。相手の区間は互いに重ならないので、その差の総和が表の答えになる。記録のない相手の値は初期値0のままで正しい。

light 同士の走査では、現在の二区間の交差を足した後、右端の早い区間を捨てる。その区間の右端は、相手の次の区間の左端以下なので、相手の未処理区間との交差は残っていない。従って交差を漏れなく重複なく数え、片方の列が尽きた時点で終了できる。端点が接するだけなら交差長は0である。

以上の二方式はともに二人の在室区間の交差長の総和を返す。閾値による分類は処理方法だけを変えるので、heavy の有無に応じた回答はすべて正しい。

実装上の注意

  • 人別の記録を隣接する組にして半開区間を作る。全体の記録は既に時刻順なので、並べ直す必要はない。空の区間列なら共通時間は0である。
  • heavy ごとの走査では時計・在室フラグ・入室時の時計を初期化する。時計を進める前に hh のフラグを反転すると、入室前や退室後の時間を加えてしまう。
  • 回答表は heavy の行番号と人番号で直接参照できる配列にする。本解説では連想配列への挿入・検索や、同じ質問の答えを追加で保存する処理を使わない。
  • 時間と回答は64 bit整数で持つ。回答表の要素数や保持 bytes の積も、配列を確保する前に十分な整数幅で計算する。

復習の核

  • heavy の人数は、全人数ではなく分類に使った量の総和から導く。今回は一つの区間に入室・退室の2記録が必要である。
  • 「全記録を1回走査」で終わらず、前後の配列初期化と回答表の保持まで数える。記録数と人数に大小関係がない点に注意する。
  • 共通時間は、一人の在室中だけ進む時計の端点差で取り出せる。途中の出入りのたびに全相手を更新しなくてよい。

計算量と制約

時間

全体は、実際の heavy 人数 HH を用いて

O(N+T+Q+H(N+T)+QC)O\bigl(N+T+Q+H(N+T)+QC\bigr)

となる。人別の空の区間列や heavy 判定用配列の準備・全員の分類に O(N)O(N)、記録の変換に O(T)O(T)、質問の入出力に O(Q)O(Q) かかる。heavy 一人につき長さ NN の配列を初期化して TT 記録を走査するので O(N+T)O(N+T)、light 同士の質問は1件 O(C)O(C) である。よって人数の上界を代入すると

O(N+T+Q+T(N+T)C+1+QC)O\left(N+T+Q+\frac{T(N+T)}{C+1}+QC\right)

とも書ける。今回は全員分の表を持つので、NN が TT 以下とは限らない入力に対して、heavy 前計算を O(T2/C)O(T^2/C) とだけ評価することはできない。

空間

O(N+T+Q+HN)O(N+T+Q+HN)

である。NN 人分の区間列の管理領域と作業用配列、TT 件の記録と計 T/2T/2 個の区間、QQ 件の質問、H×NH\times N 要素の回答表を保持する。各行を表の保存先で直接作り、heavy ごとの作業用配列は使い回す。heavy が0人でも O(N+T+Q)O(N+T+Q) の固定費用は残る。

制約との対応

公式制約は 2≤N,T≤2×1052\leq N,T\leq 2\times10^5、1≤Q≤2×1051\leq Q\leq2\times10^5、1≤T1<⋯<TT≤1091\leq T_1<\dotsb<T_T\leq10^9。各人の記録数は偶数で、質問の二人は異なる。制限は5秒・1024 MiBである。

閾値は、時間の二項 T(N+T)/(C+1)T(N+T)/(C+1) と QCQC を釣り合わせると、定数倍を除く目安として

C≈T(N+T)QC\approx\sqrt{\frac{T(N+T)}{Q}}

を得る。1≤C≤T/21\leq C\leq T/2 の整数へ調整する。C=T/2C=T/2 なら全員が light になる。次に実際の HH を数え、64 bit整数の表だけで 8HN8HN bytes 必要なことを確認する。メモリが足りなければ CC を大きくして行数を減らし、増える light 側の走査も評価し直す。

例えば上限の N=T=Q=2×105N=T=Q=2\times10^5 では、上の目安は約632である。近い規模の整数として C=500C=500 を採ると、H≤199H\leq199 なので、表は最大39,800,000要素、318,400,000 bytes(約303.7 MiB)になる。記録・区間・質問・作業用配列も配列で持てば、それらの線形領域を加えて1024 MiB以内に収められる。

heavy 側の全記録走査は最大39,800,000件で、これに行の初期化などが加わる。light の質問は1件につき高々 2C=10002C=1000 回のポインタ前進、全質問で高々約2億回である。時間はこの走査と配列操作の実装定数にも左右されるため、連続配列で処理する。

具体的には C=min⁡(500,T/2)C=\min(500,T/2) とすれば、記録が少ない場合は全員を light にしつつ、全制約でこの人数・容量・走査回数の上界を満たせる。この選択を出発点に、上の時間式と実際の表の容量から閾値を調整してもよい。

例えば N=2×105,T=2N=2\times10^5,T=2 で一人しか記録に現れなくても、空の区間列や分類用配列を用意する費用は消えない。C≥1C\geq1 なら heavy は0人で、全体は O(N+T+Q)O(N+T+Q) になる。一度も記録に現れない人を含む質問も、空の列から0と答えられる。

出典

分類・前提・執筆情報

掲載状態: 収録済み

AtCoder Office の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 平方根・閾値による軽重分類

主題
  • 平方根・閾値による軽重分類: 頻度・次数・更新回数を閾値でheavy/lightに分け、両側の計算量を均衡させる。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 平方根・閾値による軽重分類

    補助タグ: 尺取り法・sliding window

    執筆: abc-explanation-author1.1.1 / revision 3

    学習の位置

    体系上の位置: 平方根・閾値による軽重分類

    • 頻度・次数・更新回数を閾値でheavy/lightに分け、両側の計算量を均衡させる。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題