Posted at

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

More than 1 year has passed since last update.

どうも〜最近AtCoderにハマっている prd_xxx です。

ノリと勢いでQiitaのアカウントを取ったので、ノリと勢いで記事を書いてみます。


経緯

こちらの@drkenさんの記事

で紹介された10問が、AtCoder上で提出できるようになりました。

AtCoder Beginners Selection

その結果、AtCoder に登録したら解くべき精選過去問 10 問を (任意の言語) で解いてみた シリーズが流行ってます。

百花繚乱!なないろ言語で競技プログラミングをする資料まとめ

というわけで、乗るしかない、このビッグウェーブに (ネタが古い)


なぜ CoffeeScript なのか?

まだ記事にされてない言語で、何かあったかな〜と頭をひねったところ、奇跡的に思い出しました。

5,6年ぐらい前、そういえば業務でCoffeeScriptを書いたことがあったな、と。

そして当時はそれなりに好きな言語だったな〜、と。

(なぜか社内では不評だったので悲しい)

(そしてなぜか、CoffeeScriptでググると、オワコンとかサジェストされてきて悲しい)

私自身、だいぶブランクがあってCoffeeScriptのことを忘れているのですが、

思い出しがてら、やってみようかなーと思います!!


どうやってAtCoderに提出するか?

さて、AtCoderは色々な言語をサポートしてますが、CoffeeScriptは提出できません

でも心配は要りません。

CoffeeScriptは、コンパイルするとJavaScriptになります!!

JavaScriptならAtCoderに提出できます!


そもそもCoffeeScriptって?

元々CoffeeScriptは、JavaScriptを書きやすくするために生まれた言語で、等価なJavaScriptに対してコード量が1/3削減できるらしいです。(本当か?)

私は、JavaScriptは全く書けないのですが、CoffeeScriptがJavaScriptよりも可読性に優れた言語であるという認識は変わりません。


  • JSは、=====の使い分けとか、ややこしい部分が多いイメージ

  • CSは、そのようなJSのアラを、隠してくれるイメージ

以下、この記事にはCoffeeScriptのみを載せます。(変換されたJavaScriptは読みづらいです)


第1問 ABC 086 A - Product


1.coffee

stdin = process.openStdin()

stdin.setEncoding 'utf8'
stdin.on 'data', (input) ->
s = input.trim().split(' ')
a = parseInt(s[0])
b = parseInt(s[1])
console.log if (a*b)%2 is 0 then 'Even' else 'Odd'
process.exit()

まずは小手調べ、のつもりだったのですが、

いきなり標準入力から文字列を受け取るところでハマりました。

(そういえば、この言語で標準入力を扱ったことがない!)

1行入力されるとstdin.on'data'イベントが走るので、それを利用しています。

また、process.exit()しないと、プログラムが終了しないので注意です。

標準出力はconsole.log() で大丈夫です。

if (条件) then (A) else (B) の形で三項演算子の働きをします。


第2問 ABC 081 A - Placing Marbles


2.coffee

stdin = process.openStdin()

stdin.setEncoding 'utf8'
stdin.on 'data', (input) ->
s = input.trim()
console.log s.split('1').length - 1
process.exit()

やりたいことは、標準入力で受け取った文字列に含まれる、1をカウントする問題です。

count()のようなメソッドはないので、split('1')で分割された数から1を引くというトリッキーなことをしています。

これは私の知恵ではなくて、CoffeeScript Cookbookに書いてありました。


第3問 ABC 081 B - Shift only


3.coffee

readline = require('readline')

lines = []
reader = readline.createInterface process.stdin, process.stdout

solve = (input) ->
N = parseInt input[0]
tokens = input[1].trim().split(' ')
nums = (parseInt(token) for token in tokens)
ans = 0
while true
for i in [0...N]
if nums[i]%2 is 0
nums[i] //= 2
else
console.log ans
process.exit()
ans++

reader.on 'line', (line) ->
lines.push line
solve(lines) if lines.length is 2



標準入力の壁、再び

標準入力でまたハマりました。

なぜなら、2問目までは1行だけ読み取ればよかったのですが、複数行を読み取る必要があるからです。

stdin.on を入れ子にしたりアホなことを試しました

色々試したところ、readlineモジュールを使うのが良さそうでした。

'line'イベントを拾うたびにグローバル変数'lines'に貯めていき、想定する行数まで入力されたら'solve(lines)'を走らせます。(以後、この形式に統一します)


(parseInt(token) for token in tokens) はPython等でもよく出てくる内包表記の書き方です。好き。

ロジックは問題文の通り、素直に実装しました。

2で割れる限り割っていき、割れなくなったら答えを出力して終了です。


第4問 ABC 087 B - Coins


4.coffee

readline = require('readline')

lines = []
reader = readline.createInterface process.stdin, process.stdout

solve = (input) ->
A = parseInt input[0]
B = parseInt input[1]
C = parseInt input[2]
X = parseInt input[3]
ans = 0
for a in [0..A]
for b in [0..B]
for c in [0..C]
ans++ if a*500 + b*100 + c*50 is X
console.log ans
process.exit()

reader.on 'line', (line) ->
lines.push line
solve(lines) if lines.length is 4


素直に3重ループを回す問題です。

