問題概要
長さNの数列A,Bを与えられる。Aの各要素にXを足し、Mで割った数列をCとする。Cを並べ替えるとBと一致するとき、Aに足すべき最小のXを求めよ。
入力
- 1 ≦ n ≦ 2000
- 1 ≦ m ≦ 109
- 0 ≦ a_i < m
- 0 ≦ b_i < m
解答
まずソートする。次にAの各要素にMを足した数列をAの後ろにくっつけてやる。これで考察はほとんど終わりである。
たとえば
- n=4
- m=3
- A = [0, 0, 2, 1]
- B = [2, 0, 1, 1]
このとき、先程いったことをすると以下のようになる
A' = [0, 0, 1, 2, 3, 3, 4, 5]
B = [0, 1, 1, 2]
あとはA'から切り出した長さNの部分列とソート済みのBを比較して、各要素の差が等しいならばそれが答え候補となる。今回でいえば、「2, 3, 3, 4」という部分列とBは各要素の差が等しい。あとは部分列からXを逆算すれば良い。
今回のキモはソートできること、Mで割る操作を別のことに変換することだ。
