LoginSignup
2

More than 3 years have passed since last update.

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

Posted at

ことのはじまり・・・

「競技プログラミングを通して,みんなで楽しみながらプログラミング力をアップしよう!」ということで,職場でプロコン部が発足しました。AtCoder という競技プログラミングサイトがあって,まずはこちらの記事に掲載されている過去問 10 問にチャレンジしてみました。

『AtCoder に登録したら次にやること ~ これだけ解けば十分闘える!過去問精選 10 問』

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

ルール

  • 1行のアロー関数(の組み合わせ)で構成
  • { } は使わない
  • for, if は使わない
  • 三項演算子はあり

テンプレート

  • 標準入力相当の文字列を受け取り,標準出力に出す文字列を返す関数 main を実装する
  • 実際に標準入力から受け取って,標準出力するところは全ての問題共通なので分離する
const main = input => 'output'; // Implement this function

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

なので,実際には2行ですが,混ぜると煩雑になるので分けてます。
(合成可能なので,やろうと思えば1行にできるのでOKとしています)

インデックス

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


// 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';

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

1問目 ABC086A - Product

問題:

a と b の積が偶数か奇数か

入力:
a b

出力
Odd or Even

解答:

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

解説:

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

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

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

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

※ reduce は初期値を省略すると最初の要素が初期値になります。要素が2つなので,1つ目と2つ目の要素がそれぞれ ax になります。

2問目 ABC081A - Placing Marbles

問題:

1 の数を数える

入力:
0 または 1 からなる3文字

出力:
1 の数

解答:

const main = input => input.split('')
  .map(x => +x)
  .reduce((a, x) => a + x);

解説:

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

別解:

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

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

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

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

3問目 ABC081B - Shift only

問題:

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

入力:
N
A1, A2, ... AN

出力:
何回割れるか

解答:

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

解説:

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

例:216 の場合,2進数にすると 11011000 なので3回割ることができます。

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

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

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

別解:

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

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

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

これなら速度OK。

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

4問目 ABC087B - Coins

問題:

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

入力:
A
B
C
X

出力:
組み合わせの数

解答:

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

解説:

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

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

  1. 1週目 ( i ) 用の配列を生成
    i が x / 500 を超えることはないので,どちらか小さい方を採用
  2. 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 に設定する」
というようなことをしています。

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

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

5問目 ABC083B - Some Sums

問題:

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

入力:
N A B

出力:
総和

解答:

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

解説:

  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 し,分割代入で上記の関数に渡す ※

※ 4問目に同じ

6問目 ABC088B - Card Game for Two

問題:

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

入力:
N
a1 a2 a3 ... aN

出力:
合計の差分

解答:

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

解説:

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

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

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

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

7問目 ABC085B - Kagami Mochi

問題:

N 個の数字から重複を除外した時の数

入力:
N
d1
d2
:
dN

出力:
一意の数

解答:

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

解説:

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

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

別解:

  • reduce でアキュムレーターが配列
const main = input => input.split('\n').slice(1)
  .reduce((s, x) => s.filter(y => x === y)[0] ? s : s.concat([x]), [])
  .length - 1;

  • reduce でアキュムレーターが文字列
const main = input => input.split('\n').slice(1)
  .reduce((s, x) => s.indexOf(`:${x}-`) >= 0 ? s : `${s}:${x}-`, '')
  .replace(/-/g, '')
  .split(':')
  .length - 2;

8問目 ABC085C - Otoshidama

問題:

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

入力:
N Y

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

解答:

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]));

解説:

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

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]));

線形オーダー

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

式1:N = i + j + k
式2:Y = 10000 * i + 5000 * j + 1000 * k

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

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

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

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

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

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

関数化

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

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]));

関数版では,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 はわかりません。
  • そこで fc3fk にて n, i, j から k を算出して fc4 に渡します。
  • まだ j も分からないので fc2fj x から j を算出して fc3 に渡します。
    ただし,fc2 では x が 4 で割り切れない場合は false を返して後続の呼び出しはしません。
  • fc1fx にて 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ですが,前段の処理と粒度を合わせてあります。

9問目 ABC049C - 白昼夢 / Daydream

問題:

ある文字列 Sdream, dreamer, erase, eraser のみから構成されているか

入力:
S

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

解答:

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';

解説:

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 で一次元にします。

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

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

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 はバージョンが低くて未対応・・・

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']);

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

10問目 ABC086C - Traveling

問題:

時刻 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

(9問目と微妙に違うのが引っ掛け・・・)

解答:

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';

解説:

input.trim().split('\n').slice(1)
改行区切りで配列化して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) の時間の偶奇と原点からの距離の偶奇が一致するか ※1
  3. ((n[0] - p[0]) >= (Math.abs(n[1] - p[1]) + Math.abs(n[2] - p[2]))
    前回と今回の時間差内で移動可能な距離圏内か ※2

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

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

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

別解:

本当はこんな感じで配列内の要素を展開した状態で引数を受ければ,名前を付けられるのでもう少し可読性が高くなる気がします。でも,AtCoder の Node.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 のバージョンを上げてほしいです・・・

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

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


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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2