読者です 読者をやめる 読者になる 読者になる

本履歴

購入した古本の履歴と時々プログラミング

「の」の字形の無限に循環する配列のk番目

K-th Value of Japanese Hiragana Character "の"-like Infinitely Circulating Array

コンピュータは有限しか扱えないので前の状態から次の状態が決まる系は最終的に必ず循環します。そんな循環する状態列のk番目をここでは求めたいと思います。例えば、みんな大好きフィボナッチ数列1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...で純粋数学的にはこのまま増大していくのですが、有限しか扱えないコンピュータでは10^9+7で割った余りとかにして32bitに収まるよう妥協します。ここでは試しに11で割った余りにして最初の項から見てみると1, 1, 2, 3, 5, 8, 2, 10, 1, 0, 1, 1, 2, 3, 5, 8, 2, ...となり、すぐに循環してしまいました。フィボナッチ数列は定義から前の2項の和で次の項が決まるので、実際は数列内に1, 1パターンが2回目に出てきた所で計算(2項を足して11で割る)を打ち切って、それまで計算した結果を使ってk番目の値は簡単に分かります(これを後で見ます)。一般的には鳩の巣原理 - Wikipedia から、11*11+1番目まで計算すれば必ず既に循環していると言えます。ただし、10^9+7で割る例の場合は、最悪(10^9+7)^2+1番目まで計算しないと循環しない可能性があるので、有名な行列のpowmodを使うべきです。前述のフィボナッチ数列の例では一番最初に戻ってしまいましたが(円環)、一般的には途中の状態に戻ることが多く、その場合、自分は配列が「の」の形に似ているなあと常々感じています(一番最後に戻る=同じ状態が永遠と続く場合は「の」の円が潰れて「つ」になってしまいますが(笑))。英語でなんと表現するんでしょう? 似たような形のアルファベットはbやd, e,, p, qって結構ありますね。実際のプログラムは簡単で、どこに戻るのかで場合分けをすればOKです。ret_ptが「の」の字の合流点で、円周長がsize - ret_ptです。

#!ruby
#”の”の字型無限循環配列のk番目を求める

#ary: 循環配列
#ret_pt: 配列最後まで行った時にどこに戻るか
#k: 求める番目、当然配列のサイズより大きいことが予想される
#0-indexed
#O(1)

def no_at(ary, ret_pt, k)
    size = ary.size
    return ary[k] if k < size
    return ary[k % size] if ret_pt == 0
    return ary.last if ret_pt == size - 1
    k -= ret_pt
    r = k % (size - ret_pt)
    ary[ret_pt + r]
end

フィボナッチ数列の例で使うときはno_at([1, 1, 2, 3, 5, 8, 2, 10, 1, 0], 0, 1000)でもいいですしno_at([1, 1, 2, 3, 5, 8, 2, 10, 1, 0, 1], 1, 1000)でもOK。ではどうやって循環していることを調べるかについてですが、これはRubyだと現在の状態をハッシュに入れておけば二度目に出てきた時判別できます。オススメなのがハッシュの値を配列のindexにする方法。Ruby likeなpseudo codeだと

S = 系の初期状態
H = Hash.new
A = Array.new
Until H[S]
  A << S
  H[S] = A.size-1 #配列A内の状態Sの位置
  S = NextState(S)
End

Print no_at(A, H[S], k)

で計算量はO(|A|)すなわち状態の総数になります。したがってこれを使うときは状態の場合の数がどのくらいになるか事前に見積もることが必要です。 実際、mod 11フィボナッチ数列の最初の15項目を上記に当てはめて求めてみると、

#!ruby
M = 11
s = [1, 1]
h = Hash.new
a = Array.new
until h[s]
    a << s
    h[s] = a.size - 1
    s = [s.last, (s.first + s.last) % M]
end

15.times{|k|
    p no_at(a, h[s], k)
}

# [1, 1]
# [1, 2]
# [2, 3]
# [3, 5]
# [5, 8]
# [8, 2]
# [2, 10]
# [10, 1]
# [1, 0]
# [0, 1]
# [1, 1]
# [1, 2]
# [2, 3]
# [3, 5]
# [5, 8]

となりうまく行ってます。ちなみに、今回は純粋に状態を返していますのでフィボナッチ数列の実際の項を求めるには、リターン値の加工が必要です。このようなのの字ループですが、応用例は他にも 線形合同法 - Wikipediaなど枚挙にいとまがないくらいです。 以下、この考え方が使えるオンラインジャッジ問題の二例です。

