【Atcoder】JavaScriptで550問以上過去問を解いて、気付いた罠・注意点

JavaScriptでAtcoderに挑む

かれこれJavaScriptで550問以上Atcoderの過去問を解きました。（なお未だに茶色コーダー...）

この手の分野では、Cなどの高速な言語で挑むのがセオリーかと思いますが、自分の場合はJS力の底上げのためという名目で競プロを始めたので JavaScript を選択しました。

競プロやるには世知辛い言語ですが、少なからずJSで挑んでいる人も居るようなので知見を共有しておきます。

全て執筆時の情報なので、今後の言語アップデートなどで変化していく可能性あり.
（2019年9月時点）

標準入力の受け取り

"use strict";

const main = arg => {
  
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));  

この例だと arg という引数に標準入力が文字列で入ってきます。
後は自分の好みで加工したり変数に入れたりしていきます。

具体例

N K
A1 A2 A3 A4

よくある上のような入力を受け取る例

全部整数で受けとりたいという仮定で行きます。

"use strict";

const main = arg => {
  const input = arg.trim().split("\n");

  const N = parseInt(input[0].split(" ")[0]);
  const K = parseInt(input[0].split(" ")[1]);
  const A = input[1].split(" ").map(n=>parseInt(n));
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));  

自分はこんな感じでやっています。
ここら辺は好みなのであくまで一例です。

標準入力は全て文字列で渡されます。
JSは型が無いので、型の変換が必要な場合はうっかり忘れないように気を付ける。

trim() 関数については後ほど説明します。

ES6などのモダンな記法を使うには

言語アップデートで多分意識しなくても良くなったので修正済み

普通に const などの宣言を使うと、ランタイムエラーになってしまいます。
これを解決するためには、先頭に"use strict";を宣言してください。

標準入力からの受け取りに一度 trim() をかけよう

"use strict";
    
const main = arg => {
    const input = arg.trim().split("\n");
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

他のJS使いの方に教えてもらった知見です。
標準入力の末尾などに不要な空白などが入っているときが稀にあります。

その場合に配列操作を行ったときに思わぬ挙動をすることがあるので念のため trim() を掛けることを強く推奨します。

trim() は空白を削除してくれる関数です。

具体例 (ABC123-A)

trim()無
https://atcoder.jp/contests/abc123/submissions/4883475

trim()有
https://atcoder.jp/contests/abc123/submissions/4889820

ちなみにこれでハマってABCで1回0完したことがあります

整数の最大値が普通の言語より小さいことに超気をつける

MAX_SAFE_INTEGER // 9007199254740991

JavaScriptの整数型はだいたい10の16乗くらいから計算に誤差が生まれ結果がおかしくなってきます。

問題の制約を見て、10の9乗が登場し、さらに掛け算や大きめの足し算が出てきてオーバーフローする問題が稀によくあります。

解決策としては、BigIntを使うしかなさそうです。

// BigIntで宣言するか、数値に「n」を付ける
const N = BigInt(input[0])

const sum = 0n

・素直に別言語を使う
・Biginterger.jsを使う

~~多分こんなもんだと思います。 ~~
Biginterger.jsは大きい整数を扱うためのライブラリです。babelなどでコンパイルして使うか、インラインに直接埋め込む方法があります。

ちなみ自分は直接埋め込んでいます。
結構辛いです。

具体例(ABC139-D)

注意点：最後に出力するときにtoString()を掛けないとWAになります

これに関してはそろそろ言語アップデートが来るはずなので、そしたら解決されると思います。

追記

ABC163からNode.jsのバージョンがアップデートされ、BigIntが使えるようになりました。
ただし、過去問に関しては2020年4月現在、引き続き使えません。

一行ずつ答えを出力する問題の注意点

Yes
No
No
Yes

こんな感じで、1行ずつ改行しながら答えを出力する必要があるとき

for(let i=0; i<N; i++) {
  if(hoge) {
    console.log("Yes");
  } else {
    console.log("No");
  }
} 

ループの中で毎回 console.log を使うと遅いので問題によってはTLEになることがあります。

let answer = [];

for(let i=0; i<N; i++) {
  if(hoge) {
    answer.push("Yes");
  } else {
    answer.push("No");
  }
} 

console.log(answer.join("\n"));

こんな感じで、一度配列にpushしていってから最後にまとめて改行しながらjoinなどが良いと思います。

具体例 (ChokudaiSpeerrun02-B)

遅い例
https://atcoder.jp/contests/chokudai_S002/submissions/5884791

速い例
https://atcoder.jp/contests/chokudai_S002/submissions/7676761

ループの回し方の注意

for(let i in someArray) {
}

は遅いのでA,B問題以外では気をつけた方が良いです。

特にこれで2重ループを作ると配列のサイズ次第では劇的に遅くなってTLEすることがあります。

具体例 (三井住友信託銀行プログラミングコンテスト2019-D)

遅い例
https://atcoder.jp/contests/sumitrust2019/submissions/8772466

速い例
https://atcoder.jp/contests/sumitrust2019/submissions/8772442

Math.max(...Array) / Math.min(...Array)に関する注意

Math.maxやMath.minは配列にも適用する事が出来て、とっても便利です。

const array = [1, 3, 5, 10, -1];

cosnole.log(Math.max(...array)); // 10

ですが、罠があります。
配列のサイズが巨大になってくると（35536個とかだったと思う）、エラーを吐いてREになります。

なのでデカい配列に対して、最大や最小を取りたい時は一度sortして先頭を取り出したり、reduceを使うなりしないといけません。

const array = [1, 3, 5, 10, -1];

console.log(array.sort((a, b)=> b - a)[0]); // 10
console.log(array.reduce((m, n) => m > n ? m : n)); // 10

まとめ

やはりBigIntを使う場合だと、ただでさえ競プロの問題そのもので頭がこんがらがっている時に
さらに混乱させられたり思わぬWAが出たりするので、JSでやるのはあまりオススメできないなと思いました。

あと二分探索やQueueなどの標準ライブラリもPythonなどより貧弱なのは否めないですね。
自分でライブラリを作成しておくしかないです。

この記事は、これからまた新たに何か気付いたら追記していく予定です。