トヨタ自動車プログラミングコンテスト2024#8（AtCoder Beginner Contest 365）G問題メモ

トヨタ自動車プログラミングコンテスト2024#8（AtCoder Beginner Contest 365）

G - AtCoder Office

• AtCoder 社のオフィスには $N$ 人の高橋くんが所属しています。
• AtCoder 社ではオフィスの入退室の記録が取られており、記録が取られはじめてから $M$ 回の入退室が行われました。
• $i$ 番目 $(1\leq i\leq M)$ の入退室記録は整数の組 $(T _ i,P _ i)$ で表され、時刻 $T _ i$ に $P _ i$ 番目の高橋くんがオフィスの外にいるならオフィスに入ったことを、オフィスの中にいるならオフィスから出たことを表します。
• 記録が取られはじめた時点ではどの高橋くんもオフィスの外におり、現在どの高橋くんもオフィスの外にいることがわかっています。
• 次の形式の $Q$ 個の質問に答えてください。
• $i$ 番目 $(1\leq i\leq Q)$ の質問では整数の組 $(A _ i,B _ i)$ が与えられるので、記録を取っていた間に $A _ i$ 番目の高橋くんと $B _ i$ 番目の高橋くんがどちらもオフィスの中にいた時間の長さを求めてください。

• $2\leq N\leq2\times10 ^ 5$
• $2\leq M\leq2\times10 ^ 5$
• $1\leq T _ 1\lt T _ 2\lt\dotsb\lt T _ M\leq10 ^ 9$
• $1\leq P _ i\leq N\ (1\leq i\leq M)$
• どの $1\leq p\leq N$ についても、$P _ i=p$ となる $i$ は偶数個存在する
• $1\leq Q\leq2\times10 ^ 5$
• $1\leq A _ i\lt B _ i\leq N\ (1\leq i\leq Q)$
• 入力はすべて整数

まず注意点として、同じ $(A_i,B_i)$ クエリは複数回投げられうる。
同じクエリは再計算されないように、事前にまとめるなどする必要がある。

まず率直に思いつく方法として、イベント順に解くことを考えると、

• $\mathrm{Pair}[i]=[j_1,j_2,...]$：人 $i$ とのクエリがある人 $j$ のリスト
• $\mathrm{LastEnter}[i]$：人 $i$ が最後に入った時刻、退室中は $-1$

を用意して、$T_i$ 順に入退室を見ていき、

• 人 $P_i$ の入室時：
  • $\mathrm{LastEnter}[P_i]=T_i$ とする。
• 人 $P_i$ の退室時：
  • $\mathrm{LastEnter}[P_i]=-1$ にする。またその直前まで入っていた値を $t$ とする
  • 各 $\mathrm{Pair}[P_i]$ にある $j$ につき、
    • $j$ が退室中（$\mathrm{LastEnter}[j]=-1$）なら何もしない
    • それ以外なら、$T_i - \max(\mathrm{LastEnter}[j],t)$ を、$(P_i,j)$ ペアの答えに加算する

としていくと、答えとなる。

問題は、「入退室が多く、ペアも多い人」がいると、$O(NM)$ かかってしまう。
（例えば、ほぼ人 $i$ の入退室で $M$ 個の記録が占められ、クエリでも他の $N-1$ 人全てとの答えが求められる場合など）

そういう人は、別処理をする。

入退室の多い1人を $p$ とする。

記録 $i$ から $i+1$ までの時間を、「時区間 $i$」とする。
各時区間の長さ $D_i=T_{i+1}-T_i$ を求めておく。

長さ $M-1$ の数列 $X$ を用意し、時区間 $i$ に人 $p$ が入室しているなら $X_i=D_i$、退室中は $X_i=0$ とする。

   記録 i   0   1    2    3    4    5    6    7
        T   3   9   15   17   20   25   26   30
        D     6   6    2    3    5    1    4

pの入退室  in      out        in       out
        X     6   6    0    0    5    1    0

こうしておけば、

• $p$ とペアとなる各人 $j$ につき、
  • $j$ の各入退室時刻 $(s,t)$（時刻 $T_i$ でなく、記録index $i$ の方で）につき、
    • $X$ 上で $[s,t)$ の区間和を求めて、
  • 全入退室にわたる総和を取れば、$(p,j)$ の答えとなる。

