2012-12-21

2010年から2012年までのプログラミングコンテストを振り返る

自分の実力がどれくらい向上しているのか自分でわからないので2011年5月から2012年12月16日までのコンテストについて時系列順に振り返ってみる。「参加人数」は0より大きい点数を取った人数を参加人数として扱い、「上位何%か」のところには(自分の順位)÷(参加人数)×100の小数第2位以下を切り捨てしたものとしている。

日付	時間	コンテスト名	スコア / 満点	順位 / 参加人数	上位何%か
2011年 05/14	5時間	UTPC 2011	300 / 1200	120位 / 157人	76.4%
2011年 06/05	5時間	UAPC 2011	3 / 12問	46位 / 156人	29.4%
2011年 08/06	5時間	KUPC 2011	400 / 1000	48位 / 132人	36.3%
2011年 09/24	5時間	UAPC 2011 summer	1 / 10問	55位 / 72人	76.3%
2011年 10/15	4時間	RUPC 2011	3 / 9問	57位 / 97人	58.7%
2011年 12/24	5時間	Xmas Contest 2011	175 / 800	63位 / 92人	68.4%
2012年 03/03	4時間	CTPC(一般)	500 / 1100	30位 / 64人	46.8%
2012年 03/13	3時間	RitsCamp Day1	4 / 7問	13位 / 53チーム	-
2012年 03/14	5時間	RitsCamp Day2	2 / 12問	9位 / 17チーム	-
2012年 03/15	3時間	RitsCamp Day3	1 / 6問	34位 / 37チーム	-
2012年 04/14	90分	ARC #001 (鯖が落ちたので中止)	300 / 400	4位 / 139人(参考記録)	-
2012年 05/02	90分	ARC #002	300 / 400	89位 / 358人	24.8%
2012年 05/26	3時間	ふか杯	300 / 700	22位 / 102人	21.5 %
2012年 05/27	90分	ARC #003	200 / 400	113位 / 302人	37.4%
2012年 06/02	2時間	WUPC 2012	430 / 600	47位 / 137人	34.3%
2012年 06/10	90分	HBPC	100 / 400	29 / 29	100%
2012年 06/16	90分	ARC #004	100 / 400	198位 / 307人	64.4%
2012年 06/30	90分	ARC #005	200 / 400	157位 / 261人	60.1%
2012年 07/01	5時間	KUPC 2012	500 / 1200	102位 / 178人	57.3%
2012年 07/06	3時間	ICPC国内予選	2 / 7問	69位 / 320チーム?	21.5%
2012年 07/21	90分	ARC #006	不参加	-	-	-
2012年 08/03	2時間	天下一予選A	250 / 400	70位 / 245人	28.5%
2012年 08/18	2時間	天下一予選B	180 / 400	73位 / 166人	43.9%
2012年 08/29	2時間	天下一予選C (携帯から参加)	200 / 400	112位 / 168人	66.6%
2012年 09/03	3時間	ACPC2012 Day1(携帯から参加)	1 / 7問	33位 / 35チーム	94.2%
2012年 09/05	3時間	ACPC2012 Day3(携帯から参加)	1 / 6問	22位 / 26チーム	84.6%
2012年 09/08	90分	ARC #007	200 / 400	142位 / 216人	65.7%
2012年 09/15	5時間	JAGSummerCamp Day2	2 / 10問	27位 / 38チーム	71.0%
2012年 09/16	3時間	JAGSummerCamp Day3 A	1 / 6問	27位 / 32チーム	84.3%
2012年 09/16	3時間	JAGSummerCamp Day3 B	1 / 7問	35位 / 42チーム	83.3%
2012年 09/17	5時間	JAGSummerCamp Day4	0 / 10問	-	-
2012年 09/22	90分	ARC #008	250 / 400	48位 / 248人	19.3%
2012年 10/20	5時間	ACPC2012Day2OL	3 / 10問	24位 / 36位	66.6%
2012年 10/20	90分	ARC #009	240 / 400	69位 / 278人	24.8%
2012年 10/21	5時間	Autumn Fest 2012	100 / 1070	68位 / 99人	68.6%
2012年 11/04	5時間	ICPC模擬地区予選 2012	1 / 10問	49位 / 49人	100%
2012年 11/18	5時間	ICPCアジア地区予選 2012	1 / 10問	31位 / 34チーム	91.1%
2012年 11/24	1時間	DigitalArts PC	200 / 300	55位 / 176人	31.2%
2012年 12/02	5時間	UTPC 2012	355.22 / 2400	51位 / 171チーム	29.8%
2012年 12/08	4時間	WUPC 2nd	260 / 800	71位 / 201	35.3%
2012年 12/16	90分	ARC #010	210 / 400	47位 / 287人	16.3%

