リム=ドゥールの櫃で5枚積み込む時のオーダー
結論が見たい人は→のリンクから飛んでください.
動機
wikiに
5枚をキープするまではライブラリーの一番下に望む順番で置けるのもポイント。山札が5の倍数でなければ、大量のライフを支払う事で２周目以降に突入して望む５枚の組み合わせにすることも可能。
と書いてあったので山札の枚数を $n$ とした時,どのくらいのオーダーで5枚を積み込むことが出来るかを調べる.
ついでに手順の省略が可能かどうかも検証する.
リム=ドゥールの櫃のテキスト
あなたのライブラリーの一番上から５枚のカードを見る。あなたが選んだ回数だけ、あなたは１点のライフを支払い、それらのカードをあなたのライブラリーの一番下に望む順番で置き、その後あなたのライブラリーの一番上から５枚のカードを見てもよい。その後、あなたのライブラリーを切り直し、これによりあなたが見た最後のカードをその一番上に望む順番で置く。
put those cards on the bottom of your library in any order, then look at the top five cards of your library. Then shuffle your library and put the last cards you looked at this way on top of it in any order.
計算機科学用語に置き換えると
$n$ 枚のカードが有り,「上から5枚を任意の順番で下に送る」を任意回繰り返し, 上から5枚を任意の5枚にする.
この時,繰り返す回数の上界を求めよ.
となる.
$n$ が5の倍数の時は容易にわかるように不可能である.
よって以下, $n$ が5の倍数以外の時を考察する.
考察
カードは $n = 5m + l \ (l=1,2,3,4)$ 枚あり, 最初は無作為な状態にあるとする.
また,今後「上からn枚をそのままの順番で下に送る」を「上ローテートn」,「上から5枚を任意の順番で下に送る」を「リム(る)」と表現する.
補題
- 上ローテート5を $m$ 回行うと下にあった $l$ 枚が上の $l$ 枚となる. また, これは下ローテート $l$ に等しい.
- 上ローテート5を $m + 1$ 回行うと, 上から $5 - l$ 枚目が一番上に来る. また, これは上ローテート $l$ に等しい.
- 上ローテート5を $n$ 回行ってもカードの列は変化しない.
5枚を揃える
初期状態から「任意のカードを上から $x$ 番目に置く」を5回繰り返すことによって, ソートが完了する.
この時, 補題より, 上ローテート5を $n$ 回しても列は変化しないので, この $n$ 回のローテートのうち適当な回数をリムに変更し, カードを $x$ 番目に移動させる.
目的のカードが $k = 5i + j \ (j = 0, 1, 2, 3, 4)$ 番目にあるとする.
この時, $x < k$ としても一般性を失わない.
$j \neq 0$ ならば $i + 1$ 回目の上ローテート5をリムに変更し, カードの位置を $5i + j - 1$ まで移動することが出来る.
残りの $n - (i + 1)$ 回は全て上ローテート5にすれば, 目的のカードから $x$ までの距離が1減ったカード列が出来上がる.
$j = 0$ の時, 補題より上ローテート5を $m$ 回行えば, カードの位置が $5i + l$ 番目まで移動するので, この後, 上ローテート5を $i$ 回行い, リムをしてカードの位置を $5i + l - 1$ まで移動させ,
残りの $n - (m + i + 1)$ 回全て上ローテート5とすれば, 同様に $x$ までの距離が1減ったカード列となる.
この操作を最大 $n - 1$ 回行うので($x$ と $k$ の差は最大 $n - 1$), 「任意のカードを上から $x$ 番目に置く」のは $O(n^2) = 1 \times n^2 > n \times (n - 1)$ である(カードを1動かすのに $n$ 回, カードを目的の位置に動かすので $n - 1$ 回かかる).
なお, $x > k$ の場合は, $j = 4$とこれ以外の場合に分ければ良い.
「任意のカードを上から $x$ 番目に置く」ことを5回やってもオーダーは変わらないので,結局, $O(n^2)
= 5 \times n^2$ である.
行動の省略は可能か
多分可能だと思う.
総合ルールを引用する.
719.2a At any point in the game, the player with priority may suggest a shortcut by describing a sequence of game choices, for all players, that may be legally taken based on the current game state and the predictable results of the sequence of choices. This sequence may be a non-repetitive series of choices, a loop that repeats a specified number of times, multiple loops, or nested loops, and may even cross multiple turns. It can’t include conditional actions, where the outcome of a game event determines the next action a player takes. The ending point of this sequence must be a place where a player has priority, though it need not be the player proposing the shortcut.
めっちゃ長い719.2aの中の
It can’t include conditional actions, where the outcome of a game event determines the next action a player takes.
上記の手段は多分ココに引っかかって, 条件分岐が含まれているので出来ないと思うけど, ライブラリを一周すればどのカードが上から何枚目かは既知の情報になるので, そこからは条件分岐を含まないループが構成可能なので出来るかも?
そもそも「上から5枚を任意の順番で下に送る」はイベントなのか?
つまり何点払えばいいの?
上界が $5n^2$ であることがわかったので, カードの枚数を $n$ とした時, $5n^2$ 点である.
普通の構築なら $18000 = 5 \times 60 \times 60$, EDHなら $50000 = 5 \times 100 \times 100$ 点くらい払っとけばいいと思うよ.
ちなみに
単純にソートの問題として考えた時, $n$ 枚をソートするのにかかるオーダーは $O(n^3)$.
もっと小さくなるかも?