JavaScriptで競技プログラミングを始めよう！

JavaScript

これは，Competitive Programming Advent Calendar Div2012の17日目の記事です．

はじめに

競技プログラミングといえばC++, Javaなどの言語を使う人が圧倒的に多かったのですが、最近は会津オンラインジャッジやAtCoderなどでC#, D言語, Ruby, Python, PHPなども使えるようになり,軽量プログラミング言語(Lightweight Language,LL)で競技プログラミングできるようになりつつあります。LLのなかでも特にRubyやPythonを使う人は多い印象を受けますが, JavaScriptを使う人は少ない印象が私にはあったので少しでもJavaScriptで競技プログラミングする人が増えればいいな、と考えこの記事を書くことになりました。

この記事ではAtCoderにおいてJavaScriptを使うことと競技プログラミングの初歩的は知識はあるという前提で書かれています。

よく使う処理やデータ構造など

変数の宣言
変数の宣言をするときはvarを使います。varを省略してもプログラムは動きますが、できるだけ書いたほうがよいです。(varを省略した場合は必ずグローバル変数となる)

// 整数 (Numberオブジェクト)
var x = 0;
// 浮動小数 (Numberオブジェクト)
var pi = 3.14;
// 文字列 (Stringオブジェクト)
var str = "Hello!";
// 真偽値 (Booleanオブジェクト)
var flag = true;
// 配列 (Arrayオブジェクト)
var a = [1, 2, 3];
var b = new Array(3); // サイズ3の配列を宣言

数値(Numberオブジェクト)は整数も小数もどちらもNumberオブジェクトなので計算の途中で整数と小数の計算を行うと思わぬ数値になる可能性がありバグの原因になるので注意が必要です。

条件分岐 (if文)

if ( /* 条件式 */ ) {
    /* 条件式がtrueのとき */
} else {
    /* 条件式がfalseのとき */
}

if文はC++やJavaとほとんど変わらないので特に問題なく使えるでしょう。

繰り返し処理 (for文, while文)

for ( /* 初期化処理 */ ; /* 条件式 */ ; /* ループ変数の更新 */ ) {
    /* 条件式がtrueの間繰り返し処理 */
}
// x が 0 以上の間ループする
while ( /* 条件式 */ ) {
    /* 条件式がtrueの間繰り返し処理 */
}

// 例
var x = 0;
// 10 回ループ
for (var i=0 ; i < 10 ; i++ ) {
    x += i * i;
}

for文やwhile文も特にC++やJavaとほとんど変わらないので特に問題なく使えるでしょう。

関数 (function)

function 関数名( 引数の並び ) {
    /* 処理 */
}

// 例 (引数xの二乗を返す関数)
function f(x) {
    return x * x;
}

JavaScriptの関数ではC++やJavaと違い関数の戻り値の型を明示的に書くことはできないので関数呼び出しをするときは気をつける必要があります。またJavaScriptではfunctionもオブジェクトなので関数を引数に取る関数(高階関数)も使えます。例えば

という計算をしたいときは以下のようなコードを書くとよいです。

function sigma(a, b, f) {
    var sum = 0;
    for (var k = a ; k <= b ; k++ ) {
        sum += f(k);
    }
    return sum;
}
function f(x) {
    return x * x;
}
function g(x) {
    return 2 * x;
}

function Main() {
    sigma(1, 3, f); // => 14 (1 + 4 + 9)
    sigma(1, 3, g); // => 12 (2 + 4 + 6)
}

変数のスコープ
JavaScriptで苦労することのひとつに変数のスコープがあります。JavaScriptの変数はグローバル変数と関数内のローカルな変数の2つしかありません。なのでC++やJavaと同じような感覚でコードを書いているとfor文などで使ったループ変数が衝突して思わぬバグが発生することがあります。

var a = 0;
function f(){
    var x = 0;
    for(var i=0 ; i < 10 ; i++ ){
      // 処理
    }
    // ここでも変数 i は参照できる
}
// ここでは変数xやiは参照できない. 変数aは参照できる

コメント文
コメント文はC++やJavaと同じです。

// 1行コメント
/* 複数行コメント */

配列 (Arrayオブジェクト)
配列は単に配列としてでなく先頭や末尾に要素を追加したり取り除いたりできるのでスタックやキューとして使うこともできます。

// 配列の宣言
var a = [1, 2, 3];
var b = new Array(3); // サイズ3の配列を宣言
var c = new Array(3, 4, 5, 6, 7); // => [3, 4, 5, 6, 7]
var d = []; // => 空の配列
var e = new Array(); // => 空の配列

// 配列の要素数を取得
a.length; // => 3

