AtCoder Beginners Selection を Ruby で解いた

制限時間ガン無視で、エレガントさ重視で書いた。

ABC086A - Product

# frozen_string_literal: true

a, b = gets.split(' ').map(&:to_i)
product_is_even = a.even? || b.even?

puts product_is_even ? 'Even' : 'Odd'

ABC081A - Placing Marbles

問題

提出結果

# frozen_string_literal: true

puts gets.count('1')

ABC081B - Shift only

問題

提出結果１（分かりやすさ重視）

# frozen_string_literal: true

_n = gets
a = gets.split(' ').map(&:to_i)

def divisible_count_by_2(num)
  quo, rem = num.divmod(2)
  rem.zero? ? divisible_count_by_2(quo) + 1 : 0
end

count = a.map { |ai| divisible_count_by_2(ai) }.min

puts count

提出結果２（パフォーマンス重視（のつもりだった））
※ 不必要なとこまで割り算をしないようにして、実行時間を短くするつもりだったが、無駄な工夫が災いしたのか実行時間はむしろ増大した。

# frozen_string_literal: true

_n = gets
a = gets.split(' ').map(&:to_i)

class RemBy2Sequence
  include Enumerable

  def initialize(num)
    @last_quo = num
  end

  def each
    loop do
      @last_quo, rem = @last_quo.divmod(2)
      yield rem
    end
  end
end

count = a.reduce(Float::INFINITY) do |result, ai|
  RemBy2Sequence.new(ai)
                .each_with_index
                .lazy
                .take_while { |r, i| r.zero? && i < result }
                .count
end

puts count

提出結果３（エレガントさ重視）

# frozen_string_literal: true

_n = gets
a = gets.split(' ').map(&:to_i)

count = a.map do |ai|
  ai.to_s(2).reverse.chars.take_while { |c| c == '0' }.count
end.min

puts count

ABC087B - Coins

問題

提出結果

# frozen_string_literal: true

purse_coin500_count = gets.to_i
purse_coin100_count = gets.to_i
purse_coin50_count = gets.to_i
total_amount = gets.to_i

max_coin500_count = [purse_coin500_count, total_amount / 500].min
pattern_count = (0..max_coin500_count).sum do |coin500_count|
  rest_amount_after500 = total_amount - 500 * coin500_count
  max_coin100_count = [purse_coin100_count, rest_amount_after500 / 100].min
  (0..max_coin100_count).count do |coin100_count|
    rest_amount = rest_amount_after500 - 100 * coin100_count
    coin50_count = rest_amount / 50
    coin50_count <= purse_coin50_count
  end
end

puts pattern_count

ABC083B - Some Sums

問題

提出結果

# frozen_string_literal: true

n, a, b = gets.split(' ').map(&:to_i)

total = (1..n).find_all do |num|
  sum = num.to_s.chars.map(&:to_i).sum
  a <= sum && sum <= b
end.sum

puts total

ABC088B - Card Game for Two

問題

提出結果

# frozen_string_literal: true

_n = gets.to_i
a = gets.split(' ').map(&:to_i).sort_by { -1 * _1 }
a << 0 if a.length.odd?

alice_point, bob_point = a.each_slice(2).to_a.transpose.map(&:sum)

puts alice_point - bob_point

ABC085B - Kagami Mochi

問題

提出結果

# frozen_string_literal: true

n = gets.to_i
a = Array.new(n) { gets.to_i }

count = a.uniq.length

puts count

ABC085C - Otoshidama

問題

提出結果

# frozen_string_literal: true

bill_count, amount = gets.chomp.split(' ').map(&:to_i)
amount /= 1000 # NOTE: treat amount in 1/1000 scale

# NOTE: Persons drawn in bills at 2019:
#  1,000 Yen : Hideyo Noguchi
#  5,000 Yen : Ichiyo Higuchi
# 10,000 Yen : Yukichi Fukuzawa

State = Struct.new(:noguchi, :higuchi, :fukuzawa) do
  class << self
    def impossible
      new(-1, -1, -1)
    end
  end

  def bill_count
    noguchi + higuchi + fukuzawa
  end

  # DEBUG:
  # def amount
  #   noguchi + higuchi * 5 + fukuzawa * 10
  # end

  def to_s
    "#{fukuzawa} #{higuchi} #{noguchi}"
  end
end

# NOTE: Adjust bill_count while concerning states which amount is always right.

max_noguchi_state = State.new(amount, 0, 0)
if max_noguchi_state.bill_count < bill_count
  puts State.impossible
  exit
end

# let bill_count of a state near ASAP with exchanging noguchi to higuchi
many_higuchi_state = lambda do |prev_state|
  exchange_count =
    [(prev_state.bill_count - bill_count) / 4, prev_state.noguchi / 5].min
  noguchi = prev_state.noguchi - exchange_count * 5
  higuchi = prev_state.higuchi + exchange_count
  State.new(noguchi, higuchi, prev_state.fukuzawa)
end.call(max_noguchi_state)

# let bill_count of a state right with exchanging higuchi to fukuzawa
goal_state = lambda do |prev_state|
  exchange_count = prev_state.bill_count - bill_count
  higuchi = prev_state.higuchi - exchange_count * 2
  fukuzawa = prev_state.fukuzawa + exchange_count
  return State.impossible if higuchi.negative?

  State.new(prev_state.noguchi, higuchi, fukuzawa)