初めてプログラミングコンテストに参加したのは2010年のICPC国内予選だが当時はAOJ・PKU・TopCoderの存在も知らず、ろくにプログラムも書けないレベルで0完だった。
AOJの存在を知り、問題をちゃんと解き始めたのは2010年9月頃からで、実質のデビュー戦にあたるのはUTPC 2011(2011年5月)になる。
2011年の6月くらいにはやるだけ問題くらいは確実に解けるようになっていたが、BFSとDFSの使い分けがまだ上手にできないレベルで、典型的なDPやダイクストラすら書けないレベルだった。
2011年のICPC国内予選は入院していて不参加だった。参加していたとしても高々3問しか解けないレベルだったので確実に予選落ちしていたと思う。
自力で典型DPを書けるようになったのはRUPC 2011以降(2011年10月)で、このとき初めて実戦でDPが書けたので感激した記憶がある。
2012年3月の立命館合宿ではじめて競技プログラマの方々の存在を知った、周りのレベルが本当に高くて刺激を受けた。
2012年4月から新AtCoderがオープンし、ここからAtCoder Regular Contestを始めとしてコンテストラッシュがはじまった。
2012年6月くらいになると典型的なDFS, BFS, DP, ダイクストラくらいは書けるようになっていたはず。二分探索や構文解析はまだ書けないレベルだった
2012年のICPC国内予選はいろいろと失敗して2問しか解けなかったが不思議な力でアジア地区予選の出場権を得る。
2012年JAG Summer Campに参加して自分の実力は地区予選レベルの問題がぜんぜん解けないレベルであることを知る。合宿のコンテスト中は隣に妖精さんがいた。
合宿4日目は2010年ICPC国内予選ぶりの0完で、チームのみんなには申し訳ない感じだった。
合宿終了後は解けなかった問題を復習し、座標圧縮、二次元累積和、構文解析、二分探索、ローリングハッシュが自力で書け、かなり多くのことを覚えた。
ICPCアジア地区予選は結局1問しか解けず明らかに自分の実力不足だった
今年のAtCoderでのコンテストは順位がいつも安定して50-70位であることが多く頭打ちになっている。さらに上を目指すにはより難しい問題を解けるようにならないといけない。
2012年で0完しそうで焦ったコンテストは「RitsCamp Day 3」「HBPC」「ACPC2012Day2OL」「Autumn Fest 2012」「ICPC模擬地区予選 2012」あたり。特に「HBPC」はコンテスト残り2分でsubmit→ACで、ぎりぎりすぎてコード書いているときに心臓止まりそうだった。

今後の課題

AOJの問題だけでなく、PKU・SRM・Project Eulerあたりの問題も解いていきましょう
ネットワークフロー系の問題も解けるようになりましょう
数値計算のアルゴリズムも覚えましょう
期待値DPなど確率などが絡む問題も解けるようになりましょう
数え上げ系の問題も解けるようになりましょう

2012-12-20

JavaScriptでデータ構造を実装したい！ (スタック・キュー・ヒープ実装編)

JavaScript

前回の記事「JavaScriptでデータ構造を実装したい！ (基本編)」ではJavaScriptでデータ構造を実装するために必要な知識をまとめたので、今回は実際にJavaScriptでスタック・キュー・ヒープを実装してみます。

まずはスタック・キューの実装ですがJavaScriptの配列には先頭や末尾の要素を出し入れするメソッドがあるのでスタック・キューは実装する必要がありません。しかし普段C++を使ってプログラミングコンテストに参加している感覚と同じようにスタック・キューを使うを使うためにメソッド名を同じにして使いやすくしてみましょう。
スタック

Stack.prototype.push = function (val) {
    this.data.push(val);
    return val;
}
Stack.prototype.pop = function () {
    return this.data.pop();
}
Stack.prototype.top = function () {
    return this.data[this.data.length - 1];
}
Stack.prototype.size = function () {
    return this.data.length;
}
Stack.prototype.empty = function () {
    return this.data.length == 0;
}

// 例
var st = new Stack();
st.push(1); // [] => [1]
st.push(2); // [1] => [1, 2]
st.push(3); // [1, 2] => [1, 2, 3]
st.empty(); // false
st.pop(); // [1, 2, 3] => [1, 2]
st.size(); // 2

