1269 B. Modulo Equality

Problem - 1269B - Codeforces

問題概要

長さNの数列A,Bを与えられる。Aの各要素にXを足し、Mで割った数列をCとする。Cを並べ替えるとBと一致するとき、Aに足すべき最小のXを求めよ。

入力

  1. 1 ≦ n ≦ 2000
  2. 1 ≦ m ≦ 109
  3. 0 ≦ a_i < m
  4. 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で割る操作を別のことに変換することだ。