Spirits Garden (VRChat)

マジで計算手法を教えてほしい
Spirits Garden by ubu461
vrchat.com/hom...

[@ねーぴあ]

面白そうと思って取り組んでみたら、想像以上に長くなってしまいました…
参考
bataparaドットcomスラッシュarchivesスラッシュmarkov-matrixドットhtml
先にこちらを読むとわかりやすいかもしれません。
＊わかりやすさのため、マップにおける番号とは別の番号振りをしています。
開始/中継地点において、
左下、右下、左上、右上、中央下、中央上を順に地点1から地点6
終着地点において、
左下、中央下、右下、中央上を順に地点7から地点9、地点0
とします。
地点iにおけるステップtでの存在確率をx_i(t)（以降変数tは必要がなければ省略）とし、
ステップtでの各地点の確率をx=(x1,x2,…,x0)で表します。（表記上横向きですが、これは列ベクトルです。）
地点iから地点jへ向かう確率をa_jiとすると、
A(x(t+1))=(x(t))
を満たす遷移行列A=(a_ij)が定義できます。
例えば、全ての道が開通している場合、
Aㅤ=ㅤ{
ㅤ{ㅤㅤ0,ㅤㅤ0,ㅤㅤ0,ㅤㅤ0,ㅤa15,ㅤa16,ㅤㅤ0,ㅤㅤ0,ㅤㅤ0,ㅤㅤ0},
ㅤ{ㅤㅤ0,ㅤㅤ0,ㅤㅤ0,ㅤㅤ0,ㅤa25,ㅤa26,ㅤㅤ0,ㅤㅤ0,ㅤㅤ0,ㅤㅤ0},
ㅤ{ㅤㅤ0,ㅤㅤ0,ㅤㅤ0,ㅤㅤ0,ㅤa35,ㅤa36,ㅤㅤ0,ㅤㅤ0,ㅤㅤ0,ㅤㅤ0},
ㅤ{ㅤㅤ0,ㅤㅤ0,ㅤㅤ0,ㅤㅤ0,ㅤa45,ㅤa46,ㅤㅤ0,ㅤㅤ0,ㅤㅤ0,ㅤㅤ0},
ㅤ{ㅤa51,ㅤa52,ㅤa53,ㅤa54,ㅤㅤ0,ㅤㅤ0,ㅤㅤ0,ㅤㅤ0,ㅤㅤ0,ㅤㅤ0},
ㅤ{ㅤa61,ㅤa62,ㅤa63,ㅤa64,ㅤㅤ0,ㅤㅤ0,ㅤㅤ0,ㅤㅤ0,ㅤㅤ0,ㅤㅤ0},
ㅤ{ㅤa71,ㅤa72,ㅤㅤ0,ㅤㅤ0,ㅤㅤ0,ㅤㅤ0,ㅤㅤ1,ㅤㅤ0,ㅤㅤ0,ㅤㅤ0},
ㅤ{ㅤㅤ0,ㅤa82,ㅤa83,ㅤㅤ0,ㅤㅤ0,ㅤㅤ0,ㅤㅤ0,ㅤㅤ1,ㅤㅤ0,ㅤㅤ0},
ㅤ{ㅤa93,ㅤㅤ0,ㅤㅤ0,ㅤa94,ㅤㅤ0,ㅤㅤ0,ㅤㅤ0,ㅤㅤ0,ㅤㅤ1,ㅤㅤ0},
ㅤ{ㅤㅤ0,ㅤa02,ㅤㅤ0,ㅤa04,ㅤㅤ0,ㅤㅤ0,ㅤㅤ0,ㅤㅤ0,ㅤㅤ0,ㅤㅤ1}
}
となります。
（道がない場所は確率0、終着地点は確率1で自身へ移動、と捉えています。）
よって、対角化等でA^nを求めたのちに、lim[t->∞]x(t)=lim[t->∞](A^t)x(0)の極限を取って、lim[t->∞]x(t)を求めれば、各終着地点での確率がわかります。
もっといい方法はありそうですが、思いつきませんでした…
別案（いろいろ試行錯誤した結果）
ステージ5における解法
地点5で生成された物質が終着地点8に行く確率を求めると、
4/10*4/11 + 4/10+1/4 = 35/44
これは最初の2秒で過半数が到達することを表すため、この時点で地点8が最大であることが確定する。

[@kuchiwo]

ありがとう　確かに最大のものが求まっていればいいから別案で頑張るのが現実的なのかな
数秒後に開始地点に戻ってくるやつの存在をどう処理すべきかがわからず諦めちゃったけど、割り切って数ループ分を計算しちゃうのが結局早いのかも(複数人でJoinしてるならなおさら)
ちなみに全クリしてもまだ秘密があるという噂なので興味があったら実際にこのワールドに行ってみてください