🐢

[ABC349 E] Weighted Tic-Tac-Toe

2024/04/15に公開

Ruby

三目並べの勝敗判定の基本が学べる問題。

問題を要約する

三目並べの勝者は？
引き分けの場合にのみ置いたマスの合計得点で勝者を決める

コンテスト中は三目並べても得点で勝敗を決めるものだと勘違いしていた。だから、勝つには点数の高いマスから埋めていけばいいのに、なんで三目を並べようとしているのか謎だった。

問題を理解する

並べ勝ち

	0	1	2
0	○	×
1	×	○
2			○

この場合は三目並んだので○の勝ち。

引き分け

	0	1	2
0	○	×	○
1	×	○	×
2	○	×	○

この場合は(この問題の特殊ルールのため)○と×のマスの合計値の大きい方の勝ち。

実装方針

まず、

# player から指し始めたときの勝者を返す
def evaluate(player)
  # 勝者を返す
end

puts evaluate(0) == 0 ? "Takahashi" : "Aoki"

とする。

次に「勝者を返す」を4つのパートに分けて実装する。

並べ勝ちなら勝者を返す
引き分けなら得点で勝敗を決めて勝者を返す
すべてのマスに順に置いてみて evaluate(相手) を呼んで自分が勝者なら自分を返す
どのマスに置いても勝てないので相手を勝者として返す

解説の模範解答(C++)風の実装 (AC)

149 ms

N = 3
A = N.times.collect { gets.split.collect(&:to_i) }  # => [[-1, 1, 0], [-4, -2, -5], [-4, -1, -5]]
@board = Array.new(N) { Array.new(N) }
@score = Array.new(2, 0)
@memo = {}

# player から指し始めて勝者を返す
def evaluate(player)
  opponent = player ^ 1

  # 並べ勝ち？ (直前に指したのは相手なので「相手が勝ったか？」だけを調べる)
  if win?(opponent)
    return opponent
  end

  # 引き分け？ (得点で勝敗を決める)
  if @board.flatten.all?
    return @score[player] > @score[opponent] ? player : opponent
  end

  # 置く
  N.times do |x|
    N.times do |y|
      unless @board[x][y]
        @score[player] += A[x][y]
        @board[x][y] = player
        winner = @memo[@board] ||= evaluate(opponent) # 不自然なメモ化
        @board[x][y] = nil
        @score[player] -= A[x][y]
        if winner == player
          return player
        end
      end
    end
  end

  # すべてのパターンを試みたが勝てなかったので相手を返す
  opponent
end

# player は並べ勝ちしたか？
def win?(player)
  acc = false
  acc ||= N.times.any? { |y| N.times.all? { |x| @board[x][y] == player } } # →
  acc ||= N.times.any? { |x| N.times.all? { |y| @board[x][y] == player } } # ↓
  acc ||= N.times.all? { |x| @board[x][x] == player }                      # ＼
  acc ||= N.times.all? { |x| @board[-x.next][x] == player }                # ／
  acc
end

winner = evaluate(0)                                # => 1
puts winner == 0 ? "Takahashi" : "Aoki"

メモ化は evaluate の内側で行いたかったが、あちこちで return したせいで、呼び出し元でメモ化せざるをえなくなってしまった。

暫定リファクタリング (AC)

134 ms

N = 3
A = N.times.collect { gets.split.collect(&:to_i) }  # => [[-1, 1, 0], [-4, -2, -5], [-4, -1, -5]]
@board = Array.new(N) { Array.new(N) }
@score = Array.new(2, 0)
@memo = {}

# player から指し始めて勝者を返す
def evaluate(player)
  if @memo[@board]
    return @memo[@board]
  end

  opponent = player ^ 1
  winner = nil

  # 並べ勝ち？ (直前に指したのは相手なので「相手が勝ったか？」だけを調べる)
  winner ||= yield_self do
    if win?(opponent)
      opponent
    end
  end

  # 引き分け？ (得点で勝敗を決める)
  winner ||= yield_self do
    if @board.flatten.all?
      @score[player] > @score[opponent] ? player : opponent
    end
  end

  # 置く
  winner ||= yield_self do
    catch :break do
      N.times do |x|
        N.times do |y|
          unless @board[x][y]
            @score[player] += A[x][y]
            @board[x][y] = player
            provisional_winner = evaluate(opponent)
            @board[x][y] = nil
            @score[player] -= A[x][y]
            if provisional_winner == player
              throw :break, player
            end
          end
        end
      end
      nil
    end
  end

  # すべてのパターンを試みたが勝てなかったので相手を勝者とする
  winner ||= opponent

  # 勝者を返す
  @memo[@board] = winner
end

# player は並べ勝ちしたか？
def win?(player)
  acc = false
  acc ||= N.times.any? { |y| N.times.all? { |x| @board[x][y] == player } } # →
  acc ||= N.times.any? { |x| N.times.all? { |y| @board[x][y] == player } } # ↓
  acc ||= N.times.all? { |x| @board[x][x] == player }                      # ＼
  acc ||= N.times.all? { |x| @board[-x.next][x] == player }                # ／
  acc
end

winner = evaluate(0)                                # => 1
puts winner == 0 ? "Takahashi" : "Aoki"

あちこちで return しないようにしたもの。出口が一カ所になるため処理が追いやすい。それだけでなくメモ化も内部で行えるようになった。

さらにリファクタリング (AC)

136 ms

N = 3
A = N.times.collect { gets.split.collect(&:to_i) }  # => [[-1, 1, 0], [-4, -2, -5], [-4, -1, -5]]

RED  = 0
BLUE = 1

Integer.class_eval do
  def opponent = self ^ 1
end

@board = Array.new(N) { Array.new(N) }
@score = Array.new(2, 0)
@memo = {}

# player から指し始めたときの勝者を返す
def evaluate(player)
  @memo[@board] ||= win_by_line(player.opponent)
  @memo[@board] ||= draw
  @memo[@board] ||= try_all(player)
  @memo[@board] ||= player.opponent
end

# player が並べ勝ちしていれば player を返す
def win_by_line(player)
  if win?(player)
    player
  end
end

# 引き分けなら得点で勝敗を決めて勝者を返す
def draw
  if @board.flatten.all?
    @score[RED] > @score[BLUE] ? RED : BLUE
  end
end

# player がすべてのマスを試して player が勝てば player を返す
def try_all(player)
  catch :break do
    N.times do |x|
      N.times do |y|
        unless @board[x][y]
          @score[player] += A[x][y]
          @board[x][y] = player
          winner = evaluate(player.opponent)
          @board[x][y] = nil
          @score[player] -= A[x][y]
          if winner == player
            throw :break, player
          end
        end
      end
    end
    nil
  end
end

# player は並べ勝ちしたか？
def win?(player)
  acc = false
  acc ||= N.times.any? { |y| N.times.all? { |x| @board[x][y] == player } } # →
  acc ||= N.times.any? { |x| N.times.all? { |y| @board[x][y] == player } } # ↓
  acc ||= N.times.all? { |x| @board[x][x] == player }                      # ＼
  acc ||= N.times.all? { |x| @board[-x.next][x] == player }                # ／
  acc
end

winner = evaluate(RED)                              # => 1
puts winner == RED ? "Takahashi" : "Aoki"

evaluate 長すぎ問題とマジックナンバーを改善したもの。