ABC258A～Gをcrystalで解く

crystalでAtCoderに参加しています。
先週のABC258を題材に、競技プログラミングにおけるcrystalの小ネタを書いていきます。

A - When?

問題へのリンク

日付・時刻の取り扱い

rubyと同じく、21.hour + 30.minuteのように、Int型のメソッドとして時刻を生成できます。
この場合、時間の間隔を表しますので、Time::Span型になります。
to_sすると、デフォルトで21:30:05のように時：分：秒の文字列になります。
先頭5文字が答えですね。

文字列の一部を出力

printfなどフォーマット付き出力において、%sで文字列に変換した出力を行いますが
幅指定子に小数点を付けると、最大出力幅になりますので、%5.5sで先頭5文字を出力できます。

コード

k = gets.to_s.to_i64
t = 21.hour + k.minute
puts "%5.5s" % t

B - Number Box

問題へのリンク

max_ofブロック中のnext

開始位置と8方向について、最大値を全探索します。
crystalにはmax_ofがあるので簡潔に記述することができますが、一部の
条件をnextで飛ばす場合、何も引数を指定しなければエラーになります。
（これは、ブロックの値がnilになるためです）

nextに引数を与えると、それがブロックの値になります。
この問題では0以上が保証されているので、最小値の0を指定しています。

n = gets.to_s.to_i64
a = Array.new(n) { gets.to_s.chars.map(&.to_i64) }

ans = n.times.max_of do |y|
  n.times.max_of do |x|
    {-1, 0, 1}.max_of do |dx|
      {-1, 0, 1}.max_of do |dy|
        next 0 if dx.zero? && dy.zero?
        n.times.sum do |i|
          ny = (y + dy * i) % n
          nx = (x + dx * i) % n
          10_i64 ** i * a[ny][nx]
        end
      end
    end
  end
end

pp ans

C - Rotation

問題へのリンク

文字列を変えずに参照位置を変えるようにします。
種別の異なるクエリが与えられる場合、case ~ whenを使用すると少しだけ
見通しが良くなります。

n, q = gets.to_s.split.map(&.to_i64)
s = gets.to_s

i = 0
q.times do
  cmd, x = gets.to_s.split.map(&.to_i64)
  case cmd
  when 1
    i = (i - x) % n
  when 2
    puts s[(i+x-1)%n]
  end
end

D - Trophy

問題へのリンク

最適解の場合、途中のステージは１回のみ、最後のステージに残り全部として解いています。
厳密な証明はしませんでしたが、連続するステージの難易度が逆転する場合から、帰納法で
行けそうだなというあたりで見切り実装しました。

transpose

rubyと同じく2次元配列の転置を行います。
問題のa,bをそれぞれ別の配列にするために使用。

累積和

ArrayやIndexableのメソッドとして定義しておくと素早く実装できます。

class Array(T)
  def cs
    each_with_object([T.zero]) do |v, acc|
      acc << acc.last + v
    end
  end
end

n, x = gets.to_s.split.map(&.to_i64)
a, b = Array.new(n) do
  gets.to_s.split.map(&.to_i64)
end.transpose

csa = a.cs
csb = b.cs

ans = n.times.min_of do |i|
  next Int64::MAX if x < i + 1

  cnt = x - i - 1
  csa[i+1] + csb[i+1] + b[i] * cnt
end

pp ans

E - Packing Potatoes

問題へのリンク

本番では実装の筋が悪く4WA、時間も1時間ぐらい溶かしてしまいました。
良く良く睨めば尺取り法が使える問題。合わせてダブリングで最終位置を求めるのが
バグらせにくい解法だったかと思います。

# しゃくとり法で開始位置ごとの答えcntを求めておく
# 移動先はnexでダブリング

n, q, x = gets.to_s.split.map(&.to_i64)
w = gets.to_s.split.map(&.to_i64)
wsum = w.sum
ww = w + w

cnt = Array.new(n, 0_i64)
nex = Array.new(60) { Array.new(n, -1_i64) }

# しゃくとり法
m, r = x.divmod(wsum)
hi = 0_i64
sum = 0_i64
n.times do |lo|
  while hi < lo || (sum < r && hi < n * 2)
    sum += ww[hi]
    hi += 1
  end

  cnt[lo] = m * n + hi - lo
  nex[0][lo] = hi % n

  sum -= ww[lo]
end

# ダブリング準備
(1...60).each do |i|
  n.times do |j|
    nex[i][j] = nex[i-1][nex[i-1][j]]
  end
end

q.times do
  k = gets.to_s.to_i64.pred
  j = 0_i64

  # ダブリング
  60.times do |i|
    next if k.bit(i) == 0
    j = nex[i][j]
  end

  ans = cnt[j]
  pp ans
end

F - Main Street

問題へのリンク

recordマクロ

本来はワンライナーでstructを定義できるマクロですが、ブロック内にメソッド定義を
並べることもできます。

