背景
以下のような問題を解いているときに行き詰まりました、、
扱う文字列XYZの定義を説明すると
レベル1のときは"XYZ"であると。
レベル2のときはと言うと "X" + "XYZ" + "Y" + "XYZ" + "Z" = "XXYZYXYZZ" となる。
要するにレベルnのときに "X" + (n - 1レベ) + "Y" + (n - 1レベ) + "Z" となるような文字列。
そして、レベルxのときの特定の区間の文字列が知りたいです。
開始地点をs、終了地点をgとします。
例えば以下の入出力になる想定です。
python
1# 入力 2x = 2 3s = 3 4g = 6 5 6# 出力 7YZYX
行ったこと
登場が遅れましたが、ここで動的計画法が出てきます。
とりあえずメモ化の事を考えながらレベルxまでの文字列を生成してメモしていきました。
以下のようなコードの具合です。
python
1x, s, g = map(int, input().split()) 2dp = [""] * 52 3def create_str(level): 4 if level == 1: 5 dp[1] = "XYZ" 6 return dp[1] 7 else: 8 if dp[level] == "": 9 dp[level] = "X" + create_str(level - 1) + "Y" + create_str(level - 1) + "Z" 10 return dp[level] 11 else: 12 return dp[level] 13 14data = create_str(x) 15print(data[s-1:g])
備考
- 入力部分は説明と少し違いますが一行でスペース区切りで値を受け取ってる仕様で書いてます。
- 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])
しかし、結局これくらいの工夫では結果は変わりませんでした(泣)
どなたか高速化の方法をご教示ください。
回答1件
あなたの回答
tips
プレビュー