動的計画法を高速化したい(メモ化の過程でメモリが足りなくなってしまう)

Question

背景

以下のような問題を解いているときに行き詰まりました、、

扱う文字列XYZの定義を説明すると
レベル1のときは"XYZ"であると。
レベル2のときはと言うと "X" + "XYZ" + "Y" + "XYZ" + "Z" = "XXYZYXYZZ" となる。
要するにレベルnのときに "X" + (n - 1レベ) + "Y" + (n - 1レベ) + "Z" となるような文字列。

そして、レベルxのときの特定の区間の文字列が知りたいです。
開始地点をs、終了地点をgとします。

例えば以下の入出力になる想定です。

# 入力
x = 2
s = 3
g = 6

# 出力
YZYX

行ったこと

登場が遅れましたが、ここで動的計画法が出てきます。
とりあえずメモ化の事を考えながらレベルxまでの文字列を生成してメモしていきました。
以下のようなコードの具合です。

x, s, g = map(int, input().split())
dp = [""] * 52
def create_str(level):
    if level == 1:
        dp[1] = "XYZ"
        return dp[1]
    else:
        if dp[level] == "":
            dp[level] = "X" + create_str(level - 1) + "Y" + create_str(level - 1) + "Z"
            return dp[level]
        else:
            return dp[level]

data = create_str(x)
print(data[s-1:g])

備考

1. 入力部分は説明と少し違いますが一行でスペース区切りで値を受け取ってる仕様で書いてます。
2. dpの初期化で52個にしているのは制約条件でレベルの最大値が50と言う指定があるからです.

これで満足げにしていていくつかのテストケースを通してみたところ悲劇が。。。
これだと確かにほとんどのケースを通過するのですが重いテストケースの途中で実行が先に進まなくなってしまうと言う。。

考察

必要なのは求めたいレベルの-1だけであることと言うことに気がつき
必要のなくなったレベルのものを再度初期化していく事をしました。

x, s, g = map(int, input().split())

dp = [""] * 52
dp[1] = "XYZ"
inDp = [False] * 52
inDp[0] = True
inDp[1] = True

def create_str(level):
    if not inDp[level]:
        dp[level] = "X" + create_str(level - 1) + "Y" + create_str(level - 1) + "Z"
        inDp[level] = True
        # 工夫したのはココ！！
        dp[level - 2] = ""
    return dp[level]

data = create_str(x)
print(data[s-1:g])

しかし、結局これくらいの工夫では結果は変わりませんでした(泣)

どなたか高速化の方法をご教示ください。

Comments

[can110]

「アルゴリズム」タグをつけるとより多くの人の目につくかと思います。
また、g-s < 100などの、sとgに何らかの制限はないでしょうか？
ない場合x=30だと最大3221225469文字出力されることになりますが。

[kuraudo]

質問ありがとうございます。
・1 ≦ s ≦ t ≦ レベル k の XYZ 文字列の長さ
・1 ≦ t - s + 1 ≦ 100
となっています。

すいません、この制約を明記できておりませんでした。

> 「アルゴリズム」タグをつけるとより多くの人の目につくかと思います。
それっぽいタグを探してたんですけど始め作った際に思い浮かばなかったのでご指摘いただけて助かりました。ありがとうございます

[swordone]

これpaizaの問題では？

[xebme]

動的計画法が必要でしょうか。

Answer 1

文字列を結合すると大変なことになります。

文字列の長さを漸化式で表す
X(0) = 3
X(1) = 2 * X(0) + 3
X(2) = 2 * X(1) + 3

これを解くと、6 * 2 ^ n - 3

n = 100 のときとてつもなく大きくなりす。
7605903601369376408980219232253

PCで文字列の結合とスライスで解くのは無理です。

方針変更

• 入力 x s g を受け付ける
• x から、上の式を使って文字列の長さ L を計算する
• ある数 n と L から L のなかで n 番目の文字を見つける関数を作る
• s から g まで整数をインクリメントして関数を呼び、求める文字列を得る

n 番目の文字を見つける関数

• L = 3 のとき、n 番目はすぐにわかる。
• L > 3 の時、n が L の右端、中点、左端のとき、求める文字列はそれぞれ、'X', 'Y' ,'Z'
• それ以外なら、n が中点より大きいか小さいかに応じて再帰
  L = (L-3)/2
  n の L に対する相対的位置を計算しなおす

これでうまくいくはず。アルゴリズムに誤りがあれば指摘してください。

Comments

[kuraudo]

貴重な回答ありがとうございます。

[xebme]

動的計画法では、繰り返し同じ部分問題をとく必要があり、その部分問題が過去に計算したことがあるときにメモ化すると有効ですが、この問題は、毎回一度も解いたことがない部分問題を解くので、メモ化に意味がありません。動的計画法を適用できないことを認識してください。
アルゴリズムの教科書は、わずかに条件が変わると問題が解けなくなることが多いので、必ず問題分析をするよう奨めています。問題分析力を磨きましょう。

[kuraudo]

> 問題分析力を磨きましょう。
はい、アプローチの紹介だけでなく自分の解法に対するフィードバックまでくださり大変嬉しいです。ありがとうございます