LoginSignup
9
2

More than 3 years have passed since last update.

@hibit(hibit at)

女騎士の感度を35億倍にする効率的な手順を動的計画法で調査する（幅優先探索でよかった）

Last updated at Posted at 2019-12-25

追記：後で見返したら普通に幅優先探索（BFS）でよかったです

　クリスマスですね。おめで対魔忍！　元気にTwitterを覗いていたら以下のようなツイートが目に入りました。

image.png

「感度3000倍」の定義からすると初期値は0ではなく1の方が適切に思えますが……まあ計算の都合もありそうです。何はともあれ、$5!=120$通りの総当たりをすれば簡単に求められます。

import itertools

def kusuri(kando, s):
    if s == 'A':
        return kando/2
    if s == 'B':
        return kando - 900
    if s == 'C':
        return kando + 2000
    if s == 'D':
        return kando * 5
    if s == 'E':
        return kando + 500


def main():
    chars = "ABCDE"
    for c in list(itertools.permutations(chars, 5)):
        kando = 0
        for cc in c:
            kando = kusuri(kando,cc)
        if kando == 3000:
            print(c)
Output
('B', 'C', 'D', 'E', 'A')
('C', 'A', 'B', 'E', 'D')
('C', 'A', 'E', 'B', 'D')
('C', 'B', 'D', 'E', 'A')

　この4通りが答えとなります。計算も一瞬で終わります。

最小感度と最大感度

　最終的な感度の内最小のものと最大のもの、またその時の順番を求めてみます。

def min_max():

    chars = "ABCDE"

    min_kando = 0
    max_kando = 0

    for c in list(itertools.permutations(chars, 5)):
        kando = 0
        for cc in c:
            kando = kusuri(kando,cc)
        if kando < min_kando:
            min_kando = kando
        if max_kando < kando:
            max_kando = kando

    for c in list(itertools.permutations(chars, 5)):
        kando = 0
        for cc in c:
            kando = kusuri(kando,cc)
        if kando == min_kando:
            print("最も感度が低い組み合わせ：",end="")
            print(c)
        if kando == max_kando:
            print("最も感度が高い組み合わせ：",end="")
            print(c)

min_max()
Output
最も感度が低い組み合わせ：('A', 'B', 'D', 'C', 'E') -2000.0
最も感度が低い組み合わせ：('A', 'B', 'D', 'E', 'C') -2000.0
最も感度が高い組み合わせ：('A', 'C', 'E', 'D', 'B') 11600.0
最も感度が高い組み合わせ：('A', 'E', 'C', 'D', 'B') 11600.0

　低い方を狙うにせよ高い方を狙うにせよ、A（半分にする薬）は無駄打ちさせて、すべての加算リソース（または減算リソース）をつぎこんだ後でそれを5倍するというのがセオリーのようです。まあ言葉にするとそれはそうだろうという感じですが。

35億倍

　ところで、世のえろげーでは感度を35億倍にされた例もあるようです。（※某対魔忍とは別のゲームのようです）

image.png

　35億て……そんな大きな数int型に入らないよぉ

　オーク達の薬に上限がない場合、感度を35億にするのに効率的な組み合わせはどれでしょうか。Cの薬を与え続ければ$3,500,000,000/2,000 = 1,750,000$回で35億に達するのはわかりますが、さすがにもう少し効率的な組み合わせがありそうです。

　Dの薬（5倍）が強力すぎるので、最大限Dの薬を使う方がよさそうですが（このようなアルゴリズムを貪欲法と言います）、その途中で35億を5の指数乗で割ったような「レール」に乗せないといけません。小さい数の内にAやBの薬を駆使してレールに乗せた方がいいのか、ある程度増やしてからレールに乗せた方がいいのか。手計算でチェックするのは無理ですし、総当たりするにしても計算量が大きすぎて日が暮れてしまいます。

動的計画法

　このような時には動的計画法を用います。簡単に言うと、それ以前の計算をメモに残しながら表を埋めていくような計算方法です。常に最善手を積み上げていけば、表を最善手で網羅できるという訳です。今回は、比較する数値（手数）は1次元で大丈夫ですが、付随する情報としてどの薬を選んだかという順番も記録していきたいので、2次元の表を用意します。

def ikisugi():

    inf = pow(10,9)
    dp = []
    max_kando = 3000+10

    for i in range(max_kando):
        dp.append([])
        dp[i].append(inf)
        dp[i].append('')

    dp[0][0] = 0

　dpが結果を記録する表になります。1行目に手数、2行目に順番を記録していきます。初期値として$1,000,000,000$を代入していますが、これは要は「目無し」ということです。（目無しの手から導かれた「最善手」候補は$1,000,000,000$以上になるので、最小値の比較によってそれが最善手に採用されることはありえません）

