CrystalでAtCoder（ABC253）

CrystalでAtcoderに参加しているtamura2004です。
本日のABC253を題材に、競技プログラミングにおけるCrystalの小ネタを書こうと思います。

A - Median?

問題へのリンク

比較演算子の連鎖

PythonやJuliaには比較演算子の連鎖があり、3つ以上の変数を数学的に記述できます。Rubyではできなくてちょっと悔しかったんですが、Crystal ではできます。

コード

a, b, c = gets.to_s.split.map(&.to_i)
puts a <= b <= c || a >= b >= c ? "Yes" : "No"

デバッグマクロpp!

Crystalにはデバッグに便利なマクロpp!があります。
変数xをデバッグするときに、Rubyであれば、

x = 10
puts "x = #{x}" # => x = 10

こんな風に変数名などを記述しますが、Crystalのマクロでは、引数を構文木から参照できるので、

x = 10
pp! x # => x = 10

のように変数名を表示することができます。
引数に式を与えた場合は、

pp! 2 | 1 << 4 - 3 # => 2 | (1 << (4 - 3)) # => 2
pp! 1 < 2 < 3 # => 1 < 2 && 2 < 3

こんな感じに演算子の優先順位による括弧付けなどが表示されます。比較演算子の連鎖はシンタックスシュガーであって、複数の比較分の&&による結合であることが分かります。

B - Distance Between Tokens

問題へのリンク

オープンクラス

Crystalの標準ライブラリはCrystal自身で記述されており、オープンクラス（ユーザーがメソッドを追加できる）です。
例えば、直交座標を複素数で表すとして、標準クラスのComplexにマンハッタン距離のメソッドを追加して解くことができます。

コード

require "complex"

struct Complex
  def manhattan
    real.abs + imag.abs
  end
end

h, w = gets.to_s.split.map(&.to_i64)
s = Array.new(h) { gets.to_s }
cnt = [] of Complex
h.times do |y|
  w.times do |x|
    if s[y][x] == 'o'
      cnt << y.i + x
    end
  end
end

cnt[-1] *= -1
ans = cnt.sum.manhattan.to_i
pp ans

C - Max - Min Query

問題へのリンク

Multiset

PythonやRubyなどMultisetを持たないと少々困る系の問題です。
Crystalの場合、Arrayのinsert, deleteの内部処理にlibcのmemmoveを使用しており、定数倍が早いので、強引にArrayで解くことができます。

コード

q = gets.to_s.to_i

cnt = {} of Int64 => Int64
xs = [] of Int64

q.times do
  query = gets.to_s

  case query
  when /^1/
    _, x = query.split.map(&.to_i64)

    if cnt.has_key?(x) && cnt[x] > 0
      cnt[x] += 1
    else
      i = xs.bsearch_index(&.> x) || xs.size
      xs.insert(i, x)
      cnt[x] = 1_i64
    end
  when /^2/
    _, x, c = query.split.map(&.to_i64)
    
    next if !cnt.has_key?(x)
    cnt[x] -= Math.min(c, cnt[x])
    
    next if 0 < cnt[x]
    xs.bsearch_index(&.>= x).try do |i|
      xs.delete_at(i)
    end
  when /^3/
    puts xs[-1] - xs[0]
  end
end

D - FizzBuzz Sum Hard

問題へのリンク

Range#sum

前の記事で書いたら早速出題されました。CrystalのRange#sumはO(1)なので、以下のように素朴に書いてもTLEにならずACできます。

コード

n,a,b = gets.to_s.split.map(&.to_i64)
ans = (1_i64..n).sum
ans -= (1_i64..n//a).sum * a
ans -= (1_i64..n//b).sum * b
c = a.lcm(b)
ans += (1_i64..n//c).sum * c
pp ans