end.call(many_higuchi_state)

puts goal_state
# puts goal_state.bill_count
# puts goal_state.amount * 1000

ABC049C - 白昼夢

問題

提出結果１（メモリ超過エラー）

# frozen_string_literal: true

class String
  def end_with?(*suffixes)
    suffixes.any? do |suf|
      len = suf.length
      suf == self[-len, len]
    end
  end
end

WORDS = %w[dream dreamer erase eraser].freeze

str = gets.chomp

def parsable?(str)
  return true if str.empty?

  first_word = WORDS.find { |word| str.end_with?(word) }
  return false if first_word.nil?

  parsable?(str[0, str.length - first_word.length])
end

puts parsable?(str) ? 'YES' : 'NO'

提出結果２（同じことが Haskell ならできるのに〜）
※ 提出結果１がメモリ超過なのは末尾再帰最適化が Ruby には実装されてないため。Haskell ならそれが実装されているのでメモリを食わない。

import qualified Data.ByteString.Char8 as BS
import           Data.List
import           Data.Maybe

main = do
  str <- BS.getLine
  putStrLn $
    if solve str
      then "YES"
      else "NO"

wordsForParse :: [BS.ByteString]
wordsForParse = map BS.pack ["dream", "dreamer", "erase", "eraser"]

parseTail :: BS.ByteString -> Maybe BS.ByteString
parseTail str = find (`BS.isSuffixOf` str) wordsForParse

solve :: BS.ByteString -> Bool
solve str
  | str == BS.empty = True
  | otherwise =
    case parseTail str of
      Just w  -> solve $ BS.take (BS.length str - BS.length w) str
      Nothing -> False

提出結果３（文字列を破壊的に削る）

# frozen_string_literal: true

class String
  def end_with?(*suffixes)
    suffixes.any? do |suf|
      len = suf.length
      suf == self[-len, len]
    end
  end
end

WORDS = %w[dream dreamer erase eraser].freeze

str = gets.chomp

def parsable?(str)
  rest = str
  loop do
    return true if rest.empty?

    first_word = WORDS.find { |word| rest.end_with?(word) }
    return false if first_word.nil?

    len = first_word.length
    rest.slice!(-len, len)
  end
  raise 'unexpected'
end

puts parsable?(str) ? 'YES' : 'NO'

提出結果４（文字列の走査位置のみ持つ）

# frozen_string_literal: true

WORDS = %w[dream dreamer erase eraser].freeze

str = gets.chomp

def parsable?(str)
  index = str.length - 1
  loop do
    return true if index.negative?

    parsed_word = WORDS.find do |word|
      len = word.length
      word == str[index - len + 1, len]
    end
    return false if parsed_word.nil?

    index -= parsed_word.length
  end
  raise 'unexpected'
end

puts parsable?(str) ? 'YES' : 'NO'

提出結果５（後ろから見ることを思いつかなかった場合）

# frozen_string_literal: true

str = gets.chomp

def parsable?(str)
  rest = str
  loop do
    return true if rest.empty?

    word = first_word(rest)
    return false if word.empty?

    rest.slice!(0, word.length)
  end
  raise 'unexpected'
end

def first_word(str)
  if str.start_with?('dream')
    if str.start_with?('dreamer') && !str.start_with?('dreamera')
      'dreamer'
    else
      'dream'
    end
  elsif str.start_with?('erase')
    if str.start_with?('eraser') && !str.start_with?('erasera')
      'eraser'
    else
      'erase'
    end
  else
    ''
  end
end

puts parsable?(str) ? 'YES' : 'NO'

ABC086C - Traveling

問題

提出結果

# frozen_string_literal: true

class SpaceVector
  attr_reader :x, :y

  def initialize(x, y)
    @x = x
    @y = y
  end

  def -(other)
    self.class.new(x - other.x, y - other.y)
  end

  def manhattan_length
    x.abs + y.abs
  end
end

class TimeSpaceVector
  attr_reader :time, :space

  def initialize(time, space)
    @time = time
    @space = space
  end

  def -(other)
    self.class.new(time - other.time, space - other.space)
  end
end

class Deer
  def can_move?(time_space)
    rest_time = time_space.time - time_space.space.manhattan_length
    rest_time >= 0 && rest_time.even?
  end
end

initial_point = TimeSpaceVector.new(0, SpaceVector.new(0, 0))

n = gets.chomp.to_i
points = [initial_point] + Array.new(n) do
  t, x, y = gets.chomp.split(' ').map(&:to_i)
  TimeSpaceVector.new(t, SpaceVector.new(x, y))
end

moves = points.each_cons(2).map { _2 - _1 }
deer = Deer.new
deer_can_move = moves.all? { |move| deer.can_move?(move) }

puts deer_can_move ? 'Yes' : 'No'

実コードでモンキーパッチする時はちゃんと Refinements を使おうね。

おわり。

RAS Syndrome

冗長。

AtCoder Beginners Selection を Ruby で解いた

ABC086A - Product

ABC081A - Placing Marbles

ABC081B - Shift only

ABC087B - Coins

ABC083B - Some Sums

ABC088B - Card Game for Two

ABC085B - Kagami Mochi

ABC085C - Otoshidama

ABC049C - 白昼夢

ABC086C - Traveling