キュー

function Queue() {
    this.data = [];
}
Queue.prototype.push = function (val) {
    this.data.push(val);
    return val;
}
Queue.prototype.pop = function () {
    return this.data.shift();
}
Queue.prototype.front = function () {
    return this.data[0];
}
Queue.prototype.size = function () {
    return this.data.length;
}
Queue.prototype.empty = function () {
    return this.data.length == 0;
}

// 例
var q = new Queue();
q.push(1); // [] => [1]
q.push(2); // [1] => [1, 2]
q.front(); // 1 
q.push(3); // [1, 2] => [1, 2, 3]
q.pop(); // [1, 2, 3] => [2, 3]
q.pop(); // [2, 3] => [3]
q.size(); // 1
q.pop(); // [3] => []

メソッド名が同じなのでほとんどC++と同じようにプログラミングコンテストで使うことができそうです。(ただし、空の時にpopしようとしたときなどC++とJavaScriptで動作が異なる操作は存在する)

最後にヒープを実装してみましょう。ヒープ(二分ヒープ)は優先度付きキューの実装によく使われており、最小値(最大値)を効率よく取り出すことができるデータ構造です。ヒープの実装は二分木でなく実際には配列で実装するのが一般的のようです。ヒープの実装はプログラミングコンテストチャレンジブックp.71を参考にしてつくりました。
ヒープ

function Heap () {
    this.heap = new Array();
    this.size = 0;
}
Heap.prototype.push = function (val) {
    var k = this.size++;

    while( 0 < k ) {
        var p = Math.floor( (k - 1) / 2 );
        
        if( this.heap[p] <= val ) break;
        
        this.heap[k] = this.heap[p];
        k = p;
    }
    this.heap[k] = val;
}
Heap.prototype.pop = function () {
    var ret = this.heap[0];
    var x = this.heap[--this.size];
	
    var k = 0;
    while( k * 2 + 1 < this.size ) {
        var a = k * 2 + 1;
        var b = k * 2 + 2;
        if( b < this.size && this.heap[b] < this.heap[a] ) a = b;
		
        if( x <= this.heap[a] ) break;

        this.heap[k] = this.heap[a];
        k = a;
    }
    this.heap[k] = x;
    return ret;
}
Heap.prototype.top = function () {
    return this.heap[0];
}
Heap.prototype.size = function () {
    return this.size;
}

// 例
q.push(3);
q.push(7);
q.push(6);
q.push(-7);
q.push(2);
q.push(8);
q.pop(); // => -7 (最小値が出てくる)
q.pop(); // => 2
q.pop(); // => 3
q.pop(); // => 6

JavaScriptでスタック・キュー・ヒープが実装できたので解ける問題が増えると思います。次回は「JavaScriptでデータ構造を実装したい！ (連想配列編)」です。(準備中)

2012-12-19

JavaScriptでデータ構造を実装したい！ (基本編)

JavaScript

前回の記事「JavaScriptで競技プログラミングを始めよう！」ではJavaScriptで競技プログラミングするために必要な知識やデバッグの方法をまとめました。しかし、プログラミングコンテストでより難しい問題を解くときには使い勝手の良いスタック・キュー・優先度付きキュー・連想配列・Union-Findなどがほしいときがあります。今回の記事ではこれらのデータ構造を実装するためどうしたらいいかをまとめました。

C++のようにクラス(のようなもの)をつくりたい

C++でクラスという概念を用いて自作のデータ構造やデータの管理をするときがあります。例えば2つの整数を組にしたデータ(Pair)をC++で実装するときは次のようにするでしょう。(C++には標準でstd::pairがあるので自分で実装する必要はない)

#include <iostream>
using namespace std;

class Pair{
public:
    // メンバ変数
    int first, second;
    // コンストラクタ
    Pair(int first, int second){
        (*this).first = first;
        (*this).second = second;
    }
    // 等しいかどうか
    bool equals(const Pair &p){
        return ((*this).first == p.first && (*this).second == p.second);
    }
    // 1増やす
    void inc(){
        (*this).first++;
        (*this).second++;
    }
};

int main(){
    Pair p(3, 5);
    Pair q(2, 4);
    p.equals(q); // => false
    q.inc(); // => q.fisrt = 3, q.second = 5
    p.equals(q); // => true
}

2つの整数を組にしたデータ(Pair)をJavaScriptで実装するときは次のようにします。

