AtCoder ABC261 D の提出を集計して感じたところ + Ruby で解けず crystal で解いてみた

はじめに

AtCoder さん、ありがとうございます。

D - Flipping and Bonus

いわゆるDP問題

提出の集計

コンテスト中（2022-07-23(土) 21:00 ~ 22:40）の延べ提出数（当社調べ）

	Python (3.8.2)	PyPy3 (7.3.0)	Ruby (2.7.1)	Crystal (0.33.0)	C++ (GCC 9.2.1)
AC	4	565	12	7	2283
WA	59	18	11	6	1006
TLE	150	11	27	1	191
RE	26	3	2	0	110
CE	0	0	0	1	46
subtotal	239	597	52	15	3636

C++やPyPyでの提出数が多いのはそうなのですが、
不正解の内訳からしますと、C++ PyPy CrystalはいかにWAを出さないかのゲーム、Ruby PythonはいかにTLEを出さないかのゲームで、同じ問題であっても競い合うゲームの内容が異なる様に思われます。

Ruby (TLE)

n, m = gets.split.map(&:to_i)
x = gets.split.map(&:to_i).reverse
cy = Hash.new(0)
m.times do
  c, y = gets.split.map(&:to_i)
  cy[c] = y
end
h = Hash.new(0)
h[0] = 0
x.each do |xx|
  q = Hash.new(0)
  h.each do |k, v|
    q[k + 1] = v + xx + cy[k + 1] if q[k + 1] < v + xx + cy[k + 1]
    q[0] = v if q[0] < v
  end
  h = q
end
puts h.values.max

上記表の、Ruby_TLE の 1/27 ですね。

ハッシュを使用することにより配列のサイズを小さくしつつ、コピーする戦略でしたがTLE。

いつものごとく最後の悪あがきcrystalizer2でトランスパイル。

crystal (AC)

n, m = read_line.split.map(&.to_i)
x = read_line.split.map(&.to_i).reverse
cy = Hash(Int32, Int32).new(0)
m.times do
  c, y = read_line.split.map(&.to_i)
  cy[c] = y
end
h = Hash(Int32, Int32).new(0)
h[0] = 0
x.each do |xx|
  q = Hash(Int32, Int64).new(0)
  h.each do |k, v|
    q[k + 1] = v.to_i64 + xx + cy[k + 1] if q[k + 1] < v + xx + cy[k + 1]
    q[0] = v.to_i64 if q[0] < v
  end
  h = q
end
puts h.values.max

上記表の、crystal_AC の 1/7 （悪あがきで大勝利）。

ここでは、overflow対応としてInt64を使用する必要があります。

	Ruby	crystal
実行時間(ms)	TLE	1015