TypeScriptに慣れるために競技プログラミングの問題解いてみた

#AtCoder

#TypeScript

今泉大樹

2022.08.17

この記事は公開されてから1年以上経過しています。情報が古い可能性がありますので、ご注意ください。

こんにちは、AWS事業本部コンサルティング部に所属している今泉(@bun76235104)です。

JavaScriptは結構やってきたけど、思えばTypeScriptはちゃんと勉強できてなかったかもしれない・・・そんなこと思ったことありませんか？

私です。

私は新しい言語を学習する時に、簡単なチュートリアルをやったのち、競技プログラミングの簡単な問題を解くことで言語の仕様に慣れることが多いです。

以下の様なプログラミングにおける基本的な処理を利用して問題を楽しく解けるためです。

標準的な型: string,int,array,dict(object)などを取り扱う
- 言語特有の型の違いなど(intの取り扱うサイズなど)
if, for, whileなどの制御構文を取り扱う
map, filter, reduceなどの高階関数を取り扱える

TypeScript自体は扱ったことはあるのですが、言語の基本的な部分を見直すために今回TypeScriptでもやってみました!!

チュートリアルをやってみた

こちらのTypeScript Tutorial(英語)をやってみました。

TypeScriptとは何か？というところを最初に確認しました。

What is TypeScript?に以下のような特徴が記載されています。

TypeScriptはJavaScriptのスーパーセット(上位集合)
- TypeScriptはJavaScriptを包含していて、既存のJavaScriptコードがあれば動作させることができる
TypeScriptをコンパイルしてJavaScriptを作成する
.ts という拡張子を使う
型を利用できるようにするため、JavaScriptだと動かすまで気づけなかったバグに素早く気づくことができる
TypeScriptは主要ブラウザのJavaScriptエンジンより早く、ECMAScriptの新機能をサポートする

また,TypeScript Setupに従って実行環境をローカルに立てました。

あとは、順序に沿って一通り特徴を確認しました。

エディターのTypeScript用補完設定

私は普段はnvimとvim-lsp(vim-lsp-settings)を利用しているので、以下のように設定を追記しています

let g:lsp_settings_filetype_typescript = ['typescript-language-server', 'eslint-language-server', 'deno']

VS Codeを利用されている方はチュートリアルに必要な拡張機能の設定などが記載されていますので、ご確認ください。

AtCoderで練習してみる

AtCoderという競技プログラミングサービスです。

さまざまな言語で競技プログラミングを楽しむことができます。

TypeScriptに慣れるために問題を解いてみました。

AtCoderとは何か・AtCoderに参加するために何をすれば良いか分からない方は是非こちらの神記事をご参照ください。

また、AtCoderでは標準入力から必要なパラメーターが与えられることが多いので、標準入出力の使い方については先人の記事を参考にいたしました

標準的な型・処理を練習する問題

A- Welocom to AtCoder

問題はこちらです。

標準入出力と、プリミティブな型の扱いが分かれば簡単に回答できる問題です。

以下のようにして正解となりました。

import { readFileSync } from "fs";

const input: string[] = readFileSync("/dev/stdin", "utf8").split("\n");
const a: number = parseInt(input[0]);
const [b, c]: number[] = Array.from(input[1].split(" "), Number);
const s: string = input[2];

const ans: number = a + b + c;
console.log(ans);
console.log(s);

整数値にするのに praseIntを利用するのかNumberを利用するのか迷いを感じますね。(戒め)

ABC086A - Product

こちらの問題はif文の練習ができます。

import { readFileSync } from "fs";

const input: string[] = readFileSync("/dev/stdin", "utf8").split("\n");
const [a, b]: number[] = Array.from(input[0].split(" "), Number);

const mul: number = a * b;
let ans: "Even" | "Odd" = "Even";
if (mul % 2 !== 0) {
  ans = "Odd";
}
console.log(ans);

今回は文字列リテラルを使ってみました。(7行目)

文字列リテラルについてはこちらをご参照ください。

繰り返し処理・高階関数の練習をする問題

ABC081B - Shift only

これまでのA問題とは違い、B問題と呼ばれる問題になりました。

B問題では if for while などの処理が当たり前にできることが前提となっている問題が多く出題されます。

この問題では配列処理の練習にちょうど良いため、高階関数の reduce や map 処理を利用しています。

また、関数の書き方に慣れるためにも countEventNums という関数を作ってみました。

import { readFileSync } from "fs";

const input: string[] = readFileSync("/dev/stdin", "utf8").split("\n");
const N = Number(input[0]);
const A: number[] = Array.from(input[1].split(" "), Number);

function countEvenNums(L: number[]): number {
  const count: number = L.reduce((total: number, cur: number): number => {
    if (cur % 2 === 0) return total + 1;
    return total;
  }, 0);
  return count;
}

let ans = 0;

let numbers: number[] = A.slice(0, N);
while (countEvenNums(numbers) === N) {
  numbers = numbers.map((n: number): number => n / 2);
  ans++;
}
console.log(ans);

ABC087B - Coins

実務ではネストが深い処理はイマイチですが、一応多重forループの学習もしてみました。

import { readFileSync } from "fs";

const input: string[] = readFileSync("/dev/stdin", "utf8").split("\n");
const A = Number(input[0]);
const B = Number(input[1]);
const C = Number(input[2]);
const X = Number(input[3]);

let ans = 0;

// aを500円玉の数、bを100円玉の数、cを50円玉の数とする
for (let a = 0; a <= A; a++) {
  for (let b = 0; b <= B; b++) {
    for (let c = 0; c <= C; c++) {
      const sum = (500 * a) + (100 * b) + (50 * c);
      if (sum === X) ans++;
    }
  }
}

console.log(ans);

ABC088B - Card Game for Two

ソート処理も目を通しておきます。

sortってメソッドを呼び出すだけなんじゃないの？

という感じですが、その言語が提供している標準のsort関数でどのようなアルゴリズムが使われているかは確認しておきます。

どのようなアルゴリズムが使われているかによって、処理にかかる時間が全く異なるためです。

例えばPythonだと Timsortと呼ばれるアルゴリズムが利用されていて、高速に処理できます。

Node.jsでも利用しているv8の公式ページを見てみると、Timsort を利用している様ですね。

ということで、こちらもそのまま利用させていただければよさそうです。

import { readFileSync } from "fs";

const input: string[] = readFileSync("/dev/stdin", "utf8").split("\n");
const N = Number(input[0]);
const A: number[] = Array.from(input[1].split(" "), Number);

// 降順(ポイントが高い順)にソート
const sorted: number[] = A.sort((a, b) => b - a);

let alicePoints = 0;
let bobPoints = 0;

for (const [i, v] of sorted.entries()) {
  if (i % 2 === 0) {
    alicePoints += v;
    continue;
  }
  bobPoints += v;
}

const ans = alicePoints - bobPoints;
console.log(ans);

【参考】

こちらの神記事では計算量について解説してくれており、例えば「Facebookユーザー数のような情報を取り扱うにはどのようなアルゴリズム利用が考えらえるか？」という情報を教えてくれます。

競プロをしなくても読み物として面白いと思いますので、是非ご一読ください。