要約
- ABC286 ; F - Guess The Number 2 (a.k.a. ADT_20250821 ; I - Guess The Number 2) の説明です
- 中国剰余定理 を使います
- 中国剰余定理は ac-library-python を使います
はじめに
競プロの日頃の精進として, AtCoder Daily Training を電車の中で見ています. そんな中で出会った ADT_20250821 ; I - Guess The Number 2 という問題は, 最初はよく分からなかったのですが, いろいろ考えているうちに解き方が分かり, また制約の絶妙さに感動しました.
そして, この問題を通じて, 中国剰余定理が ac-library-python にあることも知りました.
そこで, 解き方が分かった嬉しさと, 中国剰余定理が ac-library-python にあることを忘れないために, 解き方を私なりに残しておきます.
問題概要
詳細は ABC286 ; F - Guess The Number 2 を見ていただくとして, 概要は以下のようにジャッジプログラムと解答者のプログラムがインタラクティブにやり取りをします.
- 【ジャッジ】正の整数 $N$ ($1 \le N \le 10^9$) を決める
- 【解答者】正の整数 $M$ ($ 1 \le M \le 110$) と, 長さ $M$ の整数列 $A = \left(A_1, A_2, \ldots , A_M\right)$ ($1 \le A_i \le M$) を出力する
- 【ジャッジ】$B_i = f^N\left( i \right)$ ($f\left( i \right) = A_i$) で得られる整数列 $B = \left( B_1, B_2, \ldots, B_M \right)$ を出力する
- 【解答者】ジャッジの決めた $N$ を特定し, $N$ を出力する
ジャッジに渡す配列を作る
考察 1 ; まず単純に考える
$f \left( i \right) = A_i$, $f^2 \left( i \right) = A_{A_i}$ ということを繰り返すと, どんなに頑張っても最大 $M$ 回繰り返すと同じ値に戻ります. 例えば $M = 110$ の場合,
A = \left(2, 3, 4, 5, \ldots, 110, 1\right)
という整数列を設定すると,
\begin{align}
f \left( 1 \right) &= A_1 &= 2\\
f^2 \left( 1 \right) &= f \left( A_1 \right) &= 3 \\
f^3 \left( 1 \right) &= f \left( A_2 \right) &= 4
\end{align}
となり, $N = f^N \left( i \right) - 1$ で $N$ を求めることができます. しかし, この方法で求められるのは $M = 110$ までです.
考察 2 ; 互いに素なを活用する
少ない整数列で大きな $N$ を特定するには, 複数の「互いに素な数」を使い, 上記と同様の方法を使います.
例えば互いに素な数として $2, 3$ を選択したとします. そして整数列 $A$ を
A = \left( 2, 1, 4, 5, 3 \right)
とします. $A_1, A_2$ が $2$ に対応する部分で, $A_3, A_4, A_5$ が $3$ に対応する部分です.
この場合, $f^N\left( i \right)$ は次のようになります.
| $N$ | $f^N \left( 1 \right) $ | $f^N \left( 3 \right) $ |
|---|---|---|
| 1 | 2 | 4 |
| 2 | 1 | 5 |
| 3 | 2 | 3 |
| 4 | 1 | 4 |
| 5 | 2 | 5 |
| 6 | 1 | 3 |
分かりやすいように, $f^N\left( i \right) - i$ で表してみます.
| $N$ | $f^N \left( 1 \right) - 1 $ | $f^N \left( 3 \right) - 3$ |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 0 | 2 |
| 3 | 1 | 0 |
| 4 | 0 | 1 |
| 5 | 1 | 2 |
| 6 | 0 | 0 |
このように, $2+3=5$ 個の要素で, $2 \times 3 = 6$ 個の状態を作ることができます.
また $N$ と $f^N \left( i \right) - i$ の関係を見ると,
- $f^N \left( 1 \right) - 1$ ; $N$ を 2 で割った余り
- $f^N \left( 3 \right) - 3$ ; $N$ を 3 で割った余り
になっていることが分かります ($N=6$ の場合は, $6 \equiv 0 \pmod 6$ と考えてください). このことは互いに素な数が 3 つ以上でも成り立ちますので, この考え方を用いて, $110$ 以内の要素数で $10^9$ の状態を作り出します.
また元の数 $N$ は, 互いに素な数で割った余りから求める必要がありますが, ここで 中国剰余定理 の考え方を用います.
考察 3 ; 題意に合う配列にする
上で考察したように, 互いに素な数を選べば, その積 (最小公倍数) の状態を区別することができます.
要素数 $110$ 以下という制約を考えて, 以下のように互いに素な数を設定してみます.
P = \left( 2, 3, 5, 7, 11, 13, 17, 19, 23 \right)
この場合,
\begin{align}
\sum_i P_i &= 100 \lt 110\\
\prod_i P_i &= 223092870 \lt 10^9
\end{align}
となり, $10^9$ までの正の整数を一意に決めることができません.
そこで, 「互いに素」を満足しつつ, 少しだけ大きな数にするために, 以下のように $2$ を $4$ に, $3$ を $9$ に変更します.
P = \left( 4, 9, 5, 7, 11, 13, 17, 19, 23 \right)
この場合,
\begin{align}
\sum_i P_i &= 108 \lt 110\\
\prod_i P_i &= 1338557220 \gt 10^9
\end{align}
となり, $10^9$ までの数を一意に定めることができます (制約の設定が絶妙ですね).
ここまでのプログラム
参考までに, ここまでのプログラムを載せます. 上記で $P$ とした配列は, プログラム中では M にしています.
# 2 -> 4，3 -> 9 にする
M = [4, 5, 7, 9, 11, 13, 17, 19, 23]
A = [] # 相手に渡す数列を作る
acc = 0
for i in range(len(M)): # M[i] 毎に, 1 つずらした列を作る (M[0] = 4 -> 2, 3, 4, 1)
for j in range(M[i]):
A.append(acc + (j + 1) % M[i] + 1)
acc += M[i]
# 相手に渡す
print(sum(M))
print(*A)
ジャッジから受け取った配列を処理する
各要素の変化量を得る
上で見たように, それぞれの塊の 先頭 の要素を見て, 初期値との差分を計算すれば良いです. 実装例は以下のようにリスト r に差分を入れていきます.
# 相手から受け取る
B = list(map(int, input().split()))
r = [] # 余りを入れる
acc = 0
for i in range(len(M)): # それぞれの塊が, どれだけずれたか計算する
r.append(B[acc] - (acc+1))
acc += M[i]
中国剰余定理で解を求める
余りから元の数値を求める (連立合同式を解く) には, ここでは ac-library-python を使います. インストール方法は下記を参照してください.
使い方は簡単で, ライブラリをインポートした後, 「余り」と「割った数」のリストを渡せば, 解 (と, 割った数の最小公倍数) を返してくれます.
from atcoder.math import crt
ans, _ = crt(r, M)
print(ans)
最終解
以上をまとめると, 以下のようになります (私の解答例)
from atcoder.math import crt
# 2 -> 4，3 -> 9 にする
M = [4, 5, 7, 9, 11, 13, 17, 19, 23]
A = [] # 相手に渡す数列を作る
acc = 0
for i in range(len(M)): # M[i] 毎に, 1 つずらした列を作る (M[0] = 4 -> 2, 3, 4, 1)
for j in range(M[i]):
A.append(acc + (j + 1) % M[i] + 1)
acc += M[i]
# 相手に渡す
print(sum(M))
print(*A)
# 相手から受け取る
B = list(map(int, input().split()))
if B != -1:
r = [] # 余りを入れる
acc = 0
for i in range(len(M)): # それぞれの塊が, どれだけずれたか計算する
r.append(B[acc] - (acc+1))
acc += M[i]
ans, _ = crt(r, M)
print(ans)
おわりに
必要最小限の文章でスッキリと分かりやすく書くのが難しく, 回りくどい表現の部分もあるかもしれませんが, 何かの参考になれば幸いです.
今後も競プロの精進を続け, 残すべき知識を得たと思ったら何か書きたいと思います.
参考文献
- ac-library-python
- 中国剰余定理
- 解答例
- 私の提出した解
- 中国剰余定理を自前で実装した例 $\leftarrow$ 見た目が悪いプログラムですが
- I - Guess The Number 2 解説