平面上の格子点を表すPointを定義して使いました。
「x座標だけk倍」「y座標だけbの倍数に切り捨て」「マンハッタン距離」など、この問題
でしか使わないようなメソッドもこちらで定義しておくと、本体のロジックがすっきりします。

enum

良い格子点（縦、横）や、とても良い格子点（公式解説参照）など点の区分や、
上下左右など方向を取り扱う必要があります。定数でも問題ないんですが、
crystal組み込みのenum（列挙型）を使うと、若干見通しが良くなります。
デバッグプリントの助けになること多し。

record Point, x : Int64, y : Int64 do
  def initialize(x, y)
    @x = x.to_i64
    @y = y.to_i64
  end

  def self.zero
    Point.new 0_i64, 0_i64
  end

  def zero?
    x.zero? && y.zero?
  end

  def +(b : self)
    Point.new b.x + x, b.y + y
  end

  def -(b : self)
    Point.new b.x - x, b.y - y
  end

  def %(b : Int)
    Point.new x % b, y % b
  end

  def //(b : Int)
    Point.new x // b, y // b
  end

  def mul_x(b : Int)
    Point.new x * b, y
  end

  def mul_y(b : Int)
    Point.new x, y * b
  end

  def eq_x?(b : self)
    x == b.x
  end

  def eq_y?(b : self)
    y == b.y
  end

  def floor_x(b : Int)
    Point.new x // b * b, y
  end

  def floor_y(b : Int)
    Point.new x, y // b * b
  end

  def ceil_x(b : Int)
    Point.new (x + b - 1) // b * b, y
  end

  def ceil_y(b : Int)
    Point.new x, (y + b - 1) // b * b
  end

  def manhattan
    x.abs + y.abs
  end
end

struct Int
  def x
    Point.new self, 0_i64
  end

  def y
    Point.new 0_i64, self
  end
end

enum Place
  Cross
  Tate
  Yoko
  Other
end

enum Direction
  Up
  Down
  Right
  Left
end

class ABC258F
  getter b : Int64
  getter k : Int64

  def initialize(@b, @k)
  end

  def place(z)
    w = z % b
    case
    when w.zero?   then Place::Cross
    when w.x.zero? then Place::Tate
    when w.y.zero? then Place::Yoko
    else                Place::Other
    end
  end

  def street(z, d)
    case d
    when .up?    then z.ceil_y(b)
    when .down?  then z.floor_y(b)
    when .right? then z.ceil_x(b)
    else              z.floor_x(b)
    end
  end

  def streets(z)
    return [{z, 0_i64}] unless place(z).other?

    Direction.values.map do |d|
      w = street(z, d)
      cost = (w - z).manhattan * k
      {w, cost}
    end
  end

  def intersections(z)
    case place(z)
    when .other? then [] of {Point, Int64}
    when .cross? then [{z, 0_i64}]
    when .tate?
      [Direction::Up, Direction::Down].map do |d|
        w = street(z, d)
        cost = (w - z).manhattan
        {w, cost}
      end
    else
      [Direction::Right, Direction::Left].map do |d|
        w = street(z, d)
        cost = (w - z).manhattan
        {w, cost}
      end
    end
  end

  def solve(s, g)
    Math.min (s - g).manhattan * k, dist(s, g)
  end

  def dist(s, g)
    streets(s).min_of do |z, cost_z|
      streets(g).min_of do |w, cost_w|
        dist_between_street(z, w) + cost_z + cost_w
      end
    end
  end

  def dist_between_street(s, g)
    ans = case
          when place(s) == place(g) == Place::Tate && (s // b).eq_y?(g // b)
            (s - g).mul_x(k).manhattan
          when place(s) == place(g) == Place::Yoko && (s // b).eq_x?(g // b)
            (s - g).mul_y(k).manhattan
          else
            (s - g).manhattan
          end
    Math.min ans, dist_between_intersection(s, g)
  end

  def dist_between_intersection(s, g)
    intersections(s).min_of do |z, cost_z|
      intersections(g).min_of do |w, cost_w|
        (z - w).manhattan + cost_z + cost_w
      end
    end
  end
end

t = gets.to_s.to_i64
t.times do
  b, k, sx, sy, gx, gy = gets.to_s.split.map(&.to_i64)
  f = ABC258F.new(b, k)
  pp f.solve(sx.x + sy.y, gx.x + gy.y)
end

G - Triangle

問題へのリンク

公式ではC++のbitsetで解いていますが、crystalではBigInt(多倍長整数)で解けます。
若干遅いのでTLEのリスクはありますが（本番後に）1656msで通りました。

• String#to_big_i(2)で文字列を2進数とみなして取り込める
• BigInt#popcountでビットが1の数を数えられる
• BigInt#&で論理積が取れる

require "big"

n = gets.to_s.to_i64
a = Array.new(n) do
  gets.to_s.reverse.to_big_i(2)
end

ans = 0_i64
(n-1).times do |i|
  (i+1...n).each do |j|
    next if a[i].bit(j) == 0
    ans += (a[i] & a[j]).popcount
  end
end

pp ans // 3