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

どうも〜最近AtCoderにハマっている prd_xxx です。
ノリと勢いでQiitaのアカウントを取ったので、ノリと勢いで記事を書いてみます。

経緯

こちらの@drkenさんの記事

• AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～

で紹介された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がカウンタ、cardがi番目の要素になります。

第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も好きなのですが、タイプ数が少なくて素直に書ける言語が好きなんだな〜と感じました。