プロジェクトオイラー426.

この記事の所要時間: 516

No.426 Box-ball system

問題.

(ProjectEuler426. より)

Q. 無限に並んだ箱を考える. いくつかの箱には玉が入っている. 例えば, 2個連続して玉の入った箱, それに続いて2個の空き箱, 2個の玉の入った箱, 1個の空き箱, 2個の玉の入った箱が並んだ初期配置について, これを交互に現れる玉の入った箱と空き箱の数により数列 (2, 2, 2, 1, 2) と表すことができる.

1回の操作において, それぞれの玉を以下の規則に従って1回ずつ移動させる.

(操作):まだ移動していない最も左にある玉を右側の一番近い空き箱に入れる.

1回の操作で下記に示すように, 数列(2, 2, 2, 1, 2) は (2, 2, 1, 2, 3) に変化する; 新しくできた数列は玉の入った箱の数から始めることに注意.

このような系を箱玉系(Box-ball system) または略して BBS と呼ぶ.

十分な回数この操作を繰り返した後, この系は玉の入った箱の連続した個数が変わらない状態へと発展することがわかる. 以下に示した例では, 玉の入った箱の連続した個数は [1, 2, 3] に発展する.

数列 \{t_i\} を以下のように定義する.

  • s_0 = 290797
  • s_{k+1} = s_k^2\bmod 50515093
  • t_k = (s_k\bmod 64)+1

初期配置 (t_0, t_1, \ldots, t_{10}) から開始すると, 最終状態は [1, 3, 10, 24, 51, 75] となる.

初期配置 (t_0, t_1, \ldots, t_{10 000 000}) から開始したときの最終状態を求めよ.

回答は, 最終状態の要素の自乗の和で答えよ. 例えば, 最終状態が [1, 2, 3] のとき, 14(=1^2+2^2+3^2) が答えるべき回答となる.

考え方とプログラム例

まず, 箱玉系についての説明をしておきます.

箱玉系は, 空き箱を0, 玉の入った箱を1で表すことによって, 0, 1 の列として表現できます. 例えば, 上のQ. にある, 操作による時間発展は以下のように表されます.

\begin{align*} 1100110110000000000000\\ 0011001001110000000000\\ 0000110100001110000000\\ 0000001011000001110000\\ 0000000100110000001110 \end{align*}

この0, 1の列に対して, 次のような操作 [10削除(10-elimination)] を考えます.

(操作) 列の中で隣接した10の対を削除する.

例えば, 上の 1100110110000000000000 に対して玉の入った箱を表す1が全て無くなるまで10削除を繰り返すと,

\begin{align*} & \color{blue}{\underline{\textcolor{black}{1}\textcolor{red}{1}}}\textcolor{red}{0}\textcolor{black}{0}\color{blue}{\underline{\textcolor{black}{1}\textcolor{red}{1}}}\textcolor{red}{0}\color{blue}{\underline{\textcolor{black}{1}\textcolor{red}{1}}}\textcolor{red}{0}\textcolor{black}{000000000000}\\ \to&\color{blue}{\underline{\textcolor{red}{1}}}\textcolor{red}{0}\color{blue}{\underline{\textcolor{black}{1}\textcolor{red}{1}}}\textcolor{red}{0}\textcolor{black}{00000000000000000}\\ \to&\color{blue}{\underline{\textcolor{red}{1}}}\textcolor{red}{0}\textcolor{black}{00000000000000000000}\\ \to&0000000000000000000000 \end{align*}

となります.

赤く色をつけた部分の10対を削除すると次の列になります.

玉の入った箱の列に青で下線を引いています.

i 回目の10削除によって玉の入った箱の列の個数が減少するとき, そのような i の集合を考えると, これが最終状態での玉の入った箱の連続した個数に対応することが知られています.

上の例では, 1回目, 2回目, 3回目の削除によってそれぞれ青い下線部分の個数は1つずつ減少しており, 実際, 最終状態での連続した玉の入った箱の個数は1, 2, 3 となっています.

説明が長くなりましたが, この方法を使って答えを求めてみます.

ここでは, 玉の入った箱と空き箱の数で (2, 2, 2, 1, 2) のように表す状態を [2, 2, 2, 1, 2] というリストで扱って, 10削除を実装しました.

pypy を用いて計算時間は28.2sec でした.

答えはこの下の行にあります. 反転してください.

31591886008

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加