人 $p$ の入退室回数を $R_p$、クエリで $p$ とペアとなる人の数を $P_p$ とする。

イベント順の解法では、$p$ の入退室によって発生する計算量が 「入退室回数 $R_p \times$ ペア数 $P_p$」かかっていたのに比べ、 1人を基準にする解法は最初に $X$ を作る際の「入退室記録数 $M$」の計算量で済む。

相手 $j$ の入退室によって発生する、$p$ の状態確認 （イベント順なら $\mathrm{LastEnter}$ のチェック、1人を基準にする解法なら $X$ の累積和の取得） の計算量は $R_j$ に依存し、こちらはどちらの解法も変わらない。

よって、「$R_p \times P_p$ が $M$ を超える場合」に、 イベント順から $p$ を基準に解く解法に変えるのが良い、はず。

（以下、駄文）

なお、クエリ $(p,j)$ の両方とも $R_{\circ} \times P_{\circ}$ が大きい場合、 基準とする方をどちらか一方に決めなければいけない。
（どちらでもACできるだろうので別に突き詰める必要は無いのだが）どちらを基準とした方がよいか？

「入退室回数 $R_{\circ}$ が多い」方を基準にした方が、$(p,j)$ ペアだけ考えたときの削減効果は大きいが、 基準にされなかった方は、実質的に $P_{\circ}$（※）が1減り、評価値 $R_{\circ} \times P_{\circ}$ が変動する。
（※イベント順の解法を取ったときに、入退室のたびにチェックする相手数）

評価値 $R_{\circ} \times P_{\circ}$ が減ることで、結局イベント順の解法にした方がいい、となるかもしれない。
その場合、評価値の削減効果が大きいのも「入退室回数 $R_{\circ}$ が多い」方である。

この最適化って、どうしたらいいんだろうね。

Python3

from collections import defaultdict
from itertools import accumulate

n, m = map(int, input().split())
events = []
in_out = [[] for _ in range(n)]
section_times = []
for i in range(m):
    t, p = map(int, input().split())
    p -= 1
    if i > 0:
        section_times.append(t - events[-1][0])
    if len(in_out[p]) == 0 or in_out[p][-1][1] != -1:
        in_out[p].append([i, -1])
        events.append((t, p, 0))
    else:
        in_out[p][-1][1] = i
        events.append((t, p, 1))

q = int(input())
queries = defaultdict(list)
for qi in range(q):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    queries[a, b].append(qi)
unique_queries = list(queries.keys())

pair_count = [0] * n
for a, b in unique_queries:
    pair_count[a] += 1
    pair_count[b] += 1

THRESHOLD = 200000  # 入退室回数 × クエリペア数
event_pairs = [[] for _ in range(n)]
hub_pairs = {i: [] for i in range(n) if len(in_out[i]) * pair_count[i] >= THRESHOLD}
for uqi, (a, b) in enumerate(unique_queries):
    if a in hub_pairs:
        hub_pairs[a].append((b, uqi))
    elif b in hub_pairs:
        hub_pairs[b].append((a, uqi))
    else:
        event_pairs[a].append((b, uqi))
        event_pairs[b].append((a, uqi))

unique_ans = [0] * len(unique_queries)
for i, pairs in hub_pairs.items():
    timeline = [0] * m
    for s, t in in_out[i]:
        for ti in range(s, t):
            timeline[ti + 1] = section_times[ti]
    timeline = list(accumulate(timeline))

    for j, uqi in pairs:
        tmp = 0
        for s, t in in_out[j]:
            tmp += timeline[t] - timeline[s]
        unique_ans[uqi] = tmp

last_enter = [-1] * n  # 在席していれば最終入室時刻、してなければ-1
for t, i, io in events:
    if io == 0:
        last_enter[i] = t
        continue
    lei = last_enter[i]
    last_enter[i] = -1
    for j, uqi in event_pairs[i]:
        if last_enter[j] == -1:
            continue
        unique_ans[uqi] += t - max(lei, last_enter[j])

ans = [0] * q
for uqi, ab in enumerate(unique_queries):
    for qi in queries[ab]:
        ans[qi] = unique_ans[uqi]

print('\n'.join(map(str, ans)))