AtCoder に登録したら解くべき精選過去問 10 問を MoonScript で解いてみた

実装リンク集 https://qiita.com/drken/items/6edb1c0542d4c3b7179c
問題一覧 https://abs.contest.atcoder.jp/assignments

私の実装	記事
Ruby (私家版)	https://qiita.com/cielavenir/items/c0a45b6b87c411b60b93
Swift	https://qiita.com/cielavenir/items/b90a94dce60a620fa2dc
C	https://qiita.com/cielavenir/items/ee1e47b844d05dcfc66e
VB.Net	https://qiita.com/cielavenir/items/7ddf5e9bac02daf72159
Pascal	https://qiita.com/cielavenir/items/530270ac4affca435442
Perl	https://qiita.com/cielavenir/items/4d16ba1be4ad6847a914
MoonScript/Lua	https://qiita.com/cielavenir/items/6553531e230f39cd6a3d

MoonScriptはAltLuaとして知られる言語ですね。

で。
MoonScriptでACを取ったことがあるの私だけってどういうことなんでしょうか。 なお2018年5月まではACを取ったことがある人はいませんでした…

(AtCoder Problems Language Owners欄より)

解答

mooncによるコンパイル結果も貼ります(全問Luaでも通ることを確認しています)

例題 PracticeA

• "*n"を重ねると複数個の読み取りができます。
• 改行はちゃんと読まないといけないみたいです。
• 文字列の結合は..です。

0.moon

#!/usr/bin/env moon
a = io.read("*n")
b,c = io.read("*n","*n")
io.read("*l")
l = io.read("*l")
print(tostring(a+b+c).." "..l)

0.lua

#!/usr/bin/env lua
local a = io.read("*n")
local b, c = io.read("*n", "*n")
io.read("*l")
local l = io.read("*l")
return print(tostring(a + b + c) .. " " .. l)

第１問 ABC086A Product

• if-elseは値を返します。

1.moon

#!/usr/bin/env moon
a,b = io.read("*n","*n")
print if a*b%2>0 "Odd" else "Even"

1.lua

#!/usr/bin/env lua
local a, b = io.read("*n", "*n")
return print((function()
  if a * b % 2 > 0 then
    return "Odd"
  else
    return "Even"
  end
end)())

第２問 ABC081A Placing Marbles

• gmatchを使うしかない…？
• Luaではstring.gmatch(l,"1")とl:gmatch("1")は同じ意味です。
  • MoonScriptではstring.gmatch(l,"1")とl\gmatch("1")です。
• MoonScriptでは複合代入ができます。

2.moon

#!/usr/bin/env moon
l = io.read("*l")
r = 0
r+=1 for _ in l\gmatch("1")
print r

2.lua

#!/usr/bin/env lua
local l = io.read("*l")
local r = 0
for _ in l:gmatch("1") do
  r = r + 1
end
return print(r)

第３問 ABC081B Shift only

• arrの各要素に対し2で割ることが出来た回数の最小値です。
• INF値として1<<29が使われていますが、2倍してオーバーフローしない中で簡潔に書ける数として競技プログラミングではよく使われます。
• Lua 5.3以降では//による整数除算が行なえます。(ただしMoonScriptで//=複合代入はできません)
  • 第４問の話題にもなりますが、LuaJITでは//は使えません。
    • Python3は//があるし、Rは%/%がある。 どういう形であれ、演算子形式で整数除算が記述できれば私はそれでいいんです。。
    • mrubyはa.div(b)しかないでしょうかねぇorz

3.moon

#!/usr/bin/env moon
r = 1<<29
n = tonumber(io.read("*l"))
for _ in io.read("*l")\gmatch("%d+")
	r0=0
	k=tonumber(_)
	while k%2<1
		r0+=1
		k=k//2
	if r>r0
		r=r0
print r

3.lua