// 2次元配列をつくる (配列の各要素に配列を入れていく感じ)
var x = new Array(5);
for(var i=0 ; i < x.length ; i++ ){
    x[i] = new Array(3);
}


// 配列の連結 (配列自体は変更されません)
a.concat(4, 5); // => [1, 2, 3, 4, 5]
a.concat([4, 5]) // => [1, 2, 3, 4, 5];
a.concat([4, 5], [6, 7]); // => [1, 2, 3, 4, 5, 6, 7]
// 配列を連結した文字列を返す (デフォルトはカンマ区切り, 引数を渡すとその文字列を区切りに連結した文字列を返す)
a.join(); // => "1,2,3"
a.join(":"); // => "1:2:3"
a.join(""); // => "123"

// 配列の末尾に要素を追加して、追加された後の配列のサイズを返す
a.push(7); // => 4 (a = [1, 2, 3, 7])
// 配列の末尾の要素を取り除きその値を返す (配列が空のときはundefinedを返す)
a.pop(); // => 7 (a = [1, 2, 3])
// 配列の先頭に要素を追加し、追加された後の配列のサイズを返す
a.unshift(10); // => 4 (a = [10, 1, 2, 3])
// 配列の先頭の要素を取り除きその値を返す (配列が空のときはundefinedを返す)
a.shift(); // => 10 (a = [1, 2, 3])

// 逆順にする (戻り値は配列への参照で、配列自体が変更される)
a.reverse(); // => [3, 2, 1]
// ソートする (戻り値は配列への参照で、配列自体が変更される)
// 文字列は辞書順比較でソートする、引数に比較関数を渡すと比較関数の基準でソートしてくれる。
a.sort(); // => [1, 2, 3]
["abs", "abc", "a", "c", "bc", "b"].sort(); // => ["a", "abc", "abs", "b", "bc", "c"]

// 配列の連続する要素を切り出して返す (配列自体は変更されない)
// slice(a, b) で 添え字[a,b)までの要素を切り出します。bを省略すると最後までになります。
var a = [1, 2, 3, 4, 5];
a.slice(1, 3); // => [2, 3]
a.slice(2); // => [3, 4, 5]

// 配列の要素の削除・挿入・置換
// a.splice(start, cnt, value) で位置startからcnt個の要素(0個以上)を値valueに置き換えます。(戻り値は削除した要素を返す)
// valueを省略するとcnt個の要素が削除され、valueとcntの両方を省略すると配列の末尾まで削除されます
var a = [1, 2, 3, 4, 5];
// 挿入 splice(k, 0, val) でk番目に値valを挿入できる
a.splice(2, 0, 10); // => [] (a = [1, 2, 10, 3, 4, 5])
// 削除 splice(k, 1) でk番目の要素を削除できる
a.splice(2, 1); // => [10] (a = [1, 2, 3, 4, 5])
// 置換 splice(k, 1, val) でk番目の要素をvalに置換できる
a.spice(2, 1, 10); // => [3] (a = [1, 2,, 10, 4, 5])

文字列(Stringオブジェクト)

// stringの宣言 (文字列はダブルクォーテーションでくくってもシングルクォーテーションでくくっても同じものです)
var s = "hello";
var t = String("piyopiyo");
var u = 'hoge';

// 文字列の連結
"hoge" + "piyo"; // => "hogepiyo" (+で文字列連結できる)
// 比較
"hoge" == "hoge"; // => true
"abc" < "cba"; /// => true (辞書順で比較)

// 文字列の長さを返す
s.length; // => 5
// 1文字を抜き出す (1文字の文字列が返ってくる)
t.charAt(2); // => "y"
// charCodeAt(k)でk番目の文字の文字コードの取得
"ABC".charCodeAt(0); // => 65

// 文字列の検索
// indexOf(key, index) で位置index(省略すると0)から文字列keyを検索して最初に見つかった位置を返す (見つからなかったときは-1を返す)
s.indexOf("ll", 0); // => 2
t.indexOf("pi"); // => 0
// last.IndexOf(key, index) で位置index(省略すると0)から文字列keyを逆順に検索して最初に見つかった位置を返す (見つからなかったときは-1を返す)
t.lastIndexOf("pi"); // => 4

// 文字列の一部を抜き出す (元の文字列は変更しません)
// slice(start, end) で位置startからend-1まで抜き出せます (endを省略すると最後まで)
s.slice(1, 4); // => "ell"
s.silce(1); // => "ello"
// substr(index, k) で位置indexからk文字抜き出します (kを省略すると最後まで)
t.substr(4, 2); // => "pi"
t.substr(4); // => "piyo"