function Pair(first, second) {
    this.first = first;
    this.second = second;
    this.equals = function (p) {
        return (this.first == p.first && this.second == this.second);
    }
    this.inc = function () {
        this.first++;
        this.second++;
    }
}

function Main() {
    var p = new Pair(3, 5);
    var q = new Pair(2, 4);
    p.equals(q); // => false
    q.inc(); // => q.first = 3, q.second = 5
    p.equals(q); // => true
}

C++ではインスタンスはメンバ変数(今回はfirst,second)とメンバ関数・メソッド(今回はequals, inc)を持っていますが、JavaScriptでは関数(function)もただのオブジェクトなのでインスタンスはプロパティ(メンバ変数)しか持っていないことになります。ということはJavaScriptではインスタンスごとに関数名が同じでも処理の異なるメソッドを持つことができます。例えば次のようにします。

function Pair(first, second) {
    this.first = first;
    this.second = second;
    this.equals = function (p) {
        return (this.first == p.first && this.second == this.second);
    }
    this.inc = function () {
        this.first++;
        this.second++;
    }
}

function Main() {
    var p = new Pair(3, 5);
    var q = new Pair(2, 4);
    p.equals(q); // => false
    
    // inc を 2 増やす関数に変えてあげよう！
    q.inc = function () {
        this.first += 2;
        this.second += 2;
    };
    q.inc(); // => q.first = 4, q.second = 6
    p.equals(q); // => false
}

インスタンスごとに関数をプロパティに持つのは無駄だし、どうせメソッド名が同じでもインスタンスごとに異なる処理のメソッドが欲しいことなんてあまりないでしょう。そこでメソッドはprototypeに全部書いてあげると同じオブジェクトでもインスタンスごとに関数をプロパティに持つわけではなくなるのでうれしいです。

function Pair(first, second) {
    this.first = first;
    this.second = second;    
}
Pair.prototype.equals = function (p) {
    return (this.first == p.first && this.second == this.second);
}
Pair.prototype.inc = function () {
    this.first++;
    this.second++;
}
// 以下は省略

JavaScriptはC++やJavaと違いクラスベースではなくプロトタイプベース(インスタンスベース)らしいです。クラスベースの言語ではクラスを定義し、そのクラスを元にインスタンスを生成します。しかし、JavaScriptのような言語ではインスタンスを元に新しいインスタンスを生成します。このあたりの話はhttp://www.geocities.jp/m_hiroi/light/js04.htmlを見るとわかりやすいかもしれません。

まとめ

とりあえずC++やJavaのようにクラス(のようなもの)をつくりたいときは以下のようにコードを書けばよいことがわかりました。

// コンストラクタの代わり
function クラス名( /* 引数 */ ) {
    /* 処理(初期化など) */    
}
Pair.prototype.メソッド名1 = function ( /* 引数 */ ) {
    /* 処理 */
}
Pair.prototype.メソッド名2 = function ( /* 引数 */ ) {
    /* 処理 */
}
...

// インスタンスを生成するとき
var x = new クラス名(引数);

次回の記事は「JavaScriptでデータ構造を実装したい！ (スタック・キュー・ヒープ実装編)」です。

2012-12-16

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で実装したりデバッグのさらなる工夫を重ねたいと思います。

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

2012-11-13

■

2012-08-07

AtCoder Regular Contest #003

AtCoder

問題A:GPA計算

N文字の文字列rが与えられ,r[i]が評価を表しています。評価'A', 'B', 'C, 'D', 'F'の5種類があり、それぞれ4,3,2,1,0点です。評価を点数に換算して平均を求めます。評価は'E'でなく'F'となっているので気をつけましょう。また誤差は1e-9まで許容されるので出力する桁数が足りないとWAになります。気をつけましょう。

#include <cstdio>
using namespace std;
 
int main(){
    int N, s = 0, f[256] = {0};
    char r[101];
    f['A'] = 4;
    f['B'] = 3;
    f['C'] = 2;
    f['D'] = 1;
    f['F'] = 0;
    
    scanf("%d", &N);
    scanf("%s", r);
    for(int i=0 ; i < N ; i++ ){
        s += f[ r[i] ];
    }
    double ans = (double) s / N;
    printf("%.10f\n", ans );
}

問題B:さかさま辞書