Infinity Maze

例えば、Infinity Maze | Aizu Online Judgeでは、ロボットが与えられた迷路上で直進し壁にぶつかったら右に向きを変えてまた直進ということを繰り返していく時のL歩進んだロボットの最終位置と向きが問われますが、ロボットの迷路上の位置と向きが与えられればそれ以降の動きが完璧に決まるので、そのうちロボットは循環することが分かります。つまり「の」の字メソッドが使えます。状態数は迷路のサイズ(100*100)とロボットの向き(4通り)の組み合わせで高々40,000となり、Rubyでも十分間に合います。

Google Code Jam Qualification Round 2010 C. Theme Park

Dashboard - Qualification Round 2010 - Google Code Jam

こちらの問題も同じ考えが適用できます。問題の趣旨は、ジェットコースターに複数グループ(Max 1,000)がキューになって並んで居て、乗り終わったグループは再び整列することを繰り返す時に一日に何人がジェットコースターに乗るかを答えます。ジェットコースターは一日108回走りキャパシティは109で、各グループはグループメンバー全員が乗れない場合は次のを待ちます。これもキューの最初のグループが決まればその後の状態は決まるということと状態数が1000であることから、高々1000+1回シミュレーションすれば「の」の字無限ループに入るはずです。実際、問題のサンプルにもあるグループ[1, 4, 2, 1]キャパ6、4回運転の例を取ってみると、

[1, 4, 2, 1] =>5人
[2, 1, 1, 4] =>4人
[4, 2, 1, 1] =>6人
[1, 1, 4, 2] =>6人
[2, 1, 1, 4]

となり無事循環しました(ちなみに総搭乗者数は21)。この問題が少し難しいのは108回目の状態(どのグループが一番最初に並んでいるか)ではなく、各状態に付随する数値の総和を求めることです。これもno_atメソッドを少し変形するだけで求められます。スタートからのの字の合流点までとクルクル回転するところと最後のところの3パターンです。実際はスタートから合流点と最後のところは一緒にできるので2パターンの場合分けですみます。メソッドno_sumは各配列に対し1回しか呼ばれないのでinjectしていますが、何回も呼ばれる場合は総和計算をDPにすべきです。

#!ruby
#”の”の字型無限循環配列のk番目までの総和を求める
def no_sum(ary, ret_pt, k)
    size = ary.size
    return ary[0..k].inject(:+) if k < size
    return (k / size) * ary.inject(:+) + ary[0..k % size].inject(:+) if ret_pt == 0
    return ary.inject(:+) + (k - size + 1) * ary.last if ret_pt == size - 1
    k -= ret_pt
    q, r = k.divmod(size - ret_pt)
    ary[0..ret_pt + r].inject(:+) + q * ary[ret_pt..size - 1].inject(:+)
end

これを用いてTheme Parkを解いてみると、下記のようになりました。ラージも十分通ります。注意点は合計用の配列bを用意しているのと、状態がどのグループが先頭にいるかで決まるためindex付きの配列groupを用意しているのと、全部のグループが乗車したらそれ以上乗車を打ち切るようにrotate_numがnを超えないように監視しているのと、0-indexedにするためr-1にしている所になります。本質的にはpseudo codeそのままなのがお分かりいただけるはずです。

#!ruby
def solve(r,k,n,g)
    group = g.each_with_index.to_a
    s = 0
    h = Hash.new
    a = Array.new #for state
    b = Array.new #for summation
    until h[s]
        a << s
        h[s] = a.size - 1
        passenger = 0
        rotate_num = 0
        while passenger + group.first.first <= k && rotate_num < n
            passenger += group.first.first
            group.rotate!(1)
            rotate_num += 1
        end
        b << passenger
        s = group.first.last
    end

    no_sum(b, h[s], r - 1)
end

以上をまとめると、前の状態から次の状態が決まる系では「の」の字型循環になり、そのk番目の状態(やk番目までの和)はループする箇所をdivやmodすることにより状態総数の計算量で求められます。 個人的には、循環は仏教の輪廻的な考え方なので好きです。この宇宙も有限個の原子で出来ているならばそのうち「の」の字循環することが分かります。えっ?もう何回も循環してる!?

補足

知り合いから「の」でなく「6」では?と言われた。確かに書き順からしてそうだ(笑)