#!/usr/bin/env lua
local r = 1 << 29
local n = tonumber(io.read("*l"))
for _ in io.read("*l"):gmatch("%d+") do
  local r0 = 0
  local k = tonumber(_)
  while k % 2 < 1 do
    r0 = r0 + 1
    k = k // 2
  end
  if r > r0 then
    r = r0
  end
end
return print(r)

第４問 ABC087B Coins

• 500円玉と100円玉の枚数を全探索します。

4.moon

#!/usr/bin/env moon
a = io.read("*n")
b = io.read("*n")
c = io.read("*n")
x = io.read("*n")
r = 0
for i=0,500
	for j=0,(x-500*i)//100
		k=x-500*i-100*j
		if k%50==0 and c>=k//50 and a>=i and b>=j
			r+=1
print r

4.lua

#!/usr/bin/env lua
local a = io.read("*n")
local b = io.read("*n")
local c = io.read("*n")
local x = io.read("*n")
local r = 0
for i = 0, 500 do
  for j = 0, (x - 500 * i) // 100 do
    local k = x - 500 * i - 100 * j
    if k % 50 == 0 and c >= k // 50 and a >= i and b >= j then
      r = r + 1
    end
  end
end
return print(r)

第５問 ABC083B Some Sums

• 変数sは各i(j)を10で割れるだけ割って、その間に出た余りの和です。
• 他の問題はそのまま(か、わずかな手直しで)LuaJITでも通すことができますが、この問題の除算は整数で行う必要があるため、この問題だけはLuaJITで通すことができませんでした。

5.moon

#!/usr/bin/env moon
n,a,b = io.read("*n","*n","*n")
r = 0
for i=1,n
	s=0
	j=i
	while j>0
		s+=j%10
		j=j//10
	if a<=s and s<=b
		r+=i
print r

5.lua

#!/usr/bin/env lua
local n, a, b = io.read("*n", "*n", "*n")
local r = 0
for i = 1, n do
  local s = 0
  local j = i
  while j > 0 do
    s = s + (j % 10)
    j = j // 10
  end
  if a <= s and s <= b then
    r = r + i
  end
end
return print(r)

第６問 ABC088B Card Game for Two

• 降順でソートしたら、符号を切り替えながら足しこんでいきます。
• MoonScriptにはリスト内包表記があります。コンパイルされたluaを見ると涙ぐましいことをしているようですね。。
• MoonScriptでテーブルを操作するには*arrとするようです。Luaにはそういう機能はないためインデックスを走査するしかないようです。

6.moon

#!/usr/bin/env moon
n = io.read("*n")
io.read("*l")
arr = [tonumber(e) for e in io.read("*l")\gmatch("%d+")]
table.sort(arr,(a,b)->a>b)
r = 0
t = 1
for e in *arr
	r+=t*e
	t=-t
print r

6.lua

#!/usr/bin/env lua
local n = io.read("*n")
io.read("*l")
local arr
do
  local _accum_0 = { }
  local _len_0 = 1
  for e in io.read("*l"):gmatch("%d+") do
    _accum_0[_len_0] = tonumber(e)
    _len_0 = _len_0 + 1
  end
  arr = _accum_0
end
table.sort(arr, function(a, b)
  return a > b
end)
local r = 0
local t = 1
for _index_0 = 1, #arr do
  local e = arr[_index_0]
  r = r + (t * e)
  t = -t
end
return print(r)

第７問 ABC085B Kagami Mochi

• ソートしたら、直前の数値と同じかどうか見ていきます。C++のuniqueと同様のアルゴリズムですね。
• arr\sort()とはできないみたいです。

7.moon

#!/usr/bin/env moon
n = io.read("*n")
arr = [io.read("*n") for i=1,n]
table.sort(arr)
r = 1
r+=1 for i=2,n when arr[i-1]!=arr[i]
print r

7.lua

#!/usr/bin/env lua
local n = io.read("*n")
local arr
do
  local _accum_0 = { }
  local _len_0 = 1
  for i = 1, n do
    _accum_0[_len_0] = io.read("*n")
    _len_0 = _len_0 + 1
  end
  arr = _accum_0
