Kazun の競プロ記録

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

AtCoder Beginner Contest 294 C問題 Merge Sequences

AtCoder ABC294 ABC 300 pts C問題

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

長さ N の整数列 A と長さ M の整数列 B がある. ここで, A,B はそれぞれ狭義単調増加であり, A,B に含まれる (N+M) 個の整数は全て異なる.

そして, C を A,B を連結させた整数列を昇順に並び替えた列とする.

このとき, A,B の各項は C の何番目に現れるか?

制約

  • 1 \leq N,M \leq 10^5
  • 1 \leq A_1 \lt A_2 \lt \dots \lt A_N \leq 10^9
  • 1 \leq B_1 \lt B_2 \lt \dots \lt B_M \leq 10^9
  • A_i \neq B_j

解法

実際に C を求め, 各項が A の要素か B の要素かを判定したあと, それが該当の数列の第何項かどうかを判定すれば良い.

これには辞書や連想配列を利用することによって, O( (N+M) \log (N+M)) 時間で実行可能である.

また, A,B が狭義単調増加であることから, 次のようにして求めることができる.

  • i,j,k \gets 1
  • i \leq N かつ j \leq M である限り以下を続ける.
    • A_i \lt B_j ならば, A の第 i 項は C の第 k 項である. そして, i,k に 1 を加算する.
    • A_i \gt B_j ならば, B の第 j 項は C の第 k 項である. そして, j,k に 1 を加算する.
  • 確定していない部分を確定させる.

このとき, 計算量は O(N+M) 時間である.

なお, この問題はマージソートのマージパートを題材にしている.