[Ruby]paiza DPメニュー 連続列

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

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

セクション4【連続列】は、隣り合う数列の値が昇順（または降順）に並んでいる区間のうち、最長であるものの長さを求める問題です。

STEP問題 を解いてみる

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

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

n人分の身長の配列aが与えられ、隣り合う身長の値が昇順（前項の値以上）に並んでいる区間のうち、最長であるものの長さを求める問題です。

漸化式

• dp[i] = 1
  (初期値 = 1)
• dp[i] = dp[i - 1] + 1 (a[i -1] <= a[i])
  (前項の値以上の時はカウントアップする)
• dp[i] = 1 (a[i -1] > a[i])
  (前項の値未満の時は初期値 = 1に戻す)

解答例

INPUT1 = <<~"EOS"
  5
  160
  178
  170
  190
  190
EOS
OUTPUT1 = <<~"EOS"
  3
EOS

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

  # dpテーブル初期化
  dp = [1]
  # dpテーブル更新
  # 前項の値以上ならdpテーブルをカウントアップ
  # そうでないならdpテーブルを 1 にもどす
  1.upto(n - 1) do |i|
    dp[i] = a[i - 1] <= a[i] ? dp[i - 1] + 1 : 1
  end

  # dpの最大値（最大区間数）を返す
  dp.max
end

puts solve(STDIN.read)

# puts solve(INPUT1)
# > 3

• 整数n, 配列aを受け取る。
• dpに[1]を代入する。
  (要素単体での最長は1)
• i = 1 ~ n-1で繰り返し処理を設定する。
  • dp[i] = a[i - 1] <= a[i] ? dp[i - 1] + 1 : 1
    • 前項の値以上ならdpテーブルをカウントアップ
    • そうでないならdpテーブルを 1 にもどす
• dpの最大値（最大区間数）を返す

入出力例1の処理

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

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

問題

攻略ポイント

問題を解く流れ

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

INPUT1 = <<~"EOS"
  5
  187
  192
  115
  108
  109
EOS
OUTPUT1 = <<~"EOS"
  3
EOS

p INPUT1
# > "5\n187\n192\n115\n108\n109\n"
p OUTPUT1
# > "3\n"

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

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

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

# 確認用コード
p solve(INPUT1)
# > [5, [187, 192, 115, 108, 109]]

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

• • 整数n, 配列aを受け取る。
  • dpに[1]を代入する。
    (要素単体での最長は1)
  • i = 1 ~ n-1で繰り返し処理を設定する。
    • dp[i] = a[i - 1] >= a[i] ? dp[i - 1] + 1 : 1
      • 前項の値以下ならdpテーブルをカウントアップ
      • そうでないならdpテーブルを 1 にもどす
  • dpの最大値（最大区間数）を返す

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

  # dpテーブル初期化
  dp = [1]
  # dpテーブル更新
  # 前項の値以上ならdpテーブルをカウントアップ
  # そうでないならdpテーブルを 1 にもどす
  1.upto(n - 1) do |i|
    dp[i] = a[i - 1] >= a[i] ? dp[i - 1] + 1 : 1
  end

  # 確認用コード
  dp
end

# 確認用コード
p solve(INPUT1)
# > [1, 1, 2, 3, 1]
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]
  # dpテーブル更新
  # 前項の値以上ならdpテーブルをカウントアップ
  # そうでないならdpテーブルを 1 にもどす
  1.upto(n - 1) do |i|
    dp[i] = a[i - 1] >= a[i] ? dp[i - 1] + 1 : 1
  end

  # dpの最大値（最大区間数）を文字列に変換し末尾に改行を追加
  dp.max.to_s << "\n"
end

# 確認用コード
p solve(INPUT1)
# > "3\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]
  # dpテーブル更新
  # 前項の値以上ならdpテーブルをカウントアップ
  # そうでないならdpテーブルを 1 にもどす
  1.upto(n - 1) do |i|
    dp[i] = a[i - 1] >= a[i] ? dp[i - 1] + 1 : 1
  end

  # dpの最大値（最大区間数）を文字列に変換し末尾に改行を追加
  dp.max.to_s << "\n"
end

puts solve(STDIN.read)

入出力例1の処理

今回のまとめ

セクション4は連続して増加（または減少）する区間の数を求める問題でした。

今回の問題はDPメニューのなかでも理解しやすい問題だったと思います。