スターリンソートでガチャの結果を操作する。

概要

スターリンソートなるものが流行っていると職場で聞き、どんなものか見ていた。

[1, 2, 1, 1, 4, 3, 9]
→[1, 2, 4, 9]

なるほど、ソートされていないものを粛正するらしい。
上の例だと第3、4項の1と第6項の3が粛清された。
内容は簡潔だが、職場で具体的に何使うのかを考えるという話になった。
結果としては使えないということになった。
だが使い道がないものに、使い道を見出してこそ楽しいものだ。
というわけで、スターリンソートの有用な使い方を模索してみた。

本文

前書き

これを見たときに、まず思いついたのはのガチャだった。
ガチャの結果がだんだんよくなれば嬉しいことこの上ない。
よくない結果など粛清してしまえばいいのだ。
まずは、ソシャゲのガチャで考えてみた。
ソシャゲのガチャにスターリンソートを適用すると、下記の通りになる。

[N, R, N, N, R, SR, R, N, N, UR]
→[N, R, SR, UR]

※ レア度：N < R < SR < UR

なるほど、1、2、6、10回目に引けばいいのか。
しかし、粛清するには引かずに次の結果に行かねばならないが、
そんなことは出来ない。
いや何かしらの方法で出来たとしても、出る順番が変わってしまうかもしれない。
そもそも出る順番が決まっていなければ意味がない。
従って、ソシャゲのガチャではスターリンソートは使えなさそうだ。

課題

ソートとはデータの集合をある規則に従って並べることである。
スターリンソートはデータの集合を与えられたときに、
並び替えるのではなく規則に従わないものを粛正している。
つまり、スターリンソートを使うための条件は

• データの集合が存在すること
• 規則が存在すること
• 粛正する手段が存在すること

である。
これをガチャに当てはめてみると

• データの集合が存在すること
  →ガチャの結果をデータの集合とする。
• 規則が存在すること
  →レア度を規則とする。
• 粛正する手段が存在すること
  →ガチャを引かない。

となる。
しかし、前書きの通りガチャの結果は分からないし、
引かずに次の手に行く手段もない。
ということは課題はこの二つだ。

• ガチャの結果を用意する
• ガチャを引かずに次の結果に行く手段を用意する

実験

課題を受けて

いや無理だろ。
結果が分かるならそもそも当たりまで引く。
某魔眼でもあればその結果を視ないとか出来るが、現実にそんなものはない。
ここで諦めようと思ったが、一つだけガチャの結果が分かる（らしい）ものを思い出した。
MHWにおける装飾品のマカ錬金だ。
私はやったことがないのだが、マカ錬金は3個ずつのセットで出る順番があらかじめ決まっているらしい。
つまり課題の1つ目のガチャの結果を用意するは解決した。
さらに、この順番はクエストに行くことでスキップも出来るらしい。
なんと課題の2つ目も解決した。
MHWのマカ錬金にはスターリンソートが使えそうだ。

実施

実際にマカ錬金でスターリンソートを使ってみる。
まず条件を定義する。

• マカ錬金の結果を用意する
• 3個のセット中でレア度の高いものが多くなる順番にソートする（レア5 < レア6 < レア7 < レア8）
• 粛正対象が現れたらクエストに行く

まずは結果を用意する。
1回目：体力珠、持続珠、雷光珠
2回目：耐痺珠、采配珠、耐毒珠
3回目：防御珠、耐属珠、氷結珠
4回目：爆師珠、滑走珠、飛燕珠
5回目：防風珠、無撃珠、耐眠珠
6回目：KO珠、達人珠、毒瓶珠

次にレア度を振る。
1回目：体力珠（6）、持続珠（6）、雷光珠（6）→合計18
2回目：耐痺珠（5）、采配珠（5）、耐毒珠（5）→合計15
3回目：防御珠（6）、耐属珠（6）、氷結珠（6）→合計18
4回目：爆師珠（6）、滑走珠（6）、飛燕珠（5）→合計17
5回目：防風珠（6）、無撃珠（6）、耐眠珠（5）→合計17
6回目：KO珠（6）、達人珠（6）、毒瓶珠（6）→合計18

最後に粛正する。
1回目：体力珠（6）、持続珠（6） 雷光珠（6）→合計18

考察

実験の結果1回目しか残らなかった。
こうなるとそもそも1回だけやればいいということになる。
今回は簡単にするために規則をレア度の合計値としたが、
実際はレア度が低くても貴重な装飾品がある。
レア度に加えて個人的な重みを付けるなど規則を変えれば、
自分が望む装飾品を手に入れるスターリンソートが出来るだろう。

感想

完全に夜勤中の深夜テンションで考えているので、
穴だらけの理論だと思います。
ツッコミどころ満載の記事でしょう。
ですが、スターリンソートの使い道はないわけではないと言いたいです。
そもそもどこかで使われいるのかもしれませんが、その時は申し訳ございません。
皆さんが少しでも楽にマカ錬金できますように。

参考

スターリンソートについて

• 計算量O(n)の画期的なソートアルゴリズムであるスターリンソートをHaskell で実装してみた #Haskell

マカ錬金や装飾品について