// 小文字に変換
"abcDeF".toLowerCase(); // => "abcdef"
// 大文字に変換
"abcDeF".toUpperCase(); // => "ABCDEF"

// 指定文字で分割した配列を返す
var d = "2012/12/17";
d.split("/"); // => ["2012", "12", "17"]
d.split(""); // => ["2", "0", "1", "2", "/", "1", "2", "/", "1", "7"]

文字列では正規表現を使った検索もありますが、ここでは割愛します。また文字列では"\n"のようにエスケープシーケンスも使えます。文字列は特定の位置の文字を変更できないみたいなのでsplit("")で1文字ずつ格納した配列に変換したものを使うとよさそうです。

型の変換
JavaScriptでは型を変換したいときがあります。そのようなときは以下の関数を使うとよいです。

// 数値 -> 文字列の変換はNumberオブジェクトのメソッドtoStringを使うとよいです。
// 文字列へ変換 (引数に基数を渡すとn進数に変換した文字列を返す、省略したときは基数は10)
var a = 12;
a.toString(); // => "12"
a.toString(2); // => "1100" (2進数)
a.toString(16); // => "c" (16進数)

// 文字列 -> 数値の変換
parseFloat("3.14"); // => 3.14
parseInt("12"); // => 12
parseInt("1111", 2); // => 15 (第二引数に基数の2を渡すと2進数として数値に変換する)
parseInt("ff", 16); // => 255

// 文字列を引数にとって式を評価した値を返す
eval("1+2"); // => 3
eval("35"); // => 35
eval("[1, 2, 3]"); // => [1, 2, 3]

よく使う数学関数
数学関数はMathオブジェクトにあります。

Math.abs(-1); // => 1
// 最大値を返す
Math.max(3, 5); // => 5
// 最小値を返す
Math.min(3, 5); // => 3
// 平方根を返す
Math.sqrt(2); // => 1.4142135623730951
// 累乗を返す
Math.pow(2, 3); // => 8
// eの累乗を返す
Math.exp(2); // => 7.38905609893065
// 自然対数を返す
Math.log(3); // => 1.0986122886681098
// 三角関数 (引数はラジアン, 浮動小数の誤差の関係で完全に0にならないことがあるので注意)
Math.sin(Math.PI/2.0); // => 1
Math.cos(Math.PI/2.0); // => 6.123031769111886e-17 (非常に小さい数)
Math.tan(0); // => 0
// 逆三角関数
Math.asin(1); // => 1.5707963267948966
Math.acos(1); // => 0
Math.atan(1); // => 0.7853981633974483
Math.atan2(1, 1); // => 0.7853981633974483
// 小数点以下を切上げ
Math.ceil(4.7); // => 5
Math.ceil(-4.7); // => -4
// 小数点以下を切り下げ
Math.floor(4.7); // => 4  
Math.floor(-4.7); // => -5
// 小数点以下を四捨五入
Math.round(4.7); // => 5
Math.round(4.2); // => 4
Math.round(-4.7); // => -5
Math.round(-4.2); // => -4
// 乱数[0,1)の小数を返す
Math.random();

ここまで覚えれば初歩的な問題は解けるようになるでしょう。しかし、自作のデータ構造を使いたい、連想配列が使い勝手が悪い(ただのobjectだから仕方がない)、優先度付きキューやUnion-Findや平衡二分探索木がないなど高度なデータ構造は自力で準備する必要があってやや大変です。これらについては割愛します。

デバッグの仕方など

JavaScriptはもともと標準入出力がないのでデバッグするのが面倒です。
とりあえずmain.html(htmlファイル)とmain.js(JavaScriptのコードを書くファイル)の2つを用意します。
JavaScriptはAtCoderの練習問題について解を出力するプログラムを書くことにしましょう。

main.html

<!DOCTYPE html>
<html lang="ja">

<head>
  <script src="main.js"></script>
</head>

<body>

Input:<br />
<textarea id="input" rows="10" cols="80"></textarea><br />
<input type="button" value="実行する" onClick="debug();">

</body>
</html>

main.js

// input に入力データが全部入る
function Main(input) {
    // 1行目がinput[0], 2行目がinput[1], …に入る
    input = input.split("\n");
    tmp = input[1].split(" ");
    
    // 文字列から10進数に変換するときはparseIntを使います
    var a = parseInt(input[0], 10);
    var b = parseInt(tmp[0], 10);
    var c = parseInt(tmp[1], 10);
    var s = input[2];
    
    // 出力
    console.log('%d %s', a+b+c, s);
}

// "実行する"ボタンを押した時に実行される関数 (デバッグ用)
function debug(){
	var input = document.getElementById("input").value;
	Main(input);
}

//* この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

