質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.82%

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

解決済

回答 1

投稿 編集

  • 評価
  • クリップ 2
  • VIEW 1,068

kuraudo

score 137

背景

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

扱う文字列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])

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

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

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • can110

    2019/05/04 10:29 編集

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

    キャンセル

  • kuraudo

    2019/05/04 10:32 編集

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

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

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

    キャンセル

  • swordone

    2019/05/04 10:53

    これpaizaの問題では?

    キャンセル

  • xebme

    2019/05/04 13:40

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

    キャンセル

回答 1

checkベストアンサー

+2

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

文字列の長さを漸化式で表す
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 に対する相対的位置を計算しなおす

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/05/04 19:36

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

    キャンセル

  • 2019/05/04 19:50

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

    キャンセル

  • 2019/05/04 21:05

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.82%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る