　後はこれを埋めていきます。C,D,Eの薬だけだったら一方通行に表を埋めていけばよいのですが、A,Bの薬は感度を減らすため、表の埋め方として逆方向になります。競プロ初心者のためか、こういう問題はあまり見ないのですが、何か定型名がついているものなのでしょうか？　とりあえずここでは仮に両方向DPと呼ぶことにします。

　左から始まるDP（感度が増える方向）の関数。

def left_dp(dp,max_kando):

    inf = pow(10,9)

    for i in range(500,max_kando):
        C = dp[i-2000][0]+1
        if i < 2000:
            C = inf
        D = dp[int(i/5)][0]+1
        if i%5 > 0:
            D = inf
        E = dp[i-500][0]+1

        if min(C,D,E) >= dp[i][0]:
            continue
        if min(C,D,E) == C:
            dp[i][0] = C
            dp[i][1] = dp[i-2000][1] + 'C'
        if min(C,D,E) == D:
            dp[i][0] = D
            dp[i][1] = dp[int(i/5)][1] + 'D'
        if min(C,D,E) == E:
            dp[i][0] = E
            dp[i][1] = dp[i-500][1] + 'E'

    return dp

　右から始めるDP（感度が減る方向）の関数。

def right_dp(dp,max_kando):

    inf = pow(10,9)

    for i in reversed(range(1,int(max_kando/2))):
        A = dp[i*2][0]+1
        B = dp[i+900][0]+1

        if min(A,B) >= dp[i][0]:
            continue
        if min(A,B) == A:
            dp[i][0] = A
            dp[i][1] = dp[i*2][1] + 'A'
        if min(A,B) == B:
            dp[i][0] = B
            dp[i][1] = dp[i+900][1] + 'B'  

    return dp

　あとはこれを左から、右から、左から……と繰り返すだけで表が埋まるはずです。感度3000までで試し打ち。

def ikisugi():

    inf = pow(10,9)
    dp = []
    max_kando = 3000+10

    for i in range(max_kando):
        dp.append([])
        dp[i].append(inf)
        dp[i].append('')

    dp[0][0] = 0

    for i in range(5):
        dp = left_dp(dp,max_kando)
        dp = right_dp(dp,max_kando)

    for i,dps in enumerate(dp):
        if dps[0] < inf:
            print(dps,i)

ikisugi()

　結果。

[0, ''] 0
[5, 'EEBAA'] 25
[4, 'EEBA'] 50
[6, 'CBAEBA'] 75
[3, 'EEB'] 100
.
.
.
[7, 'CBEAACE'] 2900
[7, 'EACBEAC'] 2925
[7, 'EACBBCE'] 2950
[7, 'EAEADBC'] 2975
[3, 'CEE'] 3000

　いい感じです。両方向DPの場合、ジグザグを何回繰り返せばいいかというのがわからないですね。とりあえず数を増やしても結果が変わらなかった時点で調査を打ち切っているので、結果に問題はないと思いますが。

　ちなみに、このままmax_kandoを35億まで上げると計算量が爆発してしまいます。上に述べたように、35億から5で割り続けた数を調べていきましょう。5の4乗で割った数から初めていくとして、max_kandoは560万強で済みます。これなら現実的な計算時間になります。

    for i in range(4,10):
        j = pow(5,i)
        k = int((3500000000/j))
        print(dp[k],k)
Output
[10, 'CDBDBDEEDD'] 5600000
[9, 'CDBDBDEED'] 1120000
[8, 'CDBDBDEE'] 224000
[8, 'CDBDCBBB'] 44800
[1000000000, ''] 8960
[1000000000, ''] 1792

　$22,400$からすでにレールに乗っており、後は5倍するだけになっていることがわかります。よって女騎士をオークの薬で感度35億に持っていく最小限の手順は、

CDBDBDEEDDDDDD

　であることがわかりました。わずか14手順でいけます！

　以下、検算。

C 2000
D 10000
B 9100
D 45500
B 44600
D 223000
E 223500
E 224000
D 1120000
D 5600000
D 28000000
D 140000000
D 700000000
D 3500000000

追記

　久しぶりに記事を見返してみましたが、これ普通に幅優先探索（BFS）で良かったですね。ジグザグとか考える必要はなくて、感度0のマスから1マスずつ進めていけば自動的に最短手順で埋め尽くされます。

from collections import deque

def kusuri(kando, s):
    if s == 'A':
        return kando/2
    if s == 'B':
        return kando - 900
    if s == 'C':
        return kando + 2000
    if s == 'D':
        return kando * 5
    if s == 'E':
        return kando + 500

max_range = 5600000

buc = [""]*(max_range+1)
d = deque()
d.append(0)

while(len(d)):
    loc = d[0]
    sen = buc[loc]
    d.popleft()
    for w in "ABCDE":
        nex_loc = int(kusuri(loc,w))
        if nex_loc < 1:
            continue
        if nex_loc > max_range:
            continue
        if buc[nex_loc] == "":
            buc[nex_loc] = sen+w
            d.append(nex_loc)

print(buc[max_range])
9
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
9
2