デバッグの流れ
chromeの場合は「(右上の)chromeの設定」→「ツール(L)」→「JavaScriptコンソール(Shift+Ctrl+J)」で、FireFoxの場合は「(上のほうの)ツール」→「Web開発」→「Webコンソール(Shift+Ctrl+K)」でコンソールを開くことができます。出力は全部コンソールにするので必ず開きましょう

  • main.htmlをChromeかFireFoxなどのブラウザで開く
  • JavaScriptのコンソールを開く
  • 入力したいデータをmain.htmlのテキストエリアにコピペする
  • main.htmlの「実行する」と書かれたボタンをクリックする
  • コンソールに出力される

出力を見て問題なさそうならmain.jsのコードを提出します(関数debugは消し忘れても問題ないです)。問題があるときはmain.jsの関数Mainを修正し、main.htmlのページをリロード(F5キーでリロード)して「実行する」ボタンを押す、という作業を繰り返すとよいです。割と面倒ですが、もしもっと効率の良いデバッグ方法を知っている人がいたらぜひ私に教えてください。

chromeの作業中の様子


FireFoxの作業中の様子

JavaScriptの注意点

JavaScriptの型
JavaScriptの型は大きく分けて全部で6種類です。

  • undefined
  • null
  • boolean
  • number
  • string
  • object

ArrayやDateなどはobjectに含まれます。object以外の型はプリミティブ型という扱いです。未定義の変数の値と型はすべてundefinedになります。オブジェクトの型を知りたい時はtypeof演算子を使いましょう

typeof(undefined); // => "undefined"
typeof(3); // => "number"
typeof(3.14); // => "number"
typeof("hello"); // => "string"
typeof(null); // => "object" (nullは特殊な値のはずなのですが何故かobject型…、よくわからん)
typeof(true); // => "boolean"
typeof([1, 2, 3]); // => "object"
typeof( function(){} ) // => "function"

またプリミティブ型とそれ以外で違うのは参照になるか値のコピーになるかの違いがあります。プリミティブ型以外の型は参照になるので思わぬ値の変更に気をつける必要があります。

function f(x){
    return x * x;
}
function g(x){
    for(var i=0 ; i < x.length ; i++ ){
        x[i] = x[i] * x[i];
    }
    return x;
}

function Main() {
    var x = 10;
    f(x); // => 100 (x の値は10のままで変更されていない)
    var a = [1, 2, 3];
    g(a); // => [1, 4, 9] (a の値は [1, 4, 9]に変更されている)
    
    var b = [1, 2, 3];
    var c = b; // => 参照がコピーされる
    c[0] = 1000; // => 1000 (b = [1000, 2, 3], c = [1000, 2, 3], 配列cの値を変更すると配列bも変更されるので注意)
}

上記では配列自体はコピーされず配列の参照がコピーされています。配列をコピーするときはforループで要素1つずつコピーするか以下のようにslice(0)を使うとよいです。(ただし多次元配列のときは各要素の配列が参照になってしまいうまくいかない)

var a = [1, 2, 3];
var b = a.slice(0); // => [1, 2, 3]
b[0] = 1000; => 1000 (b = [1000, 2, 3], 配列aはそのまま)

比較するときの注意
JavaScriptでは異なるオブジェクトの演算・比較をするときに思わぬ結果になってしまうことがあるので注意が必要です。型の違いも含めて比較するときには===演算子を使うとよいでしょう。

// 比較
0 == "0"; // => true
0 === "0"; // => false (===演算子を使うと型が違うときに型変換せずにfalseになってくれる)
0 == false; // => true (0とfalseの比較と1とtrueの比較はtrueが返ってくるので注意)
1 == true; // => true
2 == true; // => false
"" == false; // => true (空文字列とfalseの比較はtrueになるので注意)
"hello" == true; // => false 
// 演算
10 + "20"; // => "1020" (10が文字列に変換され文字列の連結になってしまうの注意)
10 * "20"; // => 200 ("20"が数値に変換されてしまう)

実際にAtcoderに提出してみた

実際に以下の問題で提出してAcceptをもらいました。(あえてデバッグコードを残しています)

終わりに

JavaScriptは使い勝手の悪さも含めて私のお気に入りの言語なので「競技プログラミングでもJavaScriptは使えるよ！」ということが少しでもアピールしたくてこの記事を書きました。この記事を書くためにJavaScriptでせっせと問題を解いていたわけですが、結果としてJavaScriptは競技プログラミングでは使いづらいように感じてしまいました。この記事の内容だけではどうしても初歩的な問題しか解けないので機会があればデータ構造をJavaScriptで実装したりデバッグのさらなる工夫を重ねたいと思います。

それではみなさん楽しい競技プログラミングを！