TypeScriptでAtCoderをやってみよう!

皆さんこんにちは。[cosocaf](https://atcoder.jp/users/cosocaf)です。僕は普段C++を使っているのですが、気分転換をかねてTypeScriptでAtCoderをやってみたので備忘や後続の方のために記事を書きたいと思います。なぜTypeScriptを選んだのかといいますと、僕自身C++の次によく使う言語がこれであるためなのもあるのですが、C++、Rust、Pythonばっかのこの環境に対する反骨精神的なところもあります。

## 1. 準備
まずは、環境構築です。VSCodeでおこなうことを想定しています。もうコード書けるよって状態の方はとばしてください。
また、この章は記事の趣旨とずれているので簡易的な説明にとどめています。詳しい説明は別の方の記事を参考にしてください。

### Nodeをインストールする

#### Windowsの場合
[ここ](https://nodejs.org/ja/download/)からインストーラをダウンロードします。あとはインストーラの指示に従えば問題ありません。

#### Macの場合
[brew](https://brew.sh/index_ja)があるなら以下コマンドでインストールできます。

```terminal:コマンド
brew install node
```

試しにAtCoderの[コードテスト](https://atcoder.jp/contests/practice/custom_test)に以下のコードを投げたところ、2022/03/05現在AtCoderのNodeのバージョンは12.16.1のようです。

```ts:input
console.log(process.version);
```

```terminal:output
v12.16.1
```

コンソール上で以下のコマンドを打って、バージョンが表示されればインストール完了です。

```terminal:コマンド
node -v
```

```terminal:output
v14.18.1
```

Nodeを入れる時に一緒に入っていると思いますが、npmもインストールされているか一応確認しましょう。
コンソール上で以下のコマンドを打って、バージョンが表示されればnpmがインストールされています。

```terminal:コマンド
npm -v
```

```terminal:output
v8.5.0
```

### TypeScriptをインストールする
ここから先はソースコードを書くディレクトリでおこないます。
まずは、package.jsonを作成しましょう。[仕様](https://docs.npmjs.com/cli/v7/configuring-npm/package-json)をもとに手書きすることも可能ですが、以下のコマンドで簡単に作成できます。

```terminal:コマンド
npm init
```

いくつか質問をされるので、それに答えることでpackage.jsonが作成されます。

つぎに、以下のコマンドを打ち、TypeScriptをインストールします。

```terminal:コマンド
npm i -D typescript
```

インストールできたら以下のコマンドを打ち、tsconfig.jsonを作成します。

```terminal:コマンド
npx tsc --init
```

tsconfig.jsonが作成されればOKです。
デバッグ用にsourceMapオプションを、ビルド時間短縮用にincrementalオプションをそれぞれtrueにし、libオプションにesnextを追加し、targetオプションをes2020以上(esnextで可)にしましょう。

```json:tsconfig.json
{
  "compilerOptions": {
    "incremental": true,
    "target": "esnext",
    "lib": ["esnext"],
    "module": "commonjs",
    "sourceMap": true,
    "esModuleInterop": true,
    "forceConsistentCasingInFileNames": true,
    "strict": true,
    "skipLibCheck": true
  }
}
```

各オプションについては[この記事](https://qiita.com/ryokkkke/items/390647a7c26933940470)が詳しいです。

### @types/nodeをインストールする

tscはNodeの標準ライブラリを知らないので、それを教えてあげる必要があります。
以下のコマンドで標準ライブラリの型定義ファイルをインストールします。

```terminal:コマンド
npm i -D @types/node
```

### ソースファイルを作る
それではいよいよソースファイルを作ります。どのようなディレクトリ構成にするかは決まり事ではないので好きなように作りましょう。
一応僕がやったパターンを紹介します。srcディレクトリを作って、その中にindex.tsファイルを作成します。このままだと、出力ファイルもsrcに入ってしまうので、tsconfig.jsonでoutDirを./distに変更します。
ディレクトリ構成は以下の通りです。

```terminal:ディレクトリ構成
root/
  ├ node_modules/
  ├ dist/
  ├ src/
  │   └ index.ts
  ├ package.json
  └ tsconfig.json
```

ファイルができたら以下のようなコードを書いて実行できるかテストします。

```ts:index.ts
console.log("Hello, World");
```

そして、以下のコマンドでJSにトランスパイルします。

```terminal:コマンド
npx tsc -p <tsconfig.jsonへのパス> <ソースファイルへのパス>
```

無事にファイルが出力されたら実行してみましょう。

```terminal:コマンド
node <出力されたファイルへのパス>
```

```terminal:output
Hello, World
```

うまくいけばTypeScriptの設定は完璧です。

### VSCodeの設定

それではVSCodeでのデバッグ環境を構築します。

まずは、ビルドタスクを作成します。VSCode上で、Ctrl+Shift+P → Tasks: Configure Task → tsc: ビルド - tsconfig.jsonとすることでビルドタスクが作成されます。

つぎに画面左のデバッグタブを開き、launch.jsonを作成します。作成されたlaunch.jsonを開き、エディタ右下の構成の追加...ボタンを押してNode.js: Launch Programを選択します。そして、以下のように変更します。

```json-doc:launch.json
{
  // ...
  "program": "${workspaceFolder}/<出力されるファイルへのパス>",
  // ...
  "console": "integratedTerminal",
  "preLaunchTask": "<先ほど作成したビルドタスクのラベル名>"
}
```

では、index.tsに戻り、F5キーを押して実行できるか試してみましょう。
色々出力されたのち、以下のように出力されれば成功です。

```terminal:output
Debugger attached.
Hello, World  // ここはindex.tsに書いたconsolo.logによる
Waiting for the debugger to disconnect...
```

これで準備は完了です。
それでは実際にコードを書いていきましょう!

## 2. 標準入力

AtCoderに限らず、競技プログラミングのほとんどの問題は問題に応じた入力があります。
Nodeの標準入力はいくつか方法があるので紹介します。

いずれの方法でもコンソールからの入力の場合、Ctrl+Dで入力を終了できます。

### ```fs.readFileSync```で```/dev/stdin```を読み込む

Unix系で使える方法です。Windowsでは使えません。
AtCoderの[練習問題](https://atcoder.jp/contests/practice/tasks/practice_1)の解答例はこの方法です。

```ts:index.ts
import * as fs from "fs";

const inputs = fs.readFileSync("/dev/stdin", "utf8");
```

### ```fs.readFileSync```で```process.stdin.fd```を読み込む

Unix系でもWindowsでも使える方法です。
[リファレンス](https://nodejs.org/docs/latest-v12.x/api/process.html#process_process_stdin_fd)によると、process.stdin.fdは0固定っぽいので、代わりに0でもよさそうです。

```ts:index.ts
import * as fs from "fs";

const inputs = fs.readFileSync(process.stdin.fd, "utf8");
// あるいは
const inputs = fs.readFileSync(0, "utf8");
```

ただし、Windowsの場合標準入力をコマンドでパイプしないとクラッシュするので注意が必要です。
下の例では、外部ファイル(input.txt)に入力を書いています。

```terminal:Windowsのコマンドライン例
# command promptの場合
node ./dist/index.js < input.txt

# powershellの場合
cat input.txt | node ./dist/index.js
```

### ```readline```モジュールで```process.std```を読み込む

Unix系でもWindowsでも使える方法です。
Node標準ライブラリの[readlineモジュール](https://nodejs.org/api/readline.html)を使って行単位で読み込みます。
Windowsでコンソールから標準入力をしたい場合はこの方法になると思います。

```ts:index.ts
import * as readline from "readline";

const stream = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
let inputs = "";
stream.on("line", (line) => {
  inputs += line;
  inputs += "\n";
});
stream.on("close", () => {
  // ここで処理をする。
});
```

### 結局どれがいいの?

[AtCoderのコードテスト](https://atcoder.jp/contests/practice/custom_test)で試してみました。

コードテストの入力欄は512KiBが上限なので、以下のようなコードで入力を作成しました。

```ts:create_text.ts
import * as fs from "fs";

const createText = () => {
  let text = "";
  while (text.length < 512 * 1024) {
    text += "123 456\n";
  }
  return text;
};

fs.writeFile("./out.txt", createText(), () => console.log("done."));
```

それぞれの手法を10回計測し、平均をとりました。
初期化オーバーヘッドを考慮するために、何もしないパターンも計測します。
平均は小数点以下を四捨五入しています。
|      | /dev/stdin | process.stdin.fd | readline | 何もしない |
|:----:|:----------:|:----------------:|:--------:|:---------:|
| 1    | 51ms       | 53ms             | 100ms    | 55ms      |
| 2    | 53ms       | 56ms             | 99ms     | 52ms      |
| 3    | 51ms       | 55ms             | 95ms     | 49ms      |
| 4    | 52ms       | 52ms             | 103ms    | 51ms      |
| 5    | 55ms       | 55ms             | 95ms     | 51ms      |
| 6    | 57ms       | 48ms             | 99ms     | 56ms      |
| 7    | 52ms       | 55ms             | 103ms    | 56ms      |
| 8    | 52ms       | 56ms             | 100ms    | 52ms      |
| 9    | 51ms       | 55ms             | 95ms     | 55ms      |
| 10   | 55ms       | 52ms             | 92ms     | 48ms      |
| 平均 | 53ms       | 54ms             | 98ms     | 53ms      |

`/dev/stdin`と`process.stdin.fd`に速度面での違いはほぼなさそうですね。それに対して`readline`はかなり時間がかかるようです。何もしないパターンでも`/dev/stdin`と`process.stdin.fd`とほぼ同じ時間がかかることから、標準入力を受け取ること自体にはあまりコストがかからないことがわかります。

## 3. 標準入力の加工

前章では標準入力を受け取る方法を説明しました。このままでは単一の文字列でしかないので、これを加工して利用できる形にします。

### 項目ごとに分割する

分割には```String.prototype.split```を使います。引数に入れたパターンで分割する関数です。詳しい仕様は[mozillaのリファレンス](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/String/split)を参照してください。

```ts:index.ts
const inputArray = inputs.split(/\s/);
```

### 配列から取り出す

入力の各項目はinputArrayに入っています。それを前から取り出していく関数を作ります。

```ts:index.ts
let currentIndex = 0;
function next() {
  return inputArray[currentIndex++];
}
```

```ts:使い方
const S = next();
```

### 型変換する

各項目はすべて文字列として保持されています。これを必要に応じて数字などに変換できるようにしましょう。

#### Number型

文字列を数字に変換する方法はたくさんあります。

```ts:string to number
const str = "100";

const a = parseInt(str);    // 小数点以下は失われる
const b = parseFloat(str);  // 小数点以下を保持
const c = Number(str);
const e = +str;
const f = -(-str);
const g = ~~str;
// ほかにもstr|0やstr>>0などもあるが、TypeScriptのトランスパイラに怒られる。
```

どれが最も高速か計測してみました。
以下のコードでランダムな数字列を生成し、処理時間を計測します。

```ts:index.ts
const N = 10000000; // 10^7

// ランダムな長さの数字で構成される文字列をN個生成する。
const array = [];
for (let i = 0; i < N; ++i) {
  const length = Math.random() * 10 + 1;
  const code = [];
  for (let j = 0; j < length; ++j) {
    code[j] = "0".charCodeAt(0) + Math.random() * 10;
  }
  array[i] = String.fromCharCode(...code);
}

const begin = Date.now();
for (const item of array) {
  const num = parseInt(item);
}
const end = Date.now();

console.log(`${end - begin}ms`);
```

それぞれ10回計測し、平均をとりました。平均は小数点以下四捨五入です。

|    | parseInt | parseFloat | Number  | +item   | -(-item)| ~~item |
|:--:|:--------:|:----------:|:-------:|:-------:|:-------:|:------:|
| 1  | 813ms    | 696ms      | 694ms   | 686ms   | 732ms   | 755ms  |
| 2  | 816ms    | 700ms      | 691ms   | 699ms   | 726ms   | 752ms  |
| 3  | 812ms    | 700ms      | 696ms   | 691ms   | 730ms   | 769ms  |
| 4  | 800ms    | 691ms      | 699ms   | 694ms   | 716ms   | 744ms  |
| 5  | 805ms    | 693ms      | 699ms   | 707ms   | 728ms   | 746ms  |
| 6  | 812ms    | 691ms      | 689ms   | 691ms   | 728ms   | 769ms  |
| 7  | 810ms    | 698ms      | 701ms   | 700ms   | 721ms   | 753ms  |
| 8  | 818ms    | 689ms      | 704ms   | 704ms   | 726ms   | 752ms  |
| 9  | 825ms    | 689ms      | 703ms   | 695ms   | 728ms   | 762ms  |
| 10 | 819ms    | 702ms      | 695ms   | 697ms   | 724ms   | 743ms  |
|平均| 813ms    | 695ms      | 697ms   | 696ms   | 726ms   | 755ms  |

```parseFloat```、```Number```、```+item```が最も高速なようです。```parseInt```は基数変換ができるぶん低速なのでしょうかね。

これをふまえて数字用の関数を作成しましょう。

```ts:index.ts
function nextNum() {
  return +next(); // parseFloat(next()), Number(next())でもよい
}
```

```ts:使い方
const N = nextNum();
```

#### BitInt型

JavaScriptのnumber型は2^53(≒9*10^15)以上の数を正確に表すことができません。AtCoderでは通常10^18までの整数が登場するのでnumber型では表現できない値を扱う必要があります。そこで使用するのがBigInt型です。

BigIntについての詳しい仕様は[mozillaのリファレンス](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/BigInt)を参照してください。

BigInt用の関数はこのようになります。

```ts:index.ts
function nextBigInt() {
  return BigInt(next());
}
```

```ts:使い方
const N = nextBigInt();
```

#### 配列

AtCoderの問題は、「長さNの数列A」などの形で配列を用いることがあります。

```ts:index.ts
const N = nextNum();
const A = [];
for(let i = 0; i < N; ++i) A[i] = nextNum();
```

毎回上記のように記述してもよいのですが、定型文なのでこれも関数化しましょう。

```ts:index.ts
function nextNums(length: number) {
  const arr = [];
  for(let i = 0; i < length; ++i) arr[i] = nextNum();
  return arr;
}
```

```ts:使い方
const N = nextNum();
const A = nextNums(N);
```

少し特殊な使い方ですが、[分割代入](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Operators/Destructuring_assignment)を使って以下のように入力を受け取ることもできます。

```ts:分割代入
// これを
const N = nextNum();
const M = nextNum();

// このように記述できる
const [N, M] = nextNums(2);
```

## 4. 標準出力

問題を解いたら答えを標準出力に出力する必要があります。Nodeの場合は```console.log```が標準出力になります。ただし、```console.log```は低速なので工夫が必要です。

例えば[ABC 241 - D](https://atcoder.jp/contests/abc241/tasks/abc241_d)のような複数行出力する問題で、愚直に```console.log```を使うとTLEしてしまいます。これを防ぐ方法は簡単です。事前に出力内容をバッファにためて、最後に一度に出力すれば高速に動作します。

```ts:愚直にconsole.logをするパターン
const N = nextNum();  // 大抵10^5から10^7ぐらい
const ans = []; // 答えを配列で管理しているとする。

// ごにょごにょ

for(let i = 0; i < N; ++i) {
  console.log(ans[i]);
}
```

```ts:バッファにためるパターン
// ... 省略
let buffer = "";
for(let i = 0; i < N; ++i) {
  buffer += ans[i];
  buffer += "\n";
}
console.log(buffer);
```

ただ、毎回バッファを作って+=して...というのは記述量が増えるうえ、修正が面倒なので関数化しましょう。

```ts:index.ts
let outputBuffer = "";
function print(out: string | number | bigint) {
  outputBuffer += out;
}
function println(out: string | number | bigint) {
  print(out);
  print("\n");
}
function flush() {
  console.log(outputBuffer);
}
```

```ts:使い方
// ... 省略
for(let i = 0; i < N; ++i) {
  println(ans[i]);
}
flush();
```

また、AtCoderは問題によって改行区切りで出力したり、スペース区切りで出力したりしますが、そのあたりをいい感じに出力してくれるような関数をつくっておくと後々楽かもしれません。
下の例は先ほど作成したprint関数とprintln関数をオーバーロードするアプローチです。

```ts:output-array.ts
function print(out: string | number | bigint): void;
function print<T>(out: Array<T>, separator: string): void;
function print<T>(out: string | number | bigint | Array<T>, separator?: string) {
  if(Array.isArray(out)) {
    outputBuffer += out.join(separator);
  } else {
    outputBuffer += out;
  }
}

function println(out: string | number | bigint): void;
function println<T>(out: Array<T>, separator: string): void;
function println<T>(out: string | number | bigint | Array<T>, separator?: string) {
  if(Array.isArray(out)) {
    print(out, separator || "");
  } else {
    print(out);
  }
  print("\n");
}
```

## 5. ソースコードのテンプレート

以上のことをふまえて問題を解くときのテンプレートを作成します。

```ts:index.ts
import { createInterface } from "readline";
import * as fs from "fs";

let inputs = "";
let inputArray: string[];
let currentIndex = 0;

let outputBuffer = "";

function next() {
  return inputArray[currentIndex++];
}
function nextNum() {
  return +next();
}
function nextBigInt() {
  return BigInt(next());
}
function nexts(length: number) {
  const arr = [];
  for(let i = 0; i < length; ++i) arr[i] = next();
  return arr;
}
function nextNums(length: number) {
  const arr = [];
  for(let i = 0; i < length; ++i) arr[i] = nextNum();
  return arr;
}
function nextBigInts(length: number) {
  const arr = [];
  for(let i = 0; i < length; ++i) arr[i] = nextBigInt();
  return arr;
}

function print(out: string | number | bigint): void;
function print<T>(out: Array<T>, separator: string): void;
function print<T>(out: string | number | bigint | Array<T>, separator?: string) {
  if (Array.isArray(out)) {
    outputBuffer += out.join(separator);
  } else {
    outputBuffer += out;
  }
}

function println(out: string | number | bigint): void;
function println<T>(out: Array<T>, separator: string): void;
function println<T>(out: string | number | bigint | Array<T>, separator?: string) {
  if (Array.isArray(out)) {
    print(out, separator || "");
  } else {
    print(out);
  }
  print("\n");
}

function flush() {
  console.log(outputBuffer);
}

// デバッグ環境がWindowsであれば条件分岐する
if (process.env.OS == "Windows_NT") {
  const stream = createInterface({
    input: process.stdin,
    output: process.stdout,
  });
  stream.on("line", (line) => {
    inputs += line;
    inputs += "\n";
  });
  stream.on("close", () => {
    inputArray = inputs.split(/\s/);
    main();
    flush();
  });
} else {
  inputs = fs.readFileSync("/dev/stdin", "utf8");
  inputArray = inputs.split(/\s/);
  main();
  flush();
}

function main() {
  // ここに処理を記述していく。
}
```

問題ごとにmain関数の中を書き換えます。

試しに[ABS PracticeA - Welcome to AtCoder](https://atcoder.jp/contests/abs/tasks/practice_1)を解いてみます。
[解答](https://atcoder.jp/contests/abs/submissions/29945001)

```ts:index.ts
function main() {
  const [a, b, c] = nextNums(3);
  const s = next();
  println(`${a + b + c} ${s}`);
}
```

## さいごに
AtCoderをTypeScriptでやるうえでの最低限の実装をしてみました。
この記事を通して競プロのTypeScript人口が増えてくれればうれしいです。

何か質問、修正などありましたら気軽にコメントしてください。