Ruby で解く AtCoder ABC 201 D

はじめに

AtCoder Problems の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。

今回のお題

AtCoder Beginner Contest D - Game in Momotetsu World
Difficulty: 1317

今回のテーマ、ミニマックス法

本番中に分からなかったのですが、座標の和の奇遇(x + y) % 2で先手後手が定まることを利用して解いていきます。

ユーザ解説

user.rb

def dp(x, y)
  return @memo[y][x] if @memo[y][x]

  if (x + y) % 2 == 0
    @memo[y][x] = -10000
    if y < @h - 1
      if @memo[y][x] < dp(x, y + 1) + @a[y + 1][x]
        @memo[y][x] = dp(x, y + 1) + @a[y + 1][x]
      end
    end
    if x < @w - 1
      if @memo[y][x] < dp(x + 1, y) + @a[y][x + 1]
        @memo[y][x] = dp(x + 1, y) + @a[y][x + 1]
      end
    end
  else
    @memo[y][x] = 10000
    if y < @h - 1
      if @memo[y][x] > dp(x, y + 1) - @a[y + 1][x]
        @memo[y][x] = dp(x, y + 1) - @a[y + 1][x]
      end
    end
    if x < @w - 1
      if @memo[y][x] > dp(x + 1, y) - @a[y][x + 1]
        @memo[y][x] = dp(x + 1, y) - @a[y][x + 1]
      end
    end
  end
  @memo[y][x]
end
@h, @w = gets.split.map(&:to_i)
@a = Array.new(@h){ gets.chomp.bytes.map{ _1 == 43 ? 1 : -1 } }
@memo = Array.new(@h){ [nil] * @w }
@memo[@h - 1][@w - 1] = 0

opt = dp(0, 0)
if 0 < opt
  puts 'Takahashi'
elsif opt == 0
  puts 'Draw'
else
  puts 'Aoki'
end

ユーザ解説 を参考にしたコードです。

memo.rb

  if (x + y) % 2 == 0
    @memo[y][x] = -10000
    if y < @h - 1
      if @memo[y][x] < dp(x, y + 1) + @a[y + 1][x]
        @memo[y][x] = dp(x, y + 1) + @a[y + 1][x]
      end
    end

(x + y) % 2が0なので先手の手番になります。
dp(x, y + 1)のy + 1は下方向の移動を意味しています。

bytes.rb

@a = Array.new(@h){ gets.chomp.bytes.map{ _1 == 43 ? 1 : -1 } }

43は+の文字コードを表す整数です。
文字同士の比較より高速に動作します、といいますかこの問題はRubyにとって実行時間が厳しい問題ですね。

ord.rb

p "+".ord   # => 43

Qiitaユーザ解説

user.rb

h, w = gets.split.map(&:to_i)
grid = Array.new(h){ gets.chomp.chars.map{ _1 == '+' ? 1 : -1 } }
dp = Array.new(h){ [0] * w }
dp[-1][-1] = 0
(h - 1).downto(0) do |row|
  (w - 1).downto(0) do |col|
    next if row == h - 1 && col == w - 1
    if (row + col) % 2 == 0
      s1 = -10000
      s2 = -10000
      s1 = dp[row + 1][col] + grid[row + 1][col] if row < h - 1
      s2 = dp[row][col + 1] + grid[row][col + 1] if col < w - 1
      dp[row][col] = [s1, s2].max
    else
      s1 = 10000
      s2 = 10000
      s1 = dp[row + 1][col] - grid[row + 1][col] if row < h - 1
      s2 = dp[row][col + 1] - grid[row][col + 1] if col < w - 1
      dp[row][col] = [s1, s2].min
    end
  end
end
x = dp[0][0]
if x == 0
  puts 'Draw'
elsif x > 0
  puts 'Takahashi'
else
  puts 'Aoki'
end

@u2dayo さんの【AtCoder解説】PythonでABC201のA,B,C,D問題を制する！ を参考にしたコードです。
ユーザ解説は再帰でしたが、こちらはループで解きます。

	RubyU	RubyQ
コード長 (Byte)	999	805
実行時間 (ms)	1750	1510
メモリ (KB)	84476	77924

まとめ

• ABC 201 D を解いた
• hamayanhamayan さんありがとう
• u2dayo さんありがとう