[0..N]のように書くと0〜Nまでの連続した整数を扱えるのですが、



  • [0..N] : Nを含む (0 ≦ n ≦ N)


  • [0...N] : Nを含まない (0 ≦ n < N)

のような独特の表記ができます。


第5問 ABC 083 B - Some Sums


5.coffee

readline = require('readline')

lines = []
reader = readline.createInterface process.stdin, process.stdout

solve = (input) ->
tmp = input[0].split(' ')
N = parseInt tmp[0]
A = parseInt tmp[1]
B = parseInt tmp[2]
ans = 0
for a in [1..N]
sum = 0
for c in ''+a
sum += parseInt c
ans += a if A <= sum <= B
console.log ans
process.exit()

reader.on 'line', (line) ->
lines.push line
solve(lines) if lines.length is 1


文字列⇄数値の相互変換が必要な問題です。

int型の数値aをstringに直す際に、空文字に加算して''+aのように表記するのは、他の言語でも割と使える汎用的なやり方だと思っています。


第6問 ABC 088 B - Card Game for Two


6.coffee

readline = require('readline')

lines = []
reader = readline.createInterface process.stdin, process.stdout

solve = (input) ->
N = parseInt input[0]
cards = (parseInt token for token in input[1].split(' '))
cards.sort (a,b) -> b-a
alice = bob = 0
for card,i in cards
if i%2 is 0
alice += card
else
bob += card
console.log alice - bob
process.exit()

reader.on 'line', (line) ->
lines.push line
solve(lines) if lines.length is 2


ソートが必要です。

降順にするのに、sort (a,b) -> b-aを用いています。

for card,i in cardsのように書くと、

iがカウンタ、cardi番目の要素になります。


第7問 ABC 085 B - Kagami Mochi


7.coffee

readline = require('readline')

N = null
lines = []
reader = readline.createInterface process.stdin, process.stdout

solve = (input) ->
set = {}
for element in input
set[element] = true
console.log (key for key,value of set).length
process.exit()

reader.on 'line', (line) ->
if N?
lines.push line
solve(lines) if lines.length is N
else
N = parseInt line


要素の重複を取り除く問題です。

CoffeeScriptではオブジェクトは連想配列なので、setというオブジェクトを作り、お餅の半径をキーにして(値は何でも良いので)プロパティを追加していきます。

for k,v of (オブジェクト)で、プロパティをイテレートできるので、内包表記にぶち込んでlengthを出力しました。


第8問 ABC 085 C - Otoshidama


8.coffee

readline = require('readline')

lines = []
reader = readline.createInterface process.stdin, process.stdout

solve = (input) ->
tmp = input[0].split(' ')
N = parseInt tmp[0]
Y = (parseInt tmp[1]) // 1000
for x in [0..N]
for y in [0..N-x]
z = N - x - y
break if z < 0
if x*10 + y*5 + z is Y
console.log x,y,z
process.exit()
console.log -1,-1,-1
process.exit()

reader.on 'line', (line) ->
lines.push line
solve(lines) if lines.length is 1


第4問のCoinsと似てると思いきや、出力が3パラメータの組み合わせなので解の候補が広そうです。

ですが10000円札と5000円札が決まれば残りの1000円札の枚数は一意に決まるので、2重ループで大丈夫です。


第9問 ABC 049 C - 白昼夢 / Daydream


9.coffee

readline = require('readline')

lines = []
reader = readline.createInterface process.stdin, process.stdout

solve = (input) ->
S = input[0]
words = ['dream','dreamer','erase','eraser']
end = S.length
while end > 0
found = false
for word in words
l = word.length
if word is S.substr(end-l,l)
found = true
end -= l
break
unless found
console.log 'NO'
process.exit()
console.log 'YES'
process.exit()

reader.on 'line', (line) ->
lines.push line
solve(lines) if lines.length is 1


与えられた文字列Sが、['dream','dreamer','erase',eraser']のいずれかのみで構成できるかの問題です。

先頭からやると'dream''dreamer'等の区別が面倒なので、お尻からやっていくと楽です。

途中で出てくるunlessは、ifの否定を表す予約語。


第10問 ABC 086 C - Traveling


10.coffee

readline = require('readline')

N = null
lines = []
reader = readline.createInterface process.stdin, process.stdout

solve = (input) ->
t = x = y = 0
for line in input
tmp = line.split(' ')
ti = parseInt tmp[0]
xi = parseInt tmp[1]
yi = parseInt tmp[2]
dist = Math.abs(x-xi) + Math.abs(y-yi)
if dist > ti-t or dist%2 isnt (ti-t)%2
console.log 'No'
process.exit()
t = ti
x = xi
y = yi
console.log 'Yes'
process.exit()

reader.on 'line', (line) ->
if N?
lines.push line
solve(lines) if lines.length is N
else
N = parseInt line


旅行プランの各工程で、遂行できるかチェックすれば良いのですが、その場にとどまることができないという条件が落とし穴です。

地点Aから地点Bに行くときの距離と時間の偶奇が一致しているかをdist%2 isnt (ti-t)%2 でチェックしています。


感想

文法から何から相当忘れていたので、意外と骨が折れたのですが楽しかったです!!

自分はPythonも好きなのですが、タイプ数が少なくて素直に書ける言語が好きなんだな〜と感じました。