Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 294 E問題 2xN Grid

AtCoder ABC294 ABC 500 pts E問題

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

長さ $L$ の整数列 $A, B$ がある. $A,B$ はそれぞれ連長圧縮の結果で与えられる. なお, 以下の形式で与えられる.

$A: ( (v_1, k_1), (v_2, k_2), \dots, (v_M, k_M) )$
$B: ( (w_1, l_1), (w_2, l_2), \dots, (w_N, l_N) )$

$A_i=B_i$ となる $1$ 以上 $L$ 以下の整数 $i$ の個数を求めよ.

制約

$1 \leq L \leq 10^{12}$
$1 \leq N,M \leq 10^5$
$( (v_1, k_1), (v_2, k_2), \dots, (v_M, k_M) ), ( (w_1, l_1), (w_2, l_2), \dots, (w_N, l_N) )$ は長さ $L$ の整数列の連量圧縮である.
$1 \leq v_i, w_i \leq 10^9$

解法

整数の対の列 $C$ を $C_i=(A_i, B_i)$ となるように作成する. このとき, $C$ を連長圧縮した列の長さは高々 $(N+M)$ である.

このことを頭に入れておくと, 次の解法を受け入れることができる.

$i,j \gets 1, X \gets 0$
かつである限り以下を実行する.
- $p \gets \min (k_i, l_j)$
- $v_i=w_j$ ならば, $X$ に $p$ を加算する.
- $k_i, l_j$ から $p$ を減算する.
- $k_i=0$ ならば, $i$ に $1$ を加算する.
- $l_j=0$ ならば $j$ に $1$ を加算する.
$X$ を出力する.

計算量は $O(N+M)$ 時間である.