end
table.sort(arr)
local r = 1
for i = 2, n do
  if arr[i - 1] ~= arr[i] then
    r = r + 1
  end
end
return print(r)

第８問 ABC085C Otoshidama

• 1000円札と5000円札の枚数を全探索します。
• 関数外にreturnって書けるんですね。知らなかった。

8.moon

#!/usr/bin/env moon
n,y = io.read("*n","*n")
for i=0,n
	for j=0,n-i
		k=n-i-j
		if i*1000+j*5000+k*10000==y
			print tostring(k).." "..tostring(j).." "..tostring(i)
			return
print "-1 -1 -1"

8.lua

#!/usr/bin/env lua
local n, y = io.read("*n", "*n")
for i = 0, n do
  for j = 0, n - i do
    local k = n - i - j
    if i * 1000 + j * 5000 + k * 10000 == y then
      print(tostring(k) .. " " .. tostring(j) .. " " .. tostring(i))
      return
    end
  end
end
return print("-1 -1 -1")

第９問 ABC049C Daydream

• 文字列を逆にして比較していきます。
• Luaの文字列(や配列)は1-indexedです。
• e\reverse()はe\reverse!とも書けるみたいですが、Rubyと意味が違うので今回はやめました。

9.moon

#!/usr/bin/env moon
t = [e\reverse() for e in *{"dream","dreamer","erase","eraser"}]
s = io.read("*l")\reverse()
c = 1
l = s\len()
while c<=l
	k = nil
	for e in *t
		if s\sub(c,c+e\len()-1)==e
			k = e
			break
	if k==nil
		print "NO"
		return
	c+=k\len()
print "YES"

9.lua

#!/usr/bin/env lua
local t
do
  local _accum_0 = { }
  local _len_0 = 1
  local _list_0 = {
    "dream",
    "dreamer",
    "erase",
    "eraser"
  }
  for _index_0 = 1, #_list_0 do
    local e = _list_0[_index_0]
    _accum_0[_len_0] = e:reverse()
    _len_0 = _len_0 + 1
  end
  t = _accum_0
end
local s = io.read("*l"):reverse()
local c = 1
local l = s:len()
while c <= l do
  local k = nil
  for _index_0 = 1, #t do
    local e = t[_index_0]
    if s:sub(c, c + e:len() - 1) == e then
      k = e
      break
    end
  end
  if k == nil then
    print("NO")
    return
  end
  c = c + k:len()
end
return print("YES")

第10問 ABC086C Traveling

• dx+dyがdt以下かつdtとの偶奇が一致。

10.moon

#!/usr/bin/env moon
n = io.read("*n")
t = 0
x = 0
y = 0
for i=1,n
	t0,x0,y0 = io.read("*n","*n","*n")
	dt = t0-t
	dx = x0-x
	dy = y0-y
	if dx+dy>dt or (dt-dx-dy)%2>0
		print "No"
		return
	t = t0
	x = x0
	y = y0
print "Yes"

10.lua

#!/usr/bin/env lua
local n = io.read("*n")
local t = 0
local x = 0
local y = 0
for i = 1, n do
  local t0, x0, y0 = io.read("*n", "*n", "*n")
  local dt = t0 - t
  local dx = x0 - x
  local dy = y0 - y
  if dx + dy > dt or (dt - dx - dy) % 2 > 0 then
    print("No")
    return
  end
  t = t0
  x = x0
  y = y0
end
return print("Yes")

終わりに

Pythonっぽい書き方ですが後置ifがあるし、なにより(コード例はyhpg多段階選抜に譲りますが)ラムダ式が複数行にまたがって書けるのが最大限に嬉しい(この機能、Pythonにどれぐらい切望しているかわかりますか…)。

ただ、言語仕様はかなり好みなんですが、標準ライブラリがLua頼りなので、関数型ライクな書き方がしにくいのが辛いですね…せめてreduceがあれば…