N個の文字列が入力されるので文字列を逆順に対して辞書順でソートします。出力するときに文字列を逆順のまま出力しないように気をつけましょう。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<string> v;
    for(int i = 0 ; i < n ; i++ ){
        string s;
        cin >> s;
        reverse( s.begin() , s.end() );
        v.push_back( s );
    }
    sort( v.begin() , v.end() );
    for(int i=0 ; i < v.size() ; i++ ){
        string s = v[i];
        reverse( s.begin() , s.end() );
        cout << s << endl;
    }
}

問題C:暗闇帰り道

普通のダイクストラ法だとw,h <= 500 と大きいので計算量が間に合いません。この問題の解法は明るさについて二分探索して解くらしいです。二分探索で明るさを決め打ちしてその明るさより暗い区画に入らないようにBFSします。ゴールにたどり着けないケースがあるので注意しましょう。
SPFA(Shortest Path Faster Algorithm)だと通るという話があるようですが、私は未確認です。

#include <iostream>
#include <cstdio>
#include <map>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;

const int INF = 1e+8;
const int MAX_W = 501;
typedef pair<int,int> P;

int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
char c[MAX_W][MAX_W];
int d[MAX_W][MAX_W];
int w, h, sx, sy;

// ch := 日当たりの良さ, t := 経過時間
// 区画の明るさ = ch * 0.99^t を返す.
double light(char ch, int t){
    return (double)(ch - '0') * pow( 0.99 , t );
}

// 明るさが mid 以上のところのみで BFS
bool bfs(double mid){
    // 初期化
    for(int y=0 ; y < MAX_W ; y++ ){
        for(int x=0 ; x < MAX_W ; x++ ){
            d[y][x] = INF;
        }
    }
    queue<P> q;
    q.push( P(sx,sy) );
    d[sy][sx] = 1;
    
    while( !q.empty() ){
        int x = q.front().first;
        int y = q.front().second;
        int t = d[y][x];
        q.pop();
        
        for(int i=0 ; i < 4 ; i++ ){
            int mx = x + dx[i];
            int my = y + dy[i];
            if( mx < 0 || my < 0 || mx >= w || my >= h || c[my][mx] == '#' ) continue;
            
            if( c[my][mx] == 'g' ){
                return true;
            }
            if( d[my][mx] == INF && isdigit(c[my][mx]) && mid < light( c[my][mx] , t ) ){
                d[my][mx] = t+1;
                q.push(P(mx,my));
            }
        }
    }
    return false;
}

int main(){
    
    scanf("%d %d", &h, &w );
    for(int y=0 ; y < h ; y++ ){
        scanf("%s", c[y]);
        for(int x=0 ; x < w ; x++ ){
            if( c[y][x] == 's' ){
                sx = x; sy = y;
            }
        }
    }
    
    if( !bfs(-1) ){ // たどり着けないとき
        printf("-1\n");
    }else{
        // 二分探索
        double low=0.0, high=10.0;
        for(int k=0 ; k < 100 ; k++ ){
            double mid = (low + high) / 2.0;
            if( bfs(mid) ){
                low = mid;
            }else{
                high = mid;
            }
        }
        printf("%.10f\n", low );
    }
}

問題D:シャッフル席替え

許容される誤差が2e-3とゆるいので実際にモンテカルロ法でシミュレーションして計算すると正解できる問題でした。モンテカルロ法では正しい答えが求まる保証はないですが、試行回数を増やすことによって許容誤差以内の解を求める確率が高くなるみたいです。

#include <iostream>
#include <cstdlib>
#include <map>
#include <ctime>
#include <vector>
using namespace std;

typedef pair<int,int> P;

// [a,b] のどれかの整数を返す。 (a,b は非負整数)
int random(int a, int b){
    int range = b - a + 1;
    return rand() % range + a;
}

// (v[i],v[i+1])のペア で 隣り合っていけないペアが存在するときは false を返す.
bool check(vector<int>& v, map<P,bool>& h){
    for(int i=0 ; i < v.size() ; i++ ){
        if( h[ P( v[i] , v[(i+1)%v.size()] ) ] ){
            return false;
        }
    }
    return true;
}

