ABC286 F問題 Guess The Number 2

atcoder.jp

どんな操作が行われるか具体例で考える

ジャッジ側の操作を具体的に考えてみます。

を渡すとします。つまり、 です。
N=1 の場合、 と Aと同じ数字が返ってきます。
N=2 の場合、




より が返ってきます。
N=3 の場合、




より が返ってきます。
N=3 より大きな N については、 と値が 4 のまま変わらないため、返ってきた B からは Nが 1か2か3以上 のいずれかということしかわかりません。

そこで、 を別の数字に変えてみます。
例えば とします。
このとき、
N=1 の場合、
N=2 の場合、




N=3 の場合、




N=4 の場合、




となり、N=1 と N=4 が同じになりました。2～4番目の数字に注目すると、 と周期3で巡回しています。
そのため、返ってきた B からは N を 3で割った余りがわかります。(先頭の数字から一番小さな数字の2を引いた値が余りになっています。)
一般に L 個の数字で周期 N の巡回をするような数字の並びを作ることができて、それによって N を L で割った余りがわかります。

中国剰余定理

余りから元の数が特定できるかどうかは、中国剰余定理からわかります。

与えられた 個の整数 がどの二つも互いに素ならば、任意に与えられる整数 に対し

　　

を満たす整数 x が を法として一意的に存在する。

まず、 は素数であるとします。 周期 とするためには、 個の数字が必要になります。使える数字は最大110 という制限があるため、
までになります。
この場合、中国剰余定理より までの値であれば一意に決まります。ところが Nは最大 なので、これではＮが一意に決まりません。
そこで、さらに工夫が必要になります。
素数に限定しないで、 2の代わりに , 3の代わりに を使ってみましょう。すると長さは で 最大110 の制限を満足し、 までの値が一意に決まります。

計算法

Nを で割った余りが ,
で割った余りが であるとします。( と は互いに素)
と書けます。

ここに、 となる をかけると、

これより、 と書けます。

つまり、N を で割った余りが になります。
これを繰り返していけば、 で割った余りが求められます。

コード例 (Julia)

function solve()

  # ジャッジに渡す配列の準備

  P = [4, 9, 5, 7, 11, 13, 17, 19, 23]
  N = length(P)
  L = sum(P)

  A = Vector(1:L)    # A = [1,2,3,...,L]

  base = 0
  for i = 1:N
    # 周期 P[i] の巡回をするように、数字をずらす
    a = base+1
    b = base+P[i]
    A[a:b] = circshift(A[a:b],-1)
    base += P[i]
  end

  # 配列をジャッジに渡す

  println(L)
  for i = 1:L-1
    print(A[i]," ")
  end
  println(A[L])

  # ジャッジから返される配列を受け取る
  readInts() =  parse.(Int,split(readline()))
  B = readInts()

  # 余り
  r = Vector{Int}(undef,N)
  base = 0
  for i = 1:N
    # 先頭の数字から、巡回する中で一番小さな数字を引く
    a = base+1
    r[i] = B[a] - a
    base += P[i]
  end

  # N を求める
  m = P[1]
  ans = r[1]
  for i = 2:N
    a = invmod(m,P[i])
    ans = a * m * (r[i] - ans) + ans
    m *= P[i]
    ans %= m
  end

  if ans < 0
    ans += m
  end
  println(ans)

  return 0;

end  # function solve


# main
solve()