Submission #2416640


Source Code Expand

def dcp(obj)
  Marshal.load(Marshal.dump(obj))
end

def result(board)
  score = 0
  2.times do |i|
    3.times do |j|
      score += @b[i][j] if board[i][j] == board[i+1][j]
      score += @c[j][i] if board[j][i] == board[j][i+1]
    end
  end
  score
end

def dfs(cnt, board)
  return result(board) if cnt == 9
  return @memo[[cnt, board]] if @memo.key?([cnt, board])
  
  if cnt.even?
    mx = 0
    3.times do |i|
      3.times do |j|
        if board[i][j] == -1
          board[i][j] = 1
          mx = [ mx, dfs(cnt+1, dcp(board)) ].max
          board[i][j] = -1
        end
      end
    end
    @memo[[cnt, board]] = mx
    return mx
  else
    mn = Float::INFINITY
    3.times do |i|
      3.times do |j|
        if board[i][j] == -1
          board[i][j] = 0
          mn = [ mn, dfs(cnt+1, dcp(board)) ].min
          board[i][j] = -1
        end
      end
    end
    @memo[[cnt, board]] = mn
    return mn
  end
end

@b = Array.new(2) { gets.split.map(&:to_i) }
@c = Array.new(3) { gets.split.map(&:to_i) }

@memo = {}
board = Array.new(3) { Array.new(3, -1) }
score = dfs(0, dcp(board))
puts score
puts @b.flatten.inject(&:+) + @c.flatten.inject(&:+) - score

Submission Info

Submission Time
Task C - 双子と○×ゲーム
User tfnw315
Language Ruby (2.3.3)
Score 100
Code Size 1228 Byte
Status AC
Exec Time 309 ms
Memory 4732 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 2
AC × 24
Set Name Test Cases
Sample sample-01.txt, sample-02.txt
All sample-01.txt, sample-02.txt, test-01.txt, test-02.txt, test-03.txt, test-04.txt, test-05.txt, test-06.txt, test-07.txt, test-08.txt, test-09.txt, test-10.txt, test-11.txt, test-12.txt, test-13.txt, test-14.txt, test-15.txt, test-16.txt, test-17.txt, test-18.txt, test-19.txt, test-20.txt, sample-01.txt, sample-02.txt
Case Name Status Exec Time Memory
sample-01.txt AC 306 ms 4732 KB
sample-02.txt AC 308 ms 4604 KB
test-01.txt AC 307 ms 4604 KB
test-02.txt AC 306 ms 4732 KB
test-03.txt AC 306 ms 4732 KB
test-04.txt AC 306 ms 4732 KB
test-05.txt AC 308 ms 4604 KB
test-06.txt AC 306 ms 4732 KB
test-07.txt AC 309 ms 4732 KB
test-08.txt AC 308 ms 4732 KB
test-09.txt AC 306 ms 4604 KB
test-10.txt AC 306 ms 4732 KB
test-11.txt AC 307 ms 4604 KB
test-12.txt AC 307 ms 4732 KB
test-13.txt AC 307 ms 4732 KB
test-14.txt AC 305 ms 4732 KB
test-15.txt AC 306 ms 4732 KB
test-16.txt AC 307 ms 4604 KB
test-17.txt AC 306 ms 4732 KB
test-18.txt AC 305 ms 4732 KB
test-19.txt AC 307 ms 4604 KB
test-20.txt AC 307 ms 4604 KB