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

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

# 経緯

こちらの@drkenさんの記事

* [AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～](https://qiita.com/drken/items/fd4e5e3630d0f5859067)

で紹介された10問が、AtCoder上で提出できるようになりました。
→[AtCoder Beginners Selection](https://beta.atcoder.jp/contests/abs)

その結果、**AtCoder に登録したら解くべき精選過去問 10 問を (任意の言語) で解いてみた** シリーズが流行ってます。
→[百花繚乱！なないろ言語で競技プログラミングをする資料まとめ](https://qiita.com/drken/items/6edb1c0542d4c3b7179c)

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

## なぜ 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](https://beta.atcoder.jp/contests/abc086/tasks/abc086_a)

```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](https://beta.atcoder.jp/contests/abc086/tasks/abc081_a)
```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](https://coffeescript-cookbook.github.io/chapters/strings/finding-substrings)に書いてありました。

# 第3問 [ABC 081 B - Shift only](https://beta.atcoder.jp/contests/abc086/tasks/abc081_b)
```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](https://beta.atcoder.jp/contests/abc086/tasks/abc087_b)
```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](https://beta.atcoder.jp/contests/abc086/tasks/abc083_b)
```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](https://beta.atcoder.jp/contests/abc086/tasks/abc088_b)
```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](https://beta.atcoder.jp/contests/abc086/tasks/abc085_b)
```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](https://beta.atcoder.jp/contests/abc086/tasks/abc085_c)
```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](https://beta.atcoder.jp/contests/abc086/tasks/abc049_c)
```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](https://beta.atcoder.jp/contests/abc086/tasks/abc086_c)
```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も好きなのですが、タイプ数が少なくて素直に書ける言語が好きなんだな〜と感じました。