皆さんこんにちは。cosocafです。僕は普段C++を使っているのですが、気分転換をかねてTypeScriptでAtCoderをやってみたので備忘や後続の方のために記事を書きたいと思います。なぜTypeScriptを選んだのかといいますと、僕自身C++の次によく使う言語がこれであるためなのもあるのですが、C++、Rust、Pythonばっかのこの環境に対する反骨精神的なところもあります。
1. 準備
まずは、環境構築です。VSCodeでおこなうことを想定しています。もうコード書けるよって状態の方はとばしてください。
また、この章は記事の趣旨とずれているので簡易的な説明にとどめています。詳しい説明は別の方の記事を参考にしてください。
Nodeをインストールする
Windowsの場合
ここからインストーラをダウンロードします。あとはインストーラの指示に従えば問題ありません。
Macの場合
brewがあるなら以下コマンドでインストールできます。
brew install node
試しにAtCoderのコードテストに以下のコードを投げたところ、2022/03/05現在AtCoderのNodeのバージョンは12.16.1のようです。
console.log(process.version);
v12.16.1
コンソール上で以下のコマンドを打って、バージョンが表示されればインストール完了です。
node -v
v14.18.1
Nodeを入れる時に一緒に入っていると思いますが、npmもインストールされているか一応確認しましょう。
コンソール上で以下のコマンドを打って、バージョンが表示されればnpmがインストールされています。
npm -v
v8.5.0
TypeScriptをインストールする
ここから先はソースコードを書くディレクトリでおこないます。
まずは、package.jsonを作成しましょう。仕様をもとに手書きすることも可能ですが、以下のコマンドで簡単に作成できます。
npm init
いくつか質問をされるので、それに答えることでpackage.jsonが作成されます。
つぎに、以下のコマンドを打ち、TypeScriptをインストールします。
npm i -D typescript
インストールできたら以下のコマンドを打ち、tsconfig.jsonを作成します。
npx tsc --init
tsconfig.jsonが作成されればOKです。
デバッグ用にsourceMapオプションを、ビルド時間短縮用にincrementalオプションをそれぞれtrueにし、libオプションにesnextを追加し、targetオプションをes2020以上(esnextで可)にしましょう。
{
"compilerOptions": {
"incremental": true,
"target": "esnext",
"lib": ["esnext"],
"module": "commonjs",
"sourceMap": true,
"esModuleInterop": true,
"forceConsistentCasingInFileNames": true,
"strict": true,
"skipLibCheck": true
}
}
各オプションについてはこの記事が詳しいです。
@types/nodeをインストールする
tscはNodeの標準ライブラリを知らないので、それを教えてあげる必要があります。
以下のコマンドで標準ライブラリの型定義ファイルをインストールします。
npm i -D @types/node
ソースファイルを作る
それではいよいよソースファイルを作ります。どのようなディレクトリ構成にするかは決まり事ではないので好きなように作りましょう。
一応僕がやったパターンを紹介します。srcディレクトリを作って、その中にindex.tsファイルを作成します。このままだと、出力ファイルもsrcに入ってしまうので、tsconfig.jsonでoutDirを./distに変更します。
ディレクトリ構成は以下の通りです。
root/
├ node_modules/
├ dist/
├ src/
│ └ index.ts
├ package.json
└ tsconfig.json
ファイルができたら以下のようなコードを書いて実行できるかテストします。
console.log("Hello, World");
そして、以下のコマンドでJSにトランスパイルします。
npx tsc -p <tsconfig.jsonへのパス> <ソースファイルへのパス>
無事にファイルが出力されたら実行してみましょう。
node <出力されたファイルへのパス>
Hello, World
うまくいけばTypeScriptの設定は完璧です。
VSCodeの設定
それではVSCodeでのデバッグ環境を構築します。
まずは、ビルドタスクを作成します。VSCode上で、Ctrl+Shift+P → Tasks: Configure Task → tsc: ビルド - tsconfig.jsonとすることでビルドタスクが作成されます。
つぎに画面左のデバッグタブを開き、launch.jsonを作成します。作成されたlaunch.jsonを開き、エディタ右下の構成の追加...ボタンを押してNode.js: Launch Programを選択します。そして、以下のように変更します。
{
// ...
"program": "${workspaceFolder}/<出力されるファイルへのパス>",
// ...
"console": "integratedTerminal",
"preLaunchTask": "<先ほど作成したビルドタスクのラベル名>"
}
では、index.tsに戻り、F5キーを押して実行できるか試してみましょう。
色々出力されたのち、以下のように出力されれば成功です。
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の練習問題の解答例はこの方法です。
import * as fs from "fs";
const inputs = fs.readFileSync("/dev/stdin", "utf8");
fs.readFileSyncでprocess.stdin.fdを読み込む
Unix系でもWindowsでも使える方法です。
リファレンスによると、process.stdin.fdは0固定っぽいので、代わりに0でもよさそうです。
import * as fs from "fs";
const inputs = fs.readFileSync(process.stdin.fd, "utf8");
// あるいは
const inputs = fs.readFileSync(0, "utf8");
ただし、Windowsの場合標準入力をコマンドでパイプしないとクラッシュするので注意が必要です。
下の例では、外部ファイル(input.txt)に入力を書いています。
# command promptの場合
node ./dist/index.js < input.txt
# powershellの場合
cat input.txt | node ./dist/index.js
readlineモジュールでprocess.stdを読み込む
Unix系でもWindowsでも使える方法です。
Node標準ライブラリのreadlineモジュールを使って行単位で読み込みます。
Windowsでコンソールから標準入力をしたい場合はこの方法になると思います。
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のコードテストで試してみました。
コードテストの入力欄は512KiBが上限なので、以下のようなコードで入力を作成しました。
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のリファレンスを参照してください。
const inputArray = inputs.split(/\s/);
配列から取り出す
入力の各項目はinputArrayに入っています。それを前から取り出していく関数を作ります。
let currentIndex = 0;
function next() {
return inputArray[currentIndex++];
}
const S = next();
型変換する
各項目はすべて文字列として保持されています。これを必要に応じて数字などに変換できるようにしましょう。
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のトランスパイラに怒られる。
どれが最も高速か計測してみました。
以下のコードでランダムな数字列を生成し、処理時間を計測します。
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は基数変換ができるぶん低速なのでしょうかね。
これをふまえて数字用の関数を作成しましょう。
function nextNum() {
return +next(); // parseFloat(next()), Number(next())でもよい
}
const N = nextNum();
BitInt型
JavaScriptのnumber型は2^53(≒9*10^15)以上の数を正確に表すことができません。AtCoderでは通常10^18までの整数が登場するのでnumber型では表現できない値を扱う必要があります。そこで使用するのがBigInt型です。
BigIntについての詳しい仕様はmozillaのリファレンスを参照してください。
BigInt用の関数はこのようになります。
function nextBigInt() {
return BigInt(next());
}
const N = nextBigInt();
配列
AtCoderの問題は、「長さNの数列A」などの形で配列を用いることがあります。
const N = nextNum();
const A = [];
for(let i = 0; i < N; ++i) A[i] = nextNum();
毎回上記のように記述してもよいのですが、定型文なのでこれも関数化しましょう。
function nextNums(length: number) {
const arr = [];
for(let i = 0; i < length; ++i) arr[i] = nextNum();
return arr;
}
const N = nextNum();
const A = nextNums(N);
少し特殊な使い方ですが、分割代入を使って以下のように入力を受け取ることもできます。
// これを
const N = nextNum();
const M = nextNum();
// このように記述できる
const [N, M] = nextNums(2);
4. 標準出力
問題を解いたら答えを標準出力に出力する必要があります。Nodeの場合はconsole.logが標準出力になります。ただし、console.logは低速なので工夫が必要です。
例えばABC 241 - Dのような複数行出力する問題で、愚直にconsole.logを使うとTLEしてしまいます。これを防ぐ方法は簡単です。事前に出力内容をバッファにためて、最後に一度に出力すれば高速に動作します。
const N = nextNum(); // 大抵10^5から10^7ぐらい
const ans = []; // 答えを配列で管理しているとする。
// ごにょごにょ
for(let i = 0; i < N; ++i) {
console.log(ans[i]);
}
// ... 省略
let buffer = "";
for(let i = 0; i < N; ++i) {
buffer += ans[i];
buffer += "\n";
}
console.log(buffer);
ただ、毎回バッファを作って+=して...というのは記述量が増えるうえ、修正が面倒なので関数化しましょう。
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);
}
// ... 省略
for(let i = 0; i < N; ++i) {
println(ans[i]);
}
flush();
また、AtCoderは問題によって改行区切りで出力したり、スペース区切りで出力したりしますが、そのあたりをいい感じに出力してくれるような関数をつくっておくと後々楽かもしれません。
下の例は先ほど作成したprint関数とprintln関数をオーバーロードするアプローチです。
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. ソースコードのテンプレート
以上のことをふまえて問題を解くときのテンプレートを作成します。
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を解いてみます。
解答
function main() {
const [a, b, c] = nextNums(3);
const s = next();
println(`${a + b + c} ${s}`);
}
さいごに
AtCoderをTypeScriptでやるうえでの最低限の実装をしてみました。
この記事を通して競プロのTypeScript人口が増えてくれればうれしいです。
何か質問、修正などありましたら気軽にコメントしてください。