int main(){
    // 乱数の種の初期化
    srand((unsigned int)time(NULL));
    
    // 入力
    int N, M, K;
    cin >> N >> M >> K;
    
    // h[P(i,j)] := (i,j) が隣り合ってはいけないとき true を返す.
    map<P,bool> h;
    for(int i=0 ; i < N ; i++ ){
        for(int j=0 ; j < N ; j++ ){
            h[P(i,j)] = false;
        }
    }
    // 0..N-1 から 異なる 2つを選ぶ組合せ
    vector<P> c;
    for(int i=0 ; i < N ; i++ ){
        for(int j=i+1 ; j < N ; j++ ){
            c.push_back( P(i,j) );
        }
    }
    
    // 入力
    for(int i=0 ; i < M ; i++ ){
        int A, B;
        cin >> A >> B;
        h[P(B,A)] = h[P(A,B)] = true;
    }
    
    // x := シミュレーションする回数, cnt := 隣り合わせにならなかった回数
    const int x = 1000000;
    int cnt=0;
    for(int i=0 ; i < x ; i++ ){
        vector<int> v(N);
        for(int j=0 ; j < N ; j++ ) v[j] = j;
        
        // k 回席替え
        for(int j=0 ; j < K ; j++ ){
            int pos = random( 0 , c.size()-1 );
            int a = c[pos].first;
            int b = c[pos].second;
            swap( v[a] , v[b] );
        }
        
        // チェック
        if( check(v,h) ){
            cnt++;
        }
    }
    double ans = (double) cnt / x;
    cout << ans << endl;
}

2012-08-07

AtCoder Regular Contest #002

AtCoder

AtCoder Regular Contest #002

問題A:うるう年

うるう年かどうか判定する問題です。うるう年の規則については問題文に記述されているのでそれを見てプログラムを書くとよいでしょう。

#include <iostream>
using namespace std;

bool is_leap(int y){
    return ((y % 400 == 0) || (y % 4 == 0 && y % 100 != 0));
}

int main(){
    int y;
    cin >> y;
    cout << (is_leap(y)? "YES" : "NO") << endl;
}

問題B:割り切れる日付

入力された日付y/m/d以降で y÷m÷dが割り切れるもっとも早い日付を求めます。一日ずつ進めていって調べるとよいでしょう。

#include <cstdio>
using namespace std;

//            1  2  3  4  5  6  7  8  9 10 11 12
int h[12] = {31,28,31,30,31,30,31,31,30,31,30,31};

bool is_leap(int y){
    return ((y % 400 == 0) || (y % 4 == 0 && y % 100 != 0));
}

struct Time{
    int y,m,d;
    Time(int y_, int m_, int d_){
        y = y_; m = m_; d = d_;
    }
    void inc(){
        if( is_leap( y ) && m == 2 && d == 28 ){
            d++;
        }else if(is_leap( y ) && m == 2 && d == 29 ){
            m++;
            d = 1;
        }else{
            if( d < h[m-1] ){
                d++;
            }else{
                d = 1;
                if( m == 12 ){
                    m = 1;
                    y++;
                }else{
                    m++;
                }
            }
        }
    }
};

bool check(Time t){
    if( t.y % (t.m * t.d) == 0 ) return true;
    return false;
}

int main(){
    int y, m ,d;
    scanf("%d/%d/%d", &y, &m, &d);
    Time t( y , m , d );
    while( !check(t) ){
        t.inc();
    }
    printf("%d/%02d/%02d\n", t.y , t.m , t.d );
}

問題C:コマンド入力

ボタンが'A', 'B', 'X', 'Y'の4種類があり, ボタンLとRに4種類のボタンのうち2つのボタンをショートカットとして割り当てることができます。
2つのボタンをショートカットとして割り当ては全部で16通りで、LとRの2つのボタンに割り当てるので16*16=256通り全部のショートカットの割り当てを試すとよいでしょう。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
string h[16] = {
    "AA","AB","AX","AY",
    "BA","BB","BX","BY",
    "XA","XB","XX","XY",
    "YA","YB","YX","YY"
};

int solve(string s){
    int ans = 1e+8;
    for(int i=0 ; i < 16 ; i++ ){
        for(int j=0 ; j < 16 ; j++ ){
            if( i == j ) continue;
            int sum=0;
            for(int k=0 ; k < s.size() ; ){
                if( k == s.size()-1 ){
                    sum++;
                    k++;
                }else if( s[k] == h[i][0] && s[k+1] == h[i][1] ){
                    sum++;
                    k += 2;
                }else if( s[k] == h[j][0] && s[k+1] == h[j][1] ){
                    sum++;
                    k += 2;
                }else{
                    sum++;
                    k++;
                }
            }
            ans = min( ans , sum );
        }
    }
    return ans;
}

int main(){
    int n;
    string s;
    cin >> n >> s;
    cout << solve( s ) << endl;
}