AtCoder 精選過去問 10 問を JS ワンライナー で挑戦

## ことのはじまり・・・
「競技プログラミングを通して，みんなで楽しみながらプログラミング力をアップしよう！」ということで，職場でプロコン部が発足しました。[AtCoder](https://atcoder.jp/) という競技プログラミングサイトがあって，まずはこちらの記事に掲載されている過去問 10 問にチャレンジしてみました。

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

AtCoder は色んな言語で挑戦することができます。Rust や Haskell 使いのメンバーがいる中，何の言語がいいかな～と考えましたが，あまちゃんの私は結局 JavaScript を選択しました。でも，初級問題をただ単にクリアしても面白くないかな～と思い，なんとなく全てワンライナーで解いてみることにしました。


## ルール

+ １行のアロー関数（の組み合わせ）で構成
+ { } は使わない
+ for, if は使わない
+ 三項演算子はあり


## テンプレート

+ 標準入力相当の文字列を受け取り，標準出力に出す文字列を返す関数 `main` を実装する
+ 実際に標準入力から受け取って，標準出力するところは全ての問題共通なので分離する

``` js
const main = input => 'output'; // Implement this function

console.log(main(require('fs').readFileSync('/dev/stdin', 'utf8'))); // Common part
```

なので，実際には２行ですが，混ぜると煩雑になるので分けてます。
（合成可能なので，やろうと思えば１行にできるのでＯＫとしています）


## インデックス

まずはざっと解答一覧を並べてみます。こんな雰囲気です。

``` js

// ABC086A - Product
const main = input => input.split(' ').map(x => x & 1).reduce((a, x) => a & x) === 1 ? 'Odd' : 'Even';

// ABC081A - Placing Marbles
const main = input => input.split('').map(x => +x).reduce((a, x) => a + x);

// ABC081B - Shift only
const main = input => Math.min(...(input.split('\n')[1].split(' ').map(x => (+x).toString(2)).map(x => x.length - x.lastIndexOf('1') - 1)));

// ABC087B - Coins
const main = (fn => input => fn(...input.split('\n')))((a, b, c, x) => [...Array(Math.min(a, Math.floor(x / 500)) + 1).keys()].map(i => [...Array(Math.min(b, Math.floor((x - 500 * i) / 100)) + 1).keys()].filter(j => x - 500 * i - 100 * j <= 50 * c).length).reduce((acc, cur) => acc + cur));

// ABC083B - Some Sums
const main = (fn => input => fn(...input.split(' ')))((n, a, b) => [...Array(+n).keys()].map(x => x + 1).filter(x => (x2 => x2 >= a && x2 <= b)(x.toString().split('').reduce((acc, cur) => acc + (+cur), 0))).reduce((acc, cur) => acc + cur));

// ABC088B - Card Game for Two
const main = input => input.split('\n')[1].split(' ').map(x => +x).sort((a, b) => b - a).reduce((arr, x, i) => i % 2 == 0 ? [arr[0] + x, arr[1]] : [arr[0], arr[1] + x], [0, 0]).reduce((a, b) => a - b);

// ABC085B - Kagami Mochi
const main = input => [...new Set(input.split('\n').slice(1))].length - 1;

// ABC085C - Otoshidama
const main = input => ((n, y) => ((n, y, i) => i != null ? ((n, i, x) => ((n, i, j) => ((i, j, k) => `${i} ${j} ${k}`)(i, j, n - i - j))(n, i, x / 4))(n, i, y - n - 9 * i) : '-1 -1 -1')(n, y, [...Array(Math.min(2000, Math.floor(y / 10)) + 1).keys()].find(i => ((n, y, i) => ((n, i, x) => x % 4 === 0 && (((n, i, j) => ((j, k) => j >= 0 && k >= 0)(j, n - i - j))(n, i, x / 4)))(n, i, y - n - 9 * i))(n, y, i))))(...input.split(' ').map(x => +x).reduce((n, y) => [n, y / 1000]));

// ABC049C - Daydream
const main = input => ['eraser', 'erase', 'dreamer', 'dream'].reduce((arr, word) => [].concat(...arr.map(x => x.split(word).filter(x => x))), [input.trim()]).length == 0 ? 'YES' : 'NO';

// ABC086C - Traveling
const main = input => input.trim().split('\n').slice(1).map(x => x.split(' ').map(x2 => +x2)).reduce((p, n) => (p && ((n[0] & 1) === ((n[1] + n[2]) & 1)) && ((n[0] - p[0]) >= (Math.abs(n[1] - p[1]) + Math.abs(n[2] - p[2])))) ? n : null, [0, 0, 0]) ? 'Yes' : 'No';
```

つづいて，問題ごとの解説をしていきます。
問題文は意訳してあります。原文はリンク先を参照してください。


## １問目 [ABC086A - Product](https://abs.contest.atcoder.jp/tasks/abc086_a)

#### 問題：
a と b の積が偶数か奇数か

**入力：**
`a b`

**出力**
`Odd` or `Even`

#### 解答：

``` js
const main = input => input.split(' ')
  .map(x => x & 1)
  .reduce((a, x) => a & x) === 1 ? 'Odd' : 'Even';
```
https://atcoder.jp/contests/abs/submissions/8092590

#### 解説：

偶数か奇数かの判定は１ビット目が１か０かを見ればいいですね。
掛けたときの数が偶数か奇数かは，１と０を掛けた時の組み合わせを見ればわかります。

```
0 * 0 = 0
0 * 1 = 0
1 * 0 = 0
1 * 1 = 1
```

両方１のときは１，どちらかに０を含めば０になります。
また，ビットアンドでも同じ結果になりますね。

```
0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1
```

1. `split(' ')` 空白区切りで配列に変換
2. `map(x => x & 1)` １ビット目を取る（0 か 1になる）
3. `reduce((a, x) => a & x)` ２つの数をビットアンド ※
4. 上記の結果が 1 なら `'Odd'`, そうでなければ `'Even'`

※ reduce は初期値を省略すると最初の要素が初期値になります。要素が２つなので，１つ目と２つ目の要素がそれぞれ `a` と `x` になります。


## ２問目 [ABC081A - Placing Marbles](https://abs.contest.atcoder.jp/tasks/abc081_a)

#### 問題：
1 の数を数える

**入力：**
0 または 1 からなる３文字

**出力：**
1 の数

#### 解答：

``` js
const main = input => input.split('')
  .map(x => +x)
  .reduce((a, x) => a + x);
```
https://atcoder.jp/contests/abs/submissions/8092632

#### 解説：

1. `split('')` 文字列を１文字ずつの配列に変換
2. `map(x => +x)` 要素を全て数字に変換
3. `reduce((a, x) => a + x)` 全ての要素の合計（`sum` 的なもの）

#### 別解：

replace で '0' を削除して残った文字列の長さを数える。
ただし，入力に改行が含まれるので trim が必要。

``` js
const main = input => input.trim().replace(/0/g, '').length;
```

正規表現で '1' を数える。
でもめっちゃ遅かった・・・

``` js
const main = input => (input.match(/1/g) || []).length;
```


## ３問目 [ABC081B - Shift only](https://atcoder.jp/contests/abs/tasks/abc081_b)

#### 問題：
N 個の正の整数に対して，全てが 2 で割れる限り繰り返し，何回割れるかを数える

**入力：**
`N`
`A1, A2, ... AN`

**出力：**
何回割れるか

#### 解答：

``` js
const main = input => Math.min(
  ...(
    input.split('\n')[1]
      .split(' ')
      .map(x => (+x).toString(2))
      .map(x => x.length - x.lastIndexOf('1') - 1)
  )
);
```

https://atcoder.jp/contests/abs/submissions/8101953

#### 解説：

何回２で割れるかは，２進数にしたときに右から何個０が並ぶかで分かります。２で割るということはビットを１つ右にシフトするのと同じです。１ビット目が１の場合は奇数になるので割れません。０である限りは割ることができます。

例：216 の場合，２進数にすると 11011000 なので３回割ることができます。

数列の中から，この数字が一番小さいものを選びます。

1. `split('\n')[1]` 改行区切りで配列にして２行目だけ使用
2. `split(' ')` 空白区切りで配列化
3. `map(x => (+x).toString(2))` 要素を２進数文字列に変換
4. `map(x => x.length - x.lastIndexOf('1') - 1)` ０の数を数える ※
5. `Math.min(...array)` 配列の中で一番小さい要素

※ `lastIndexOf` は文字列を後ろから検索して最初に出てくるインデックスを取得します。これを文字列全体の長さから引くと後ろから数えて最初に１が出てくる数が分かります。０の数が知りたいので１引いています。

#### 別解：

先に全ての要素を reduce でビットオアした結果の０の数を数える。

でも，以下だと遅すぎ。。
`.split('').reverse().join('')` が遅いのかな。

``` js
const main = input => input.split('\n')[1]
  .split(' ')
  .map(x => (+x))
  .reduce((a, x) => a | x)
  .toString(2)
  .split('')
  .reverse()
  .join('')
  .indexOf('1');
```

https://atcoder.jp/contests/abs/submissions/8111956

これなら速度OK。

``` js
const main = input => (
  x => x.length - x.lastIndexOf('1') - 1
)(
  input.split('\n')[1]
    .split(' ')
    .map(x => (+x))
    .reduce((a, x) => a | x)
    .toString(2)
);
```

https://atcoder.jp/contests/abs/submissions/9199766


## ４問目 [ABC087B - Coins](https://atcoder.jp/contests/abs/tasks/abc087_b)

#### 問題：
500円玉を A 枚，100円玉を B 枚，50円玉を C 枚から，合計 X 円になる組み合わせは何通りか

**入力：**
`A`
`B`
`C`
`X`

**出力：**
組み合わせの数

#### 解答：

``` js
const main = (fn => input => fn(...input.split('\n')))(
  (a, b, c, x) =>
    [...Array(Math.min(a, Math.floor(x / 500)) + 1).keys()]
      .map(i =>
        [...Array(Math.min(b, Math.floor((x - 500 * i) / 100)) + 1).keys()]
          .filter(j => x - 500 * i - 100 * j <= 50 * c)
          .length
      )
      .reduce((acc, cur) => acc + cur)
);
```

https://atcoder.jp/contests/abs/submissions/8190974

#### 解説：

２重ループで探索します。
１週目は500円玉の枚数を `i` とするループ。
２週目は100円玉の枚数を `j` とするループ。
50円玉の枚数 `k` は他の変数から算出します。
（`x = 500 * i + 100 * j + 50 * k` より）

for は使わないので配列をつくって map や reduce でなんとかします。
`[...Array(N).keys()]` で 0 から N - 1 までの配列が生成できます。

1. １週目 ( i ) 用の配列を生成  
   i が `x / 500` を超えることはないので，どちらか小さい方を採用
2. ２週目 ( j ) 用の配列を生成  
   j が `(x - 500 * i) / 100)` を超えることはないので，どちらか小さい方を採用
3. 問題の条件でフィルター  
   `x - 500 * i - 100 * j <= 50 * c` を満たせば，k が存在することになる
4. `filter` した件数 ( length ) は j 配列内での件数
5. `reduce` で i 配列内での件数を合計
6. input を改行区切りで `split` し，分割代入で上記の関数に渡す ※

※ こうすることで input を `fn = (a, b, c, x) => num` という I/F に合わせた形で渡せます。展開しないと `arr[0], arr[1], arr[2], arr[3]` というように扱うことになり，可読性が低くなります。

また，input を扱う記述を先に持ってきたいので
「『fn を受け取ったら，input を split して fn に渡す関数』を返す関数に，本体の処理を fn として渡し，結果を main に設定する」
というようなことをしています。

以下のように書いたのと同じです。

``` js
const main = input => ((n, a, b) => { /* */ })(...input.split('\n'));
```


## ５問目 [ABC083B - Some Sums](https://atcoder.jp/contests/abs/tasks/abc083_b)

#### 問題：
1 以上 N 以下の整数のうち，10進法での各桁の和が A 以上 B 以下であるものの総和

**入力：**
`N A B`

**出力：**
総和

#### 解答：

``` js
const main = (fn => input => fn(...input.split(' ')))(
  (n, a, b) =>
    [...Array(+n).keys()].map(x => x + 1)
      .filter(x =>
        (x2 => x2 >= a && x2 <= b)(
          x.toString().split('').reduce((acc, cur) => acc + (+cur), 0)
        )
      )
      .reduce((acc, cur) => acc + cur)
);
```

https://atcoder.jp/contests/abs/submissions/8199934

#### 解説：

1. `[...Array(+n).keys()].map(x => x + 1)`  
   1 から n までの配列を生成
2. `x.toString().split('').reduce((acc, cur) => acc + (+cur), 0)`  
   ある数 x を10進法の文字列にしたときの各桁の数の合計
3. `(x2 => x2 >= a && x2 <= b)`  
   ある数 x2 が a 以上 b 以下かどうか
4. `filter` 1. の配列のうち上記条件を満たすもので絞り込み
5. `reduce` 絞り込んだ配列の合計
6. input を空白区切りで split し，分割代入で上記の関数に渡す ※

※ ４問目に同じ


## ６問目 [ABC088B - Card Game for Two](https://atcoder.jp/contests/abs/tasks/abc088_b)

#### 問題：
数字が書いてある N 枚のカードから，２人のプレイヤーが数字の大きい順にカードを引いていったときのそれぞれの合計について，先手は後手よりどのくらい大きいか

**入力：**
`N`
`a1 a2 a3 ... aN`

**出力：**
合計の差分

#### 解答：

``` js
const main = input => input.split('\n')[1].split(' ').map(x => +x)
  .sort((a, b) => b - a)
  .reduce(
    (arr, x, i) => i % 2 == 0
      ? [arr[0] + x, arr[1]]
      : [arr[0], arr[1] + x]
    , [0, 0]
  )
  .reduce((a, b) => a - b);
```

https://atcoder.jp/contests/abs/submissions/8392926

#### 解説：

数字を大きい順にソートして，偶数番目（先手）と奇数番目（後手）の数字に分けて，それぞれの合計の差分を取ります。

1. `input.split('\n')[1].split(' ').map(x => +x)`  
   入力の２行目だけ使用
   空白区切りで配列化し，各要素を数値に変換
2. `sort((a, b) => b - a)` 要素を降順でソート
3. １つ目の `reduce` ２要素の配列に，偶数番目と奇数番目の数字の合計をそれぞれ加算していく※１
4. ２つ目の `reduce` 上記合計の差分 ※２

※１ reduce に渡す関数の第三引数 i は要素のインデックス。アキュムレーターの初期値 [0, 0] からはじめて，偶数番目だったら第１要素，奇数番目だったら第２要素に加算していきます。

※２ 初期値を省略するとアキュムレーターの初期値は最初の要素。要素は２つしかないので，`a - b` が１回だけ行われて差分が返却されます。


## ７問目 [ABC085B - Kagami Mochi](https://atcoder.jp/contests/abs/tasks/abc085_b)

#### 問題：
N 個の数字から重複を除外した時の数

**入力：**
`N`
`d1`
`d2`
`:`
`dN`

**出力：**
一意の数

#### 解答：

``` js
const main = input => [...new Set(input.split('\n').slice(1))].length - 1;
```

https://atcoder.jp/contests/abs/submissions/8429734

#### 解説：

Set は一意の値を扱うコレクション。

1. `input.split('\n').slice(1)` 入力を改行区切りで配列化して１行目を捨てる
2. `new Set()` で一意にする
3. `[...(set)].length` で件数を取得する
4. `- 1` 入力に改行が入っているので，その分引く（`trim` でも可）

#### 別解：

- reduce でアキュムレーターが配列

``` js
const main = input => input.split('\n').slice(1)
  .reduce((s, x) => s.filter(y => x === y)[0] ? s : s.concat([x]), [])
  .length - 1;
```

https://atcoder.jp/contests/abs/submissions/8393485

- reduce でアキュムレーターが文字列

``` js
const main = input => input.split('\n').slice(1)
  .reduce((s, x) => s.indexOf(`:${x}-`) >= 0 ? s : `${s}:${x}-`, '')
  .replace(/-/g, '')
  .split(':')
  .length - 2;
```

https://atcoder.jp/contests/abs/submissions/8393479


## ８問目 [ABC085C - Otoshidama](https://atcoder.jp/contests/abs/tasks/abc085_c)

#### 問題：
10000 円札，5000 円札，1000 円札の合計枚数が N，合計金額が Y となる組み合わせが存在するかどうか

**入力：**
`N Y`

**出力：**
組み合わせが存在しない場合は以下
`-1 -1 -1`
組み合わせが存在する場合はその一例
10000 円札 i 枚，5000 円札 j 枚，1000 円札 k 枚として
`i j k`

#### 解答：

``` js
const main = input => (
  (n, y) => (
    (n, y, i) =>
      i != null
        ? (
          (n, i, x) => (
            (n, i, j) => (
              (i, j, k) => `${i} ${j} ${k}`
            )(i, j, n - i - j)
          )(n, i, x / 4)
        )(n, i, y - n - 9 * i)
        : '-1 -1 -1'
  )(n, y, [...Array(Math.min(2000, Math.floor(y / 10)) + 1).keys()].find(
    i => (
      (n, y, i) => (
        (n, i, x) => x % 4 === 0 && (
          (
            (n, i, j) => (
              (j, k) => j >= 0 && k >= 0
            )(j, n - i - j)
          )(n, i, x / 4)
        )
      )(n, i, y - n - 9 * i)
    )(n, y, i)
  ))
)(...input.split(' ').map(x => +x).reduce((n, y) => [n, y / 1000]));
```

https://atcoder.jp/contests/abs/submissions/8757513

#### 解説：

今回の中で一番エグイやつですね。。
そのままでは説明するのが難しいので，まずは for 文を使ったケースを見てみます。

``` js
const main = input => ((n, y) => {
  for (var i = 0; i <= Math.min(2000, Math.floor(y / 10)); i++) {
    var x = y - n - 9 * i;
    if (x % 4 !== 0) continue;
    var j = x / 4;
    var k = n - i - j;
    if (j >= 0 && k >= 0)
      return `${i} ${j} ${k}`;
  }
  return '-1 -1 -1';
})(...input.split(' ').map(x => +x).reduce((n, y) => [n, y / 1000]));
```

https://atcoder.jp/contests/abs/submissions/8755437

##### 線形オーダー

まず，最初に考えたコードは二重ループだったのですが，他のメンバーの方が線形オーダーで解いたよ（ドヤァ）という話をされていたので，再考しました。
変数が複数になるとその分ループは増えるので，線形（ネストしない）のためには変数を１にする必要があります。４問目の Coins と同様，i と j の値が分かれば k の値は分かるので変数は２になりますが，それだけでは足りません。

式１：`N = i + j + k`
式２：`Y = 10000 * i + 5000 * j + 1000 * k`

式が２つ与えられていることに着目すると，連立方程式で解くことができそうです。
数が大きいと分かりづらいので，式２は事前に 1000 で割っておきます。

`Y’ = 10 * i + 5 * j + k`

２つの式を引き算すると次のようになります。

`Y’ - N = 9i + 4j`

Y と N は定数なので変数 i が分かれば j も分かることとなり，線形オーダーにすることができます。

では，コード上の計算式をみてみます。

`x = y - n - 9 * i`
`j = x / 4`

これらの式で i から j を算出できます。
式を分けているのは，はじめから割り算してしまうと `x` が割り切れない場合に `j` が浮動小数点を扱うことになり，パフォーマンスが悪くなってしまうので，`x` が 4 で割り切れるかどうかの判定を挟み込むために式を分割しています。割り切れない場合は条件に合致しないのでスキップします。

`k = n - i - j`

こちらの式で k も分かります。
ただし，上記の式だけでは，いずれかの変数がマイナスの場合も合致してしまいますので，最後に正負の判定をします。

`j >= 0 && k >= 0`

以上の条件に合致したら，`${i} ${j} ${k}` を，いずれにも合致しなければ，`-1 -1 -1` を返却します。

ちなみに `const` ではなく `var` にしているのは，AtCoder の Node.js のバージョンが古いせいです。 [^1]

[^1]: `const` とすると最初に代入した値が不変のまま巻き上げられて２週目以降の代入が無視されます。でもエラーにはなりません。仕様というよりバグのレベルですね。

これらの走査を i ごとに行います（for文）
上限は問題の制約条件である 2000（N の最大値）または，Y を 10000 で割った値となります。(先に 1000 で割ってあるのでコード上は 10 で割っています)

最後に，`input` を上記の関数に渡します。
入力を空白で区切り，数値に変換し，y を 1000 で割り，分割代入します。

##### 関数化

次に for 版のプログラムを関数を使って for 文なしで記述してみます。
「ぎゃーもう分からん！」
大丈夫！落ち着いて１つずつ見ていけばわかります😅

``` js
const fx = (n, y, i) => y - n - 9 * i;
const fj = (x) => x / 4;
const fk = (n, i, j) => n - i - j;

const fc1 = (n, y, i) => fc2(n, i, fx(n, y, i));
const fc2 = (n, i, x) => x % 4 === 0 && fc3(n, i, fj(x));
const fc3 = (n, i, j) => fc4(j, fk(n, i, j));
const fc4 = (j, k) => j >= 0 && k >= 0;

const fo1 = (n, y, i) => i != null ? fo2(n, i, fx(n, y, i)) : '-1 -1 -1';
const fo2 = (n, i, x) => fo3(n, i, fj(x));
const fo3 = (n, i, j) => fo4(i, j, fk(n, i, j));
const fo4 = (i, j, k) => `${i} ${j} ${k}`;

const fc = (n, y) => [...Array(Math.min(2000, Math.floor(y / 10)) + 1).keys()].find(i => fc1(n, y, i));
const fo = (n, y) => fo1(n, y, fc(n, y));

const main = input => fo(...input.split(' ').map(x => +x).reduce((n, y) => [n, y / 1000]));
```

https://atcoder.jp/contests/abs/submissions/8755698

関数版では，find が検索対象の要素の i だけしか返せないので，走査する関数 `fc1` と文字列を生成する関数 `fo1` に分けています。
まず，`find + fc1` で条件と合致する i を探します。見つかったら i を返し，見つからなければ undefined が返ります。その結果を `fo1` に渡します。i があれば，あらためて j, k を算出した上で `'i j k'`を返します。i が見つからなければ `'-1 -1 -1'` を返します。

**▽** `fx`, `fj`, `fk` はそれぞれ x, j, k を算出します。（x = 4j）
これらは for 版と見た目がほとんど同じですね。

- `fx` は n, y, i から x
- `fj` は x から j
- `fk` は n, i, j から k

**▽** `fc1` ~ `fc4` は i, j, k が条件に合致するかどうかを検査します。
これらはステップごとに関数を分けています。
`fc1` -> `fc2` -> `fc3` -> `fc4` というように呼び出しています。
逆から見てみていきます。

- `fc4` は j, k が正の数かを判定します。しかし，まだ j, k はわかりません。
- そこで `fc3` は `fk` にて n, i, j から k を算出して `fc4` に渡します。
- まだ j も分からないので `fc2` は `fj` x から j を算出して `fc3` に渡します。  
  ただし，`fc2` では x が 4 で割り切れない場合は false を返して後続の呼び出しはしません。
- `fc1` は `fx` にて n, y, i から x を算出して `fc2` に渡します。

このように後続で必要になる計算を引数で渡しながらリレーすることで一連の処理を形成しています。

**▽** `fo1` ~ `fo4` は 出力する文字列を生成します。(`'i j k'` or `'-1 -1 -1'`)
こちらも同じようにステップで形成されています。

- `fo1` は i がなければ '-1 -1 -1' を返して終了。  
   i がある場合は x を算出して `fo2` へ。
- `fo2` は j を算出して `fo3` へ。
- `fo3` は k を算出して `fo4` へ。
- `fo4` は i, j, k から文字列を生成して返却。

##### 関数合成

そして，これらの関数を全て合成すると最初に掲載したプログラムになります。

お疲れ様でした👼

（補足）文字列を生成する方は 4 で割り切れるのが分かっているので x を介さなくてもOKですが，前段の処理と粒度を合わせてあります。


## ９問目 [ABC049C - 白昼夢 / Daydream](https://atcoder.jp/contests/abs/tasks/arc065_a)

#### 問題：
ある文字列 `S` が `dream`, `dreamer`, `erase`, `eraser` のみから構成されているか

**入力：**
`S`

**出力：**
条件に合致する場合は `YES`
そうでない場合 `NO`

#### 解答：

``` js
const main = input =>
  ['eraser', 'erase', 'dreamer', 'dream']
    .reduce(
      (arr, word) =>
        [].concat(...arr.map(x => x.split(word).filter(x => x))),
      [input.trim()]
    )
    .length == 0 ? 'YES' : 'NO';
```

https://atcoder.jp/contests/abs/submissions/9196800

#### 解説：

##### split

split は区切り文字で分割する関数ですが，分割後の配列から区切り文字自体は削除されます。これを利用して対象文字列群（`dream`, `dreamer`, `erase`, `eraser`）で split することで入力文字列から削除していき，最終的になくなれば対象文字列群のみで構成されていることが分かります。

replace の場合は，削除後に前後の文字列が連結されてしまい，誤判定していしまう恐れがあります。

```
eradreamser（期待値：NO）
↓ dream で replace
eraser
↓ eraser で replace
(空)
↓
結果：YES
```

split の場合

```
eradreamser（期待値：NO）
↓ dream で split
[era, ser]
↓ eraser で各要素を split
[era, ser]
↓
結果：NO
```

##### reduce

reduce によって，各対象文字列に対する処理結果をアキュムレーターに適用していきます。
split が配列を返すので，次の対象文字列はその各要素に適用する必要があります。
そうすると，配列がネストしてしまうので `flat` で一次元にします。

``` js
[['1', '2'], ['3', '4']].flat();
// > ['1', '2', '3', '4']
```

しかし，AtCoder の Node.js のバージョンが古くて `flat` がないので以下で代替します。

``` js
const flat = arr => [].concat(...arr);
flat([['1', '2'], ['3', '4']]);
// > ['1', '2', '3', '4']
```

また，split した結果，空文字列になる要素ができる可能性があるので filter で除外します。

入力文字列を配列にしてアキュムレーターの初期値に指定します。
こうすることで，すべて `配列 -> 配列` で扱うことができます。
例のごとく，テストケースによって入力に改行が入る場合があるので除去します。

最終的に配列が空になれば 'YES', 何か残ってしまえば 'NO' を返します。

##### order

対象文字列群の要素と順序ですが，以下のようになっています。

`['eraser', 'erase', 'dreamer', 'dream']`

これは先に split した結果が後段に影響を与えないようにするためです。

```
[dreameraser]（期待値：YES）
↓ eraser で split & flat
[dream]
↓ dream で split & flat
[]
↓
結果：YES
```

```
[dreameraser]（期待値：YES）
↓ dreamer で split & flat
[aser]
↓ eraser で split & flat
[aser]
↓
結果：NO
```

したがって，対象文字列群を適切に並べ替えないと成立しないのでアルゴリズムとしては汎用的ではありません。

#### 別解：

動的計画法を使うと速くて汎用的だと教えてもらいました。
こちらも試しにワンライナーで書いてみましたがあんまり速くならなかったです。
配列のコピーに時間が掛かるのかな？ filter しないと `TLE` になります。
ちなみに some はバージョンが低くて未対応・・・

``` js
const main = input => (
  (word, dict) => [...Array(word.length)]
    .reduce(
      (acc, _, idx) => acc.find(x => x === idx - 1) === undefined
        ? acc
        : dict.reduce(
          (acc2, key) => word.substring(idx, idx + key.length) !== key
            ? acc2
            : acc2.filter(x => x > idx).concat([idx + key.length - 1])
          , acc
        )
      , [-1]
    )
    .find(x => x === word.length - 1) !== undefined ? 'YES' : 'NO'
)(input.trim(), ['dream', 'dreamer', 'erase', 'eraser']);
```

https://atcoder.jp/contests/abs/submissions/me

え？貪欲法？
ループ回数が決まらないのでワンライナーでは無理です・・・
再帰は末尾再帰最適化に対応してないのでダメ。
ジェネレーター関数とか使えば無限イテレートできそうだけど，それ自体が一行では書けません。


## １０問目 [ABC086C - Traveling](https://atcoder.jp/contests/abs/tasks/arc089_a)

#### 問題：
時刻 0 に 点 (0, 0) を出発
1 以上 N 以下の各 i に対し，時刻 ti に 点 (xi, yi) を訪問可能か
ただし，時刻 t から時刻 t + 1 には (x ± 1, y) または (x, y ± 1) に移動しなければならない

**入力：**
N
t1 x1 y1
t2 x2 y2
:
tN xN yN

**出力：**
訪問可能であれば `Yes`
訪問不可能であれば `No`

（９問目と微妙に違うのが引っ掛け・・・）

#### 解答：

``` js
const main = input =>
  input.trim().split('\n').slice(1)
    .map(x => x.split(' ').map(x2 => +x2))
    .reduce((p, n) =>
      (p
        && ((n[0] & 1) === ((n[1] + n[2]) & 1))
        && ((n[0] - p[0]) >= (Math.abs(n[1] - p[1]) + Math.abs(n[2] - p[2])))
      ) ? n : null,
      [0, 0, 0]
    ) ? 'Yes' : 'No';
```

https://atcoder.jp/contests/abs/submissions/9196554

#### 解説：

`input.trim().split('\n').slice(1)`
改行区切りで配列化して１行目を捨てます。

`map(x => x.split(' ').map(x2 => +x2))`
各行を空白で配列化して数値に変換します。
[t, x, y] の配列（二次元配列）になります。

`reduce`
アキュムレーターは前回の時間と位置 [t, x, y] または null。
初期値 [0, 0, 0] から始まって
[t1, x1, y1]
[t2, x2, y2]
:
と検証していきます。
いずれかの段階で不適合となった場合は null。
最終的に値があれば 'Yes', null であれば 'No' となります。

条件：

1. 前回 (p) が null でないか  
   null の場合は既に不適合なので false
2. `(n[0] & 1) === ((n[1] + n[2]) & 1)`  
   今回 (n) の時間の偶奇と原点からの距離の偶奇が一致するか ※１
3. `((n[0] - p[0]) >= (Math.abs(n[1] - p[1]) + Math.abs(n[2] - p[2]))`  
   前回と今回の時間差内で移動可能な距離圏内か ※２

※１ 常に移動しなければならないということは，時間の偶奇と原点からの距離（あるいは前回からの距離）の偶奇が一致します。

```
t: 0, xy: [0, 0] -> Even
t: 1, xy: [1, 0] -> Odd
t: 2, xy: [1, 1] -> Even
t: 3, xy: [1, 2] -> Odd
t: 4, xy: [0, 2] -> Even
t: 5, xy: [0, 1] -> Odd
```

※２ 前回からの距離が前回からの時間よりも大きければ移動不可

#### 別解：

本当はこんな感じで配列内の要素を展開した状態で引数を受ければ，名前を付けられるのでもう少し可読性が高くなる気がします。でも，AtCoder の Node.js のバージョンが・・・

``` js
const main = input =>
  input.trim().split('\n').slice(1)
    .map(l => l.split(' ').map(v => +v))
    .reduce(([t1, x1, y1, ret], [t2, x2, y2]) =>
      (ret
        && ((t2 & 1) === ((x2 + y2) & 1))
        && ((t2 - t1) >= (Math.abs(x2 - x1) + Math.abs(y2 - y1)))
      ) ? [t2, x2, y2, true] : [t1, x1, y1, false],
      [0, 0, 0, true]
    ) ? 'Yes' : 'No';
```


## まとめ

- 関数ベースで記述することでスッキリ書ける場合もあるし，そうでない場合もあります。
- とくにパフォーマンスは悪化する可能性があります。
- 純粋な競技プログラミングとはまた少し違った視点でも楽しめます。
- AtCoder の Node.js のバージョンを上げてほしいです・・・

長くなりましたが，お付き合いありがとうございました！

よいお年をお迎えください🖐