B - Si Stebbins System

概要

実際のトランプマジックで用いられている仕込みを題材にした問題です．

愚直なアルゴリズムでは正解できません．
少しだけ，工夫をしましょう．

問題原案：tnodino

略解

数列 $A$ は長さ $13$ の周期を持ちます．これを埋め込めばよいです．
剰余は最後にとるとして，等差数列と見るとより短い記述で正解できます．(本文 $Ⅳ.$ 参照)

解説

$Ⅰ.$ 愚直な実装

問題の内容をそのまま実装することで，数列 $A$ の値を求めることはできます．
数列の表現には「配列」を用いるとよいでしょう．

$Ⅱ.$ コンピュータの限界

一般的な家庭用コンピュータにできる計算の限界は，$2022$ 年現在 $10^8$ 回/秒 程度であると言われています．

愚直なアルゴリズムによってこの問題を解こうとすると，時間計算量は $O(K)$ になります．
入力されうる $K$ の最大値が $10^9$ であることを考えると，そのままでは実行時間制限に間に合わないだろうということが分かります．

$Ⅲ.$ 実験と考察

先述した理由により愚直なアルゴリズムでこの問題に正解することはできません．
しかし，計算にかかる時間を気にしなければ正しい答えを出力します．
試しにこのプログラムを用いて，$A$ の値を少し計算してみましょう．手計算でもよいです．

すると，$A = (\underline{0, 3, 6, 9, 12, 2, 5, 8, 11, 1, 4, 7, 10}, 0, 3, 6, \ldots)$ となります．
数列 $A$ は長さ $13$ の周期を持って，同じ値の列を繰り返すことに気付いたでしょうか．

これをコード内に埋め込むことで，$O(1)$ 時間で答えを求めることができます．

$Ⅳ.$ よりシンプルな解法

数列 $B$ を $B_1 = 0, B_{i+1} = B_i + 3 \hspace{0.3em}\scriptsize (i \geq 1)$ とします．
すると，加減乗算において剰余はどこでとっても結果が変わらないので，$A_i = B_i \bmod 13$ と表されます．
(詳しい証明などは他サイト様へ委ねます．)

数列 $B$ は，初項が $0$, 公差が $3$ の等差数列となるので， $B_i = 3(i - 1)$ と表現できることが分かります．

したがって，$3(i - 1) \bmod 13$ を出力すればよいです．

$Ⅴ.$ 発展

$1)$ 類題

• ABC 160 $\hspace{0.15em}$ B - Golden Coins
• ABC 165 $\hspace{0.15em}$ B - 1%
• ABC 205 $\hspace{0.15em}$ C - POW
• ARC 113 $\hspace{0.15em}$ B - A^B^C

実装例