ABC151 - Marginalia

A

puts gets.chomp.succ

B

n, k, m = gets.split.map(&:to_i)
sum = gets.split.map(&:to_i).inject(&:+)

target = m * n - sum
result = case
         when target < 0 then 0
         when target > k then -1
         else target
         end

puts result

C

'WA' だけの問題はペナルティにカウントされないことになかなか気づかなかった。'AC' が出て初めてカウントしないといけない。

n, m = gets.split.map(&:to_i)
ps = m.times.map {gets.split}

memo = Array.new(n + 1)
penalty_memo = Hash.new(0)
score = penalty = 0

ps.each do |p, s|
  pn = p.to_i    #problem number
  next if memo[pn]
  case s
  when "AC"
    score += 1
    penalty += penalty_memo[pn]
    memo[pn] = true
  else
    penalty_memo[pn] += 1
  end
end

puts "#{score} #{penalty}"

D

最初はTLE。それから、まさかの Ruby 2.3.3 なのにハマった。
方針がまちがっていた。スタートとゴールを設定して二重ループでやっていたが、よく考えてみたらスタートを設定してあとはいちばん遠いところへ行けばよいのだ。迷路を解くのはBFS。781ms。

class Position
  def initialize(x = 0, y = 0, count = 0)
    @x = x
    @y = y
    @count = count
  end
  attr_reader :x, :y, :count
end

h, w = gets.split.map(&:to_i)
maze = h.times.map {gets.chomp}
field = nil

Position.send(:define_method, :succ) do
  x = @x + 1
  y = @y
  if x >= w
    x = 0
    y += 1
    return false if y >= h
  end
  Position.new(x, y)
end

Position.send(:define_method, :move) do |dir|
  x, y = @x, @y
  dx, dy = [[1, 0], [0, -1], [-1, 0], [0, 1]][dir]
  x += dx
  y += dy
  return false if x >= w || x < 0 || y >= h || y < 0
  return false if field[y][x] != "."
  Position.new(x, y, @count + 1).mark
end

Position.send(:define_method, :mark) do
  field[@y][@x] = "*"
  self
end

solve_maze = ->(start) {
  return 0 if maze[start.y][start.x] == "#"
  field = maze.map(&:dup)
  max = 0
  q = [start.mark]
  while (po = q.shift)
    max = po.count if po.count > max
    4.times do |dir|
      nxt = po.move(dir)
      q << nxt if nxt
    end
  end
  max
}


start = Position.new
max = 0
loop do
  hosuu = solve_maze.(start)
  max = hosuu if hosuu > max
  break unless (start = start.succ)
end

puts max

E

TLE。

LIMIT = 10 ** 9 + 7

def factorial(n)
  result = 1
  2.upto(n) {|i| result *= i}
  result
end

def permutation(a, b)
  [*1..a].last(b).inject(1, &:*)
end
  
def combination(a, b)
  permutation(a, b) / factorial(b)
end


n, k = gets.split.map(&:to_i)
as = gets.split.map(&:to_i).sort
sum = 0

if k == 1
  puts 0
  exit
end

(0..n - k).each do |min|
  (min + k - 1..n - 1).each do |max|
    f = as[max] - as[min]
    sum += f * combination(max - min - 1, k - 2)
  end
end

puts sum % LIMIT

TLE。

LIMIT = 10 ** 9 + 7

n, k = gets.split.map(&:to_i)
as = gets.split.map(&:to_i).sort

acc = 1
factorial = [1] + (1..n).map {|i| acc *= i}
factorial_r = factorial.map {|a| Rational(1, a)}
combination = ->(a, b) {factorial[a] * factorial_r[b] * factorial_r[a - b]}

result = 0
(n - k + 1).times {|i| result -= as[i] * combination.(n - i - 1, k - 1)}
as.reverse!
(n - k + 1).times {|i| result += as[i] * combination.(n - i - 1, k - 1)}

puts result.to_i % LIMIT