pekempelog

ペケンペイのブログ

Educational DP Contest J Sushi

https://atcoder.jp/contests/dp/tasks/dp_j

ときかたは おいといて つぎの モンダイを かんがえてみよう。

1,2,3,...,N の ますが まっすぐに ならんでいる。あなたは はじめに ます 1 にいる。コインをなげて おもてがでたら ひとつすすんで うらがでたら ひとつもどる。もどれないときは そのばに とどまる。

ます N にたどりつくまでに コインをなげる カイスウのキタイチを もとめたい。

かんがえかたは おなじだね。なんで このモンダイを とりあげたかといえば 2SAT の randomized algorithm に つかれているから。アルゴリズムは Motwani, Raghavan の Randomized Algorithms に かいてあるよ。

キタイチを モンテカルロでもとめようとすると こうなる。

from random import randint
from math import sqrt

def f(n):
    x = 1
    res = 0
    while x != n:
        res += 1
        if randint(0, 1) == 0:
            x -= 1
        else:
            x += 1
        if x < 1: x = 1
    return res

for i in range(1, 20):
    print(i, sqrt(sum(f(i) for _ in range(1000)) / 1000))

キタイチの sqrt とると なにかみえるね。

1 0.0
2 1.4237275020171523
3 2.442130217658346
4 3.5267548823245427
5 4.549285658210528
6 5.4901730391673444
7 6.638749882319713
8 7.541087454737546
9 8.505116107379134
10 9.829598160657433
11 10.415037205886497
12 11.61709946587357
13 12.505718691862535
14 13.488550700501518
15 14.65073377001985
16 15.21042405720498
17 16.469365500832144
18 17.428998823799375
19 18.27834784656425

ちなみに こういうかたちの マルコフレンサは birth and death process とも よばれている。



このモンダイは キタイチのセンケイセイではない。たとえば $X_i$ を $i$ バンめの すしをたべおえるまでの ジカンとしたら すべてたべおえるのに かかる ジカンは $X=\max(X_1,X_2,\ldots,X_N)$ であって $X=X_1+\cdots+X_N$ ではない。ほかの おきかたでも うまくいかないと おもう。



https://ja.wikipedia.org/wiki/%E5%AF%BF%E5%8F%B8#%E7%94%A8%E5%AD%97
https://ja.wiktionary.org/wiki/%E5%A0%B4
https://ja.wiktionary.org/wiki/%E5%8D%87