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

More than 1 year has passed since last update.

実装リンク集 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を取ったことがある人はいませんでした…

moonscript.png

(AtCoder Problems Language Owners欄より)


解答

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


例題 PracticeA

https://practice.contest.atcoder.jp/tasks/practice_1



  • "*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)


第1問 ABC086A Product

https://abc086.contest.atcoder.jp/tasks/abc086_a


  • 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)())


第2問 ABC081A Placing Marbles

https://abc081.contest.atcoder.jp/tasks/abc081_a


  • 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)


第3問 ABC081B Shift only

https://abc081.contest.atcoder.jp/tasks/abc081_b


  • arrの各要素に対し2で割ることが出来た回数の最小値です。

  • INF値として1<<29が使われていますが、2倍してオーバーフローしない中で簡潔に書ける数として競技プログラミングではよく使われます。

  • Lua 5.3以降では//による整数除算が行なえます。(ただしMoonScriptで//=複合代入はできません)


    • 第4問の話題にもなりますが、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)


第4問 ABC087B Coins

https://abc087.contest.atcoder.jp/tasks/abc087_b


  • 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)


第5問 ABC083B Some Sums

https://abc083.contest.atcoder.jp/tasks/abc083_b


  • 変数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)


第6問 ABC088B Card Game for Two

https://abc088.contest.atcoder.jp/tasks/abc088_b


  • 降順でソートしたら、符号を切り替えながら足しこんでいきます。

  • 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)


第7問 ABC085B Kagami Mochi

https://abc085.contest.atcoder.jp/tasks/abc085_b


  • ソートしたら、直前の数値と同じかどうか見ていきます。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)


第8問 ABC085C Otoshidama

https://abc085.contest.atcoder.jp/tasks/abc085_c


  • 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")


第9問 ABC049C Daydream

https://abc049.contest.atcoder.jp/tasks/arc065_a


  • 文字列を逆にして比較していきます。

  • 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

https://abc086.contest.atcoder.jp/tasks/arc089_a


  • 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があれば…