[Ruby]paiza DPメニュー 部分列

こんにちは！じゃいごテックのあつしです。

今回はpaiza DPメニュー 「セクション5【部分列】 STEP1, FINAL」 を解説します。
DPメニューは動的計画法(Dynamic Programming, DP)に関する6個のセクションで構成されています。

セクション5【部分列】は、配列からいくつかの要素を取り出して、隣り合う数列の値が常に大きい（または常に小さい）区間のうち、最長であるものの長さを求める問題です。
※ 部分列：飛び飛びはOKですが、要素の順番を変えてはいけません。

STEP問題 を解いてみる

簡単な解説は付けていますが、難しいと感じたら下記の記事も参考にしてみて下さい。

STEP1: 最長部分増加列 (paizaランク B 相当)

n本分の木の長さの配列aが与えられるので、最長の増加部分列の長さを求める問題です。

解答例

INPUT1 = <<~"EOS"
  5
  100
  102
  101
  91
  199
EOS
OUTPUT1 = <<~"EOS"
  3
EOS

def solve(input_lines)
  # 入力受け取り
  n, *a = input_lines.split("\n").map(&:to_i)

  # dpテーブル初期化
  dp = [1] * n

  # dpテーブル更新
  1.upto(n - 1) do |i|
    0.upto(i - 1) do |j|
      if a[j] < a[i]
        # 最後が木 j であるような増加部分列の末尾に木 i をくっつける
        dp[i] = [dp[i], dp[j] + 1].max
      end
    end
  end

  # 最大値を返す
  dp.max
end

puts solve(STDIN.read)

# 確認用コード
# puts solve(INPUT1)
# > 3

• 整数n, 配列aを受け取る。
• dpに[1] * nを代入する。
  (要素単体での最長は1)
• i = 1 ~ n-1で繰り返し処理を設定する。
  • j = 0 ~ i-1で繰り返し処理を設定する。
    • a[j] > a[i] なら dp[i] を [dp[i], dp[j] + 1].max で更新する
• dpの最大値（増加部分列が最大になる区間の長さ）を返す

入出力例1の処理

ここからi = 1 ~ n-1のループ

FINAL問題: 最長減少部分列 (paizaランク B 相当)

※ paizaレベルアップ問題集 DPメニューより

問題

攻略ポイント

問題を解く流れ

入出力例をコピペしてヒアドキュメントで変数に代入し、データを確認します。正しく受け取れていれば確認用コードは削除します。

INPUT1 = <<~"EOS"
  5
  109
  110
  108
  103
  100
EOS
OUTPUT1 = <<~"EOS"
  4
EOS

# 確認用コード
p INPUT1
# > "5\n109\n110\n108\n103\n100\n"
p OUTPUT1
# > "4\n"

続いて、問題を解くsolveメソッドを変数の下に定義し、入力データを受け取る処理を書きます。

def solve(input_lines)
  # 入力受け取り
  n, *a = input_lines.split("\n").map(&:to_i)

  # 確認用コード
  [n, a]
end

# 確認用コード
p solve(INPUT1)
# > [5, [109, 110, 108, 103, 100]]

データが正しく受け取れていれば、solve メソッドに処理を追加していきます。
※ 不等号の向きが変わるだけで、STEP1と同じ問題です。

• • 整数n, 配列aを受け取る。
  • dpに[1] * nを代入する。
    (要素単体での部分列は1)
  • i = 1 ~ n-1で繰り返し処理を設定する。
    •  j = 1 ~ i-1で繰り返し処理を設定する。
      • もし a[j] > a[i] かつ dp[i] < dp[j] + 1 なら dp[i] を dp[j] + 1 で更新する
  • dpの最大値（減少部分列が最大になる区間の長さ）を返す

def solve(input_lines)
  # 入力受け取り
  n, *a = input_lines.split("\n").map(&:to_i)

  # dpテーブル初期化
  dp = [1] * n

  # dpテーブル更新
  1.upto(n - 1).each do |i|
    0.upto(i - 1).each do |j|
      if a[j] > a[i]
        # 最後が木 j であるような減少部分列の末尾に木 i をくっつける
        dp[i] = [dp[i], dp[j] + 1].max
      end
    end
  end

  # 確認用コード
  dp
end

# 確認用コード
p solve(INPUT1)
# > [1, 1, 2, 3, 4]
p solve(INPUT1) == OUTPUT1
# > false

dpテーブルの内容が良さそうなら、出力を整えれば完成です。
p solve(INPUT1) == OUTPUT1 -> true を確認するために、出力を文字列に変換して末尾に改行を加えます。

def solve(input_lines)
  # 入力受け取り
  n, *a = input_lines.split("\n").map(&:to_i)

  # dpテーブル初期化
  dp = [1] * n

  # dpテーブル更新
  1.upto(n - 1).each do |i|
    0.upto(i - 1).each do |j|
      if a[j] > a[i]
        # 最後が木 j であるような減少部分列の末尾に木 i をくっつける
        dp[i] = [dp[i], dp[j] + 1].max
      end
    end
  end

  # 減少部分列が最大になる区間の長さを文字列に変換し末尾に改行を追加
  dp.max.to_s << "\n"
end

# 確認用コード
p solve(INPUT1)
# > "4\n"
p solve(INPUT1) == OUTPUT1
# > true

入出力例での動作確認が出来ましたので、標準入力からのデータ受け取りに変更して、手動で動作確認をしたら提出します。
複数行のデータ受け取りなので STDIN.read を使います。（入力終了は Ctrl+D 又は Ctrl+Z)

解答コード

def solve(input_lines)
  # 入力受け取り
  n, *a = input_lines.split("\n").map(&:to_i)

  # dpテーブル初期化
  dp = [1] * n

  # dpテーブル更新
  1.upto(n - 1).each do |i|
    0.upto(i - 1).each do |j|
      if a[j] > a[i]
        # 最後が木 j であるような減少部分列の末尾に木 i をくっつける
        dp[i] = [dp[i], dp[j] + 1].max
      end
    end
  end

  # 減少部分列が最大になる区間の長さを文字列に変換し末尾に改行を追加
  dp.max.to_s << "\n"
end

puts solve(STDIN.read)

入出力例1の処理

ここからi = 1 ~ n-1のループ

今回のまとめ

セクション5は配列から選択した要素が連続して増加（または減少）する区間の数を求める問題でした。

いきなりこの問題に挑戦すると難しいですが、セクション1から順番に解いてきたらコツがつかめたかと思います！