AtCoder Beginner Contest 294 C問題 Merge Sequences
問題
提出解答
問題の概要
長さ の整数列
と長さ
の整数列
がある. ここで,
はそれぞれ狭義単調増加であり,
に含まれる
個の整数は全て異なる.
そして, を
を連結させた整数列を昇順に並び替えた列とする.
このとき, の各項は
の何番目に現れるか?
制約
解法
実際に を求め, 各項が
の要素か
の要素かを判定したあと, それが該当の数列の第何項かどうかを判定すれば良い.
これには辞書や連想配列を利用することによって, 時間で実行可能である.
また, が狭義単調増加であることから, 次のようにして求めることができる.
かつ
である限り以下を続ける.
ならば,
の第
項は
の第
項である. そして,
に
を加算する.
ならば,
の第
項は
の第
項である. そして,
に
を加算する.
- 確定していない部分を確定させる.
このとき, 計算量は 時間である.
なお, この問題はマージソートのマージパートを題材にしている.