OpenBLASが速かった

ちょっと行列演算をしたかったので適当にコードを書き散らしていたのですが、速度が必要な演算であるために既成のライブラリを使うこととしました。今回は行列乗算ができれば良いのでBLASを生で使ってもそんなに問題ありません。BLASの中でも高速な実装であるOpenBLASを使い、適当に書いたコードと速度の比較をしてみます。

結論から言うと、OpenBLASの速さを舐めてました。まさか50倍の速度差がでるとは。

比較に用いたマシンは、MacBook Pro 2013 Late 13 inch (2.4 GHz Intel Core i5) です。

インストール

Macの場合はbrewで。LinuxでもOpenBLASのパッケージはたいていのディストリビューションにはあると思います。

$ brew install homebrew/science/openblas

Matrix クラス

1024 × 1024の大きさの実正方行列の掛け算をします。以下N = 1024とします。

const int N = 1024;

適当にMatrixクラスを定義します。精度はそこそこで良いので今回はfloatを使います。

class Matrix {
public:
    Matrix(int row_size, int col_size) :
        row_size_(row_size),
        col_size_(col_size),
        data_(new float[row_size * col_size]) {}

    float& operator()(int row, int col) { return data_[row * col_size_ + col]; }
    const float& operator()(int row, int col) const { return data_[row * col_size_ + col]; }

    float* data() { return data_.get(); }
    const float* data() const { return data_.get(); }

private:
    int row_size_;
    int col_size_;
    unique_ptr<float[]> data_;
};

operator()を定義していて、行列Ai行目j列にはA(i, j)でアクセスできるようにしておきます。

1024 × 1024 の行列 A, B を掛け算し、C = ABを計算するものとします。C++の変数としては小文字a, b, cを用いて次のように表すとします。

Matrix a(N, N);
Matrix b(N, N);
Matrix c(N, N);

ナイーブに掛け算をした場合

ナイーブに実装すると次のようになるでしょう。

for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
        float s = 0;
        for (int k = 0; k < N; ++k) {
            s += a(i, k) * b(k, j);
        }
        c(i, j) = s;
    }
}

この場合、b(k, j)の部分がメモリを飛び飛びにアクセスすることになるので速度はでません。clang -O3で試すと、おおよそ6〜7秒程度の時間がかかります。

乗算順序を変更

i, j, kの順序でアクセスするのではなく、i, k, jの順でアクセスするとメモリアクセスが飛び飛びにならないのでいくらか速度が稼げます。 ただしc(i, j)は0で初期化しておく必要があります。

for (int i = 0; i < N; ++i) {
    for (int k = 0; k < N; ++k) {
        for (int j = 0; j < N; ++j) {
            c(i, j) += a(i, k) * b(k, j);
        }
    }
}

これでおよそ1.1〜1.2秒ぐらいです。演算回数としては10243なので1G回の演算があるわけですが、2.4GHzのCPUで1.2秒となると、まあちょっと遅いですねという気持ちになります。

OpenBLAS の場合

関数cblas_sgemmを使います。cblas_sgemmは、行列A, B, Cとスカラーα, βαAB + βCを計算します。計算結果はCに格納されます。単に掛け算ABを計算したければ、βを0とすれば良いでしょう。

cblas_sgemmの引数はちょっと見ただけではわかりづらいです。

行列の要素はメモリ上では行ごとに並んでいるので、CblasRowMajorを指定する必要があります。FORTRANなどではメモリ上は列ごとにならべるのが普通ですがC/C++では行ごとにならべるのが普通です。また、cblas_sgemmでは転置してから行列を掛け算することもできます。今回は転置などせずに掛け算するので、CblasNoTransを指定します。

cblas_sgemm(CblasRowMajor, CblasNoTrans, CblasNoTrans,
    N, N, N,
    1, a.data(), N,
    b.data(), N,
    0, c.data(), N);

これの計算時間はわずか0.03秒でした。

ちなみにEigenでも同じような計算をしてみたのですが、こちらは0.11秒程度でした。それでも速いですね。

2016-01-17
活動日記

ぷよぷよ AI

実機で動作するぷよぷよAIというものをしばらく有志で作っておりました。プロジェクトはgithub.com/puyoaiで公開しています。

これに関連するイベントを今までいくつか開いています。

また、先日行なわれたゲームプログラミングワークショップ 2015 (GPW-15)というワークショップで招待講演としてぷよぷよAI 人類打倒に向けてというタイトルで発表しました。スライドはリンク先の slideshare にアップロードしてあります。

2015-11-10
puyopuyo

王様達のヴァイキングの監修について

なぜこんな仕事を?

簡単に言うと、深見先生に頼まれたから、です。

もともと、競技プログラミングのマンガを描こうという話が2005年ぐらいからありました。しかし、詳細を詰めるのが難しく、一度ネームもできたものの掲載には至りませんでした(注: 私が描いたのではありません)。このときの色々な縁で深見先生とは親しくなりました(注: 競技プログラミングマンガと深見先生は直接は関係ありません)。深見先生に王様達のヴァイキングの話がきたときに、せっかくだから我々とやりたいということで話が回ってきたものです。

ただ、話が回ってきたときには6話ぐらいは話が固まっていて、また、もともとの監修は sotarok と ozarn だけに回っていました。今がそうでないとは言いませんが、最初の頃はもっと起業ものっぽい雰囲気を醸し出していたでしょう?

深見先生が協力として入ることになった後に、旧知の仲である我々にも回ってきました。そのときはちょっと画像を提供するぐらいの話でしたし、そのつもりでいました。また、もっと監修は人がいました。具体的には、YUHAのメンバーと、Gokuriのメンバー、などです。だから、そんなに負担にならないと考えました。ただ、徐々に監修は人を減らしていきました。これはそこまで仕事がなくなったというのが大きいのと、あまり多人数いても意見だけが出てまとまらないためです。人が減ったとはいえ、あまり負担は変わっていません。マンガを読んで育ってきたので、一作関われるというのも良い機会だな、と思って楽しんで協力しています。

何をやっているのか?

技術的詳細を考えることです。

基本的に、話はさだやす先生が作ります。それを受けて、事件などを深見先生が作ります。しかし、そこには技術的な詳細は書かれていません。そこで、例えば「ハッキングをする」と書かれてある部分の技術的な詳細を考え、仮のセリフをいくつか挟む形にまで落とし、その詳細を平易な日本語でさだやす先生、深見先生、および担当の山内さんに説明します。なるべく、話も読者に分かりやすい展開になるように僕は心がけています。テクニカルには別の手段を使ったほうが良い技術でも、今後の展開および、マンガとしての要請のために別の技術を敢えて用いることもあります。これは詳しい人からはツッコまれますが、それは覚悟の上です。また、マンガの上では詳細はかけません。かいても難しすぎるだけだからです。

ハッキングの技術的難易度を調整するのは難しいのですが、私が見ている分に関しては、最低でも「理論的にはできる」話にしてあります。ほとんどの場合、それを実際にやったことがある人を聞いたことがあるものを採用しています。Windows のバイナリパッチを作った話なんかは、実際にそういう人がいるという話を聞いたので、じゃあいいだろうということで通してあります。また、過去に似たようなハッキング事例があれば、それを参考に技術的詳細を詰めたりします。大体5割ぐらいの技術的詳細は僕が決めていると思いますが、週に数時間程度の時間でだいたいなんとかなっています。

2014-08-14

Shinya Kawanaka / 川中 真耶 / a.k.a. MAYAH

English version? See LinkedIn / 英語版は LinkedIn へ。

書いたもの、作ったものは Publications をご覧ください。

その他の活動場所

スキル

プログラミング言語

2014年8月現在。

  • C/C++
  • Java
  • OCaml
  • Scala
  • ECMAScript/JavaScript
  • Ruby
  • go
  • Python
  • scheme
  • Objective C

他にも、Haskell, D, SML, Prolog, Concurrent Clean, ……などを書いてきましたが、5,000行にみたないものは省略します。

なんだかんだ言ってC++を一番書いています。最も好きなのはOCamlです。ほかは Java, Scalaあたりを一番使ってきたと思います。 仕事ではC++とかgoを書いていることが多いです。JavaScriptも必要に応じて結構書きます。

プログラミングコンテスト

ICPCあたりに出場することに、過去お熱でした。我々が現役の頃は、今と違って国内のICPCはやや平和な感じでしたが、世界には通用しませんでした。我々の下の代あたりから、半分がICPC OB/OG会のせいで半分はIOIのせいだと思うのですが、急激に強くなっていった印象があります。

ICFPプログラミングコンテストも過去2年に一回ぐらい色々出場していますが、わりと成績は忘れています。これは、どちらかというとお祭りです。

  • ACM ICFP 2014: 成績はいまいちでした。40位ぐらい。
  • ACM ICFP 2013: 8位。色々まだできることはありそうでしたが、全体としてはそう悪くはなかったです。
  • ACM ICFP 2011: この年は出題側で、対戦サーバーのほとんどを3日ぐらいで書いて運用していました。大変だった……。
  • ACM ICFP 2010: 成績忘れましたが、良くはなかったです。
  • ACM ICFP 2007: 83rd place (3 member): この年は最もひどかった。
  • ACM ICFP 2004: 46 位。一人でやってて疲れた記憶しかありません。
  • ACM ICFP 2003: 9位。学科の友達何人かと参加。

その他

2014-08-12

書いたもの / 作ったもの

本 / 電子書籍

同人活動の一環として発行した本は、同人サークルYUHAの発行物をごらんください。 そのほか、SIG2Dにも寄稿しています。

ソフトウェア

作ったもののうち、ある程度面白そうなものを。

監修

Papers

  • Shinya Kawanaka, Yevgen Borodin, Jeffrey P. Bigham, Daren Lunn, Takagi Hironobu, Chieko Asakawa: Accessibility commons: a metadata infrastructure for web accessibility. In Proceedings of the 10th international ACM SIGACCESS Conference on Computers and Accessibility (Halifax, Nova Scotia, Canada, October 13 - 15, 2008). Assets ‘08. ACM, New York, NY, 153-160
  • Hironobu Takagi, Shinya Kawanaka, Masatomo Kobayashi, Takashi Itoh, Chieko Asakawa: Social accessibility: achieving accessibility through collaborative metadata authoring. In Proceedings of the 10th international ACM SIGACCESS Conference on Computers and Accessibility (Halifax, Nova Scotia, Canada, October 13 - 15, 2008). Assets ‘08. ACM, New York, NY, 193-200
  • Shinya Kawanaka, CSS 2007: JavaScript Injection Prevention by Anomaly Detection (Good Paper Award)
  • Shinya Kawanaka, Haruo Hosoya: biXid: a bidirectional transformation language for XML. ICFP 2006: 201-214. (This is also a master thesis.)
  • Shinya Kawanaka, Region Inference for dynamically typed language (Bachelor thesis)

Slides (Japanese)

slideshare上にもスライドがいくらかあります。

Articles (Japanese)

  • ASCII .technologies (2010-06) クラウドのいる場所. 8 pages.
  • ASCII .technologies (2010-10) Cassandra からのぞく NoSQL の世界 8pages
  • ASCII .technologies (2010-11) Cassandra からのぞく NoSQL の世界 8pages
  • ASCII .technologies (2010-12) Cassandra からのぞく NoSQL の世界 8pages
  • ASCII .technologies (2011-01) Cassandra からのぞく NoSQL の世界 8pages
  • ASCII .technologies (2011-02) Cassandra からのぞく NoSQL の世界 8pages
  • ASCII .technologies (2011-03) Cassandra からのぞく NoSQL の世界 8pages
  • ASCII .technologies (2011-04) Cassandra からのぞく NoSQL の世界 8pages
2014-08-11

ソースコードのバランスシート

バランスシートには、資産、負債、純資産の項目があり、資産=負債+純資産が常に成り立ちます。さて、いまここにあるソースコードを資産だと思いましょう。すると、それは負債と純資産からなっている、ということになります。

では、ソースコードにおいて、負債や純資産とは何でしょう。

負債は後で返さなければならないものです。借りっぱなしにしておくと、利子が発生します。ソースコード上でこれに対応するのは、汚いコード、ゴミコード、やっつけ仕事のコードです。これは、とりあえずソフトウェアを動かすには必要なことがあります。借金のおかげで急場をしのげて助かった、そういう経験がある人もいるでしょう。ですが、負債なので、あとで返済しなければなりません。世の中には、技術的負債という単語があります。まさにそういうことです。

ここで少し注目したいのは、コードにも利率が存在することです。本当のゴミコードは、ヤミ金の如く利率が高く、真っ先に返済しなければなりません。後で問題になるかもしれないけど、まあしばらくは問題が起きないだろうというコードもあって、こちらは利率が低いので後回しでも構いませんし、実際に後回しにされます。

純資産とは何でしょう。これは、問題が起きにくいコード、きれいなコード、よくテストされたコード、などとなります。ここで面白いのは、純資産にも利子が存在することです。純資産が溜まっていくと、その部分のコードは問題がおきにくく、それに依存したコードの開発が加速します。これは非常に良いことで、こういうコードをたくさん積み重ねていくことで、企業にとっての価値になるでしょう。

純資産の方には、技術的負債のような単語を見つけることができませんでした。何か良い言葉、ありますか?

2011-02-09

OCaml 基礎最速マスター

OCamlとは

OCaml は Haskell とは違って純粋でない関数型言語です。ML (Meta Language) という言語ファミリーの方言の一つで、フランスの INRIA という研究所で開発されています。速度を稼ぐために命令型のように書こうと思えば書けるし、遅延評価もデフォルトではしません。その分、実用的なアプリケーションが書きやすくなっています。

他の言語をある程度知っている人は、これを読めば OCaml のとりあえずの基礎をマスターして OCaml を書くことができるようになります。他の関数型言語の知識は仮定していませんが、C/C++ ぐらいの知識があれば読めると思います。元の Perl 基礎文法最速マスターではリファレンスぽい作りですが、チュートリアルぽくなってしまいました。

なお、読んでいると分かりますが、色々とめんどくさいことが多いように感じます。しかし、これをちゃんと書くと、コンパイルに通るだけでかなりの数のバグがつぶれてくれているという恩恵を受けられます。我慢して使うといいことがあります。はじめは我慢してみてください。

この文章には不足やバグがいっぱいあると思いますので是非指摘してください。

他の最速マスター系は はてな的プログラミング言語人気ランキング あたりを見てください。

基礎

OCaml はコンパイルして実行することも対話型インタプリタで実行することもできますが、ここでは対話型インタプリタで実行します。対話型インタプリタは ocaml コマンドで起動します。

$ ocaml
        Objective Caml version 3.11.1

#

とりあえず、適当に値や式を打ち込み、;; を入力するとそのまま評価されて出力されます。

# 1;;
- : int = 1
# "some";;
- : string = "some"
# 1.0;;
- : float = 1.
# 'a';;
- : char = 'a'

ごらんの通り、型と値が表示されます。1.0 は float 型になっていますが、OCaml の float は C の double と同じです。C の float に相当する型は、標準にはありません。

print 系で表示をするには、print_int などのように型を付けるか、Printf.printf を使います。

# print_int 1;;
1- : unit = ()
# print_string "some";;
some- : unit = ()
# print_float 1.0;;
1.- : unit = ()
# print_char 'a';;
a- : unit = ()
# Printf.printf "%d%s%f%c" 1 "some" 1.0 'a';;
1some1.000000a- : unit = ()

ここで、1- : unit = () の様に表示されているのは、1print_int によって表示された部分で、- : unit = () は OCaml のインタプリタによって表示された部分です。OCaml では全ての式は値を持ちますが、特に意味のない値として、() という値が定義されています。これは unit という型を持ちますが、void みたいなものだと思ってしばらくはかまいません。

なお、コメントは、(* コメント *) のように (* *) でくくります。コメントはネストができるので、(* (* some *) *) も正当なコメントです。

変数

OCaml の変数は普通の言語の変数とはちょっと違って、「値に名前を付けたもの」です。普通の言語の変数は「値を入れる箱」の名前であり、その中身をいくらでも変更ができますが、OCaml は「値に名前を付けたもの」なので、中身を変更することはできません。ただ、同じ名前を再び付けてしまって実質書き換えたようにみせることはできます。C でいうところの const が付いていると思ってもらえれば、しばらくは OK です。

OCaml の変数は let 式で定義します。let 式は let 変数名 = 式1 in 式2 のように使います。「式1」の値の名前を「変数名」で名付け、「式2」中で参照できるようにします。

# let x = 1 in x;;
- : int = 1
# let x = 1 in
  let y = x in
  y;;
- : int = 1

なお、トップレベル (要するに、他の式の中ではない)で let 式を書く場合は、in 以下を省略して、グローバル変数的な扱いにすることができます。

# let x = 1;;
val x : int = 1
# let y = x;;
val y : int = 1

この場合、式の値を出力した部分に変数名が付いていることが確認できます。(val x の部分)

四則演算

四則演算は +, -, *, / が普通に使えます。int に限っては。あまりの演算は mod です。

# 1 + 1;;
- : int = 2
# 3 - 2;;
- : int = 1
# 2 * 4;;
- : int = 8
# 7 / 2;;
- : int = 3
# 6 mod 3;;
- : int = 0

float 型の値では、各演算子の後に . を付けなければなりません。めんどいです。すいませんすいません。

# 1.0 +. 1.0;;
- : float = 2.
# 3.0 -. 1.0;;
- : float = 2.

しかも float から int を引こうとすると、自分で intfloat に変換しなければなりません。これには float 関数が使えます。本当にめんどくさいですね。すいませんすいません。これには訳があるのです。それは次の章で。

# 3.0 -. (float 1);;
- : float = 2.

また、変数の章で説明しましたが、変数は一度値を入れると変更できないので、+= に相当するような演算子はありません。なくはないのですが、邪道なので。

ちょっとだけ型の話

どうして ++. が分かれているのかというと、OCaml が型に対して非常に厳密だからです。+intint の足し算と定義され、また+.floatfloat の足し算と定義されています。int と float の和というような定義の足し算は自分で作らない限りありません。OCaml は(一部の例外を除いて)勝手に型変換をしないので、intfloat にするのは自分で変換する必要があります。

いくつかのデータ構造

組み込みで単方向リスト、タプル、配列があります。レコードもありますがしばらくは使わなくてまあなんとかなるでしょう。単方向リストやタプルは非常に良く使うので重要です。

(* 単方向リストは、要素を [] で囲んで ; で区切って書きます。 *)
# [1; 2; 3];;
- : int list = [1; 2; 3]
(* 先頭への追加は :: を使います *)
# 1 :: 2 :: 3 :: [];;
- : int list = [1; 2; 3]
(* @ でリストを連結できます *)
# [1; 2] @ [3];;
- : int list = [1; 2; 3]
(* リストには同じ型のものしか入りません *)
# [1; 1.0];;
Error: This expression has type float but an expression was expected of type
         int (* int が予測されているところに float が来ました *)

List.hd で 先頭要素、List.tl で先頭要素を除いたリストをとれます。

# List.hd [1; 2; 3];;
- : int = 1
# List.tl [1; 2; 3];;
- : int list = [2; 3]
(* タプルは、コンマで区切って書きます。一応括弧を付けてください *)
# (1, 3, "some");;
- : int * int * string = (1, 3, "some")
(* タプルは同じ型じゃなくてもかまいません。*)

2つ組の場合は、fst, snd でそれぞれ1つめの要素、2つめの要素をとれます。3つ組み以上の場合は fst, snd は使えません。この辺は後のパターンマッチの章で出てきます。

# fst (1, 2);;
- : int = 1
# snd (1, 2);;
- : int = 2
(* 配列は [| |] 中に要素を入れます。これも同じ型じゃないと入りません。*)
# let x = [|1; 2; 3|];;
val x : int array = [|1; 2; 3|]
(* 要素へのアクセスは、x.(n) のようにします。なんか変な文法ですね。*)
# x.(0);;
- : int = 1
(* 配列の要素は実は更新可能です。配列そのものは更新できません。*)
# x.(0) <- 2;;
- : unit = ()
# x;;
- : int array = [|2; 2; 3|]
(* 配列の要素数は Array.length で取ります。*)
# Array.length x;;
- : int = 3

制御式

if は通常 if-then-else で書きます。

if 1 = 1 then 2 else 3

値の比較は = です。== だとポインタで比較になります。デフォルトでは = で OK。値の否定の比較は<> で、ポインタでの否定の比較は != です。紛らわしいですね。いや本当に。あとの<, >, <=, >= は一緒です。

また if-then-else も型に厳密で、if の後は bool 値のみです。また、thenelse の後は両方とも同じ型でなければなりません。なので、次のようなのはだめです。

(* if の後が bool じゃなくて int*)
# if 0 then 1 else 2;;
Error: This expression has type int but an expression was expected of type
         bool
(* then は int なのに else は float *)
# if true then 0 else 1.0;;
Error: This expression has type float but an expression was expected of type
         int

else 以降は省略できますが、省略すると else () があるとみなされます。()unit 型の値でした。つまり、thenunit しかとれなくなります。

if をネストするとき、C の { } 相当のものを入れないと、内側の ifelse がぶらさがってしまう問題があります。C の { } 相当のものは begin end です。

(* 何も表示しないつもりなのに 2 が表示されてしまった *)
# if true then
    if false then print_int 1
  else
    print_int 2
  ;;
2- : unit = ()

(* 今度は OK *)
# if true then begin
    if false then print_int 1
  end else
    print_int 2
  ;;
- : unit = ()

この後オリジナルでは文字列の操作などが続きますが、OCaml はそういうのはあまり得意でないのでばっさり省きます。必要なら String 系のモジュールのマニュアルを見てください。

なお、whilefor もあるのですが、邪道なのでここでは触れません。ではループどうするのか? という問いは後の章で説明されます。

関数

やっと関数型言語ぽい説明をするところまで来ました。

関数適用に関しては、実はすでに使っています。関数 引数 引数 ... というように、空白で区切って連続して書けば関数適用になります。

$ print_int 1;;
1- : unit = ()
# Printf.printf "%d%s%f%c" 1 "some" 1.0 'a';;
1some1.000000a- : unit = ()

OCaml は関数型言語なので、関数も値です。従って名前を付けて変数に入れることができます。関数は fun 引数 引数 ... -> 式 の様に定義します。関数の返値は最後に評価した式の値です。なお、return はありません。

# let f = fun x y -> x + y;;
val f : int -> int -> int = <fun>
# f 1 2;;
- : int = 3

毎回 fun を書くのはめんどくさいですね。そういう場合の略記法もあります。

# let f x y = x + y;;
val f : int -> int -> int = <fun>

ここで、関数の型に注目すると、fint -> int-> int という型になっています。これは、int を2つ引数に取って(最後の) int を返す関数、と実戦的には読みます。本当は違いますけどね! 知りたい人は「カリー化」という単語でググってみてください。

さらに! 関数の定義を良くみると、どこにも int と書いてないのに勝手に int を2つ取って int を返す関数になってますね? これは、+intint の足し算である、と決めたせいです。正しく足し算するためには + の左辺と右辺は int なので、xyint じゃなければなりません。また、int + intint なので、f 自体も int を返すはずです。というわけで、fint を2つとって int を返す関数でなければならないのです。このように、勝手に型を決めてくれる機能を、型推論と言います。これのおかげでバグが非常に減ります。ありがたやありがたや。たまにうざいけどね!

なお、関数は別に変数に束縛する (という単語は初めて出てきましたが、値に名前を付けるという意味です) 必要なく使えます。

# (fun x y -> x + y) 1 2;;
- : int = 3

また、関数の引数としても渡せます。

# let apply f x y = f x y;;
val apply : ('a -> 'b -> 'c) -> 'a -> 'b -> 'c = <fun>
# let add x y = x + y;;
val add : int -> int -> int = <fun>
# apply add 1 2;;
- : int = 3

おっと、'a とか 'b とか 'c とかいう型はなんでしょう。これは多相型というものです。

多相型と型推論

型推論が行われた際に、完全に型を決めきれないと多相型というものが現れます。 上の apply なんかがそうで、'a とか 'b とかいう型が出てきています。非常におおざっぱにかつ乱暴に言うと、OCaml の関数はデフォルトでもう C++ のテンプレート関数みたいなもんだと思ってください。

たとえば、

# let id x = x;;
val id : 'a -> 'a = <fun>

は、x がどういう型であれ自分自身を返します。

C++ でいうところの、

template<typename T>
T id(T x) { return x; }

みたいなもんです。

ループと再帰

関数中で自分自身を呼び出すこと(再帰呼出)で、ループをさせることができます。C 的には気持ち悪いですしスタックも使いそうですが、大丈夫。関数の最後で自分を呼び出す限りは、最適化が効いてループと同じコードになります。これは保証されています。なので、ループしようと思ったら関数書いて再帰します。なお、自分自分を呼び出すときは let じゃなくて let rec を使わなければなりません。そういうもんだと思ってください。letlet rec の違いは、式の中で自分自身を参照できるかどうかが違います。

# let rec loop i n =
    if i < n then begin print_int i; loop (i + 1) n end
    else ()
  ;;
val loop : int -> int -> unit = <fun>
# loop 0 10;;
0123456789- : unit = ()

言い忘れてましたが、; を使ってで式を2つ以上書けます。C と同じで begin-end で囲まないと ;if が終わるので注意。

データタイプとパターンマッチ

OCaml ではデータ型を定義することができます。データ型とは、C/C++ の enumunion を併せて、強力でかつ安全にしたものです。データ型は type で定義します。

# type v =
    | Int of int
    | Float of float
  ;;
type v = Int of int | Float of float

大文字から始まる IntFloat の部分をタグとか呼んでいます。タグは大文字で始まらなければなりません。一度このようにデータ型を作ると、

# Int 3;;
- : v = Int 3
# Float 3.0;;
- : v = Float 3.

のようににして値を作ることができます。型は両方とも v になっているのに注意。つまり同じ型なので、リストなどに入れられます。

# [Int 3; Float 3.0];;
- : v list = [Int 3; Float 3.]

データ型を一度作った後、中のデータを参照したいときはパターンマッチが使えます。これは非常に強力です。どうして他の言語にこれがないんでしょうか?

パターンマッチは match 式で下のように書きます。-> の前にパターンを書き、そこに変数名を書いておくと、パターンに合うように変数に値が束縛されます。

# match x with
    | Int v -> print_int v
    | Float v -> print_float v
  ;;
3- : unit = ()

パターンマッチはデータ型以外でも使えます。タプルとかリストとか。また、C の switch の代わりにもなります。

# let rec fstof3 x = match x with
    | (a, b, c) -> a
  ;;
val fstof3 : 'a * 'b * 'c -> 'a = <fun>
# let rec sum lst = match lst with
    | [] -> 0
    | x :: xs -> x + sum xs
  ;;
val sum : int list -> int = <fun>
# sum [1; 2; 3; 4; 5];;
- : int = 15
# let rec fib x = match x with
    | 0 -> 1
    | 1 -> 1
    | x -> fib (x - 1) + fib (x - 2)
  ;;
val fib : int -> int = <fun>
# fib 4;;
- : int = 5

さらに

OCaml はもっといろんな文法、機能がありますが、ここでは紹介しきれません。ocaml.jp には日本語の情報がもっとありますから是非そちらも見てくださいね!

2010-11-01
ocaml

ACM-ICPC 国内予選

凡例

難易度は☆5段階で表しています。★は☆半分を表します。

  • ☆    :非常に易しい。全員が解いてほしい問題。
  • ☆☆   :易しい。アジア地区予選に進む為には絶対に解かなければならない。
  • ☆☆☆  :標準。アジア地区予選に進む為にはこのクラスの問題を1つは解けなければならない。
  • ☆☆☆☆ :難しい。上位に食い込む為には解かなければならない。
  • ☆☆☆☆☆:大変難しい。上位陣でも難しい。

解法・アルゴリズムでは、キーとなるアルゴリズム名を書いています。ad-hoc と書いてあるものは、その場その場で実装して解いていく問題を表しています。

ソースは、私が解いたソースへのリンクを張っています。

公式の output や PKU での問題と解答を比較していますが、解答が提供されていない問題もあるため、正答と比較出来ない場合があります。その場合備考に “Not Verified” と書いてあり、ソースの正当性は担保できません。間違っている恐れもあります。また、他の人が解を既に公開している場合、その解との比較を行って正解と見なした場合、その解へのリンクを張っています。また、PKU やプログラム・プロムナードへのリンクも、あれば張っています。公式の output があるものは PKU は通してないので、PKU だと TLE になる可能性があります。

1998 年

日本地区予選が始まった年。今から見ると簡単な問題のみで構成されています。それでもみんな解けていません。

問題問題名難易度解法・アルゴリズムソース備考
1Area of Polygons☆★多角形の面積1998A.ccNot Verified.
2A Simple Offline Text Editor☆☆ad-hoc1998B.ccNot Verified.
3Calculation of Expressions☆☆☆構文解析1998C.ccNot Verified.
4Board Arrangements for Concentration Games☆☆☆探索1998D.ccNot Verified.

1999 年

問題が5題に。今から見るとそれほど難しい問題は出ていません。

正答例がないため、Naoyuki Tamura さんの解答と比較しています。

問題問題名難易度解法・アルゴリズムソース備考n
AWhere'sYourRobot?ad-hoc1999A.cc
BUnableCount☆☆ad-hoc1999B.ccプロムナード
CFactorizationofQuadraticFormula☆☆ad-hoc1999C.cc
DSpiralFootrace☆☆☆★凸包に近い1999D.cc
EALongRideonaRailway☆☆☆探索1999E.cc

2000 年

前年よりは少し難しくなっていますが、まだそれでも今よりは簡単でしょう。E はやや問題文が理解しにくい。 この年の問題も正答例がないため、Naoyuki Tamura さんの解答と比較しています。

問題問題名難易度解法・アルゴリズムソース備考
AFermat's Last Theoremad-hoc2000A.cc
BPatience☆☆★探索2000B.cc
CCyber Guardian☆☆★ad-hoc2000C.cc
DStrange Key☆☆☆★ad-hoc2000D.cc
EFile Compression☆☆☆★ad-hoc2000E.cc

2001 年

前年と同程度の難しさ。

正答例が提供されていないため、東工大 Wiki の正答例と比較しています。

問題問題名難易度解法・アルゴリズムソース備考
AGet a Rectangular Fieldad-hoc2001A.cc東工大 Wiki (A) プロムナード
BMulti-column List☆☆ad-hoc2001B.cc東工大 Wiki (B)
CJigsaw Puzzles for Computers☆☆探索2001C.cc東工大 Wiki (C) プロムナード
DMissing Numbers☆☆☆連立方程式2001D.cc東工大 Wiki (D)
ENets of Dice☆☆☆★さいころ・探索2001E.cc東工大 Wiki (E)

2002 年

幾何問題が少し難しいですが、今のチームのレベルならおそらく全部解かれてしまうでしょう。A-D は今なら 80 分ぐらいで処理されてしまうかも。 東工大 Wiki, ACM-ICPC OB/OG の会に投稿されたソースと比較。C, D は未比較のため間違っているかもしれません。

問題問題名難易度解法・アルゴリズムソース備考
A Exploring Cavesad-hoc2002A.cc東工大 Wiki 2002 A
B Pile Up!☆☆ad-hoc2002B.cc東工大 Wiki 2002 B
C Kanglish : Analysis on Artificial Language☆☆ad-hoc2002C.ccNot Verified.
D What is the Number in my Mind?☆☆☆探索2002D.ccNot Verified.
E Enclosing Circles☆☆☆☆★幾何・円の共通接線2002E.ccACM-ICPC OB/OG の会 プロムナード

2003 年

E とそれ以外の難易度にかなり差があります。4問正解チームがかなりあり、全問正解は1チーム (Gokuri、自分のチーム)。E は探索ですが、ヒューリスティクスが必要なところが難しくなっています。最小全域木のアルゴリズムを知らないと、この年は苦しい戦いになったでしょう。

PKU に問題があるので、PKU で確認。

問題問題名難易度解法・アルゴリズムソース備考
AWhen Can We Meet?ad-hoc2003A.ccPKU 2028
BGet Many Persimmon Trees☆☆ad-hoc2003B.ccPKU 2029
CThe Secret Number☆☆☆動的計画法2003C.ccPKU 2030
DBuilding a Space Station☆☆☆最小全域木2003D.ccPKU 2031
ESquare Carpets☆☆☆☆★探索(ヒューリスティクス)2003E.ccPKU 2032

2004 年

問題が6題になり、易しい問題が一題追加されました。D, E, F はそれぞれ別の能力を要求しており、全て解ききるのは難しめ。D は幾何のひらめき、E は実装力、F は情報科学的なアルゴリズム構築能力と、かなり良いセット。全問正解が1チームあった(Gokuri-squeeze、これも自分のところのチーム)。

D は -O2 をつけて (あるいは Release build で) コンパイルしないと非常に遅くて、正解なのに正解と思ってなかったというチームがありました。

問題問題名難易度解法・アルゴリズムソース備考
AHanafuda Shufflead-hoc2004A.ccPKU 1978
BRed and Black☆☆再帰2004B.ccPKU 1979
CUnit Fraction Partition☆☆探索2004C.ccPKU 1980
DCircle and Points☆☆☆☆幾何・2点を通り半径が与えられた円2004D.ccPKU 1981
EWater Tank☆☆☆☆ad-hoc (シミュレーション)2004E.ccPKU 1982
FName the Crossing☆☆☆☆Floyd2004F.ccPKU 1983

2005 年

少し易しくなりました。E は幾何とシミュレーションの両方をこなす必要があって、やや難しめ。1チーム (GNC) が全問正解。

問題問題名難易度解法・アルゴリズムソース備考
AOhgas' Fortune☆★ad-hoc2005A.ccPKU 2683
BPolygonal Line Search☆☆★ad-hoc2005B.ccPKU 2684
CNumeral System☆☆構文解析2005C.ccPKU 2685
DTraveling by Stagecoach☆☆☆☆ダイクストラ2005D.ccPKU 2686
EEarth Observation with a Mobile Robot Team☆☆☆☆★幾何・線と線の距離2005E.ccPKU 2687
FCleaning Robot☆☆☆全探索2005F.ccPKU 2688

2006 年

少し難し目のセット。F は分かればそんなに難しくないが、本番で解くのは厳しい。C は実装が面倒。Input, Outout は こちらにある。5問正解が2チーム。C, F が両方とも国内予選で最難クラスの問題なので、全問正解はかなり厳しいだろう。

問題問題名難易度解法・アルゴリズムソース備考
ADirichlet's Theorem on Arithmetic Progressions☆★エラトステネス2006A.ccPKU 3006
BOrganize Your Train part II☆☆ad-hoc2006B.ccPKU 3007
CHexerpents of Hexwamp☆☆☆☆探索2006C.ccPKU 3008
DCurling 2.0☆☆☆探索2006D.ccPKU 3009
EThe Genome Database of All Space Life☆☆☆★ad-hoc (再帰)2006E.ccPKU 3010
FSecrets in Shadows☆☆☆☆★幾何・円と円の接線2006F.ccPKU 3011

2007 年

E を除いて易しいセット。E はおそらく国内予選の史上最難問題と思われます。A は国内予選最易。この年は特別に予選通過チームが多くなっていました。5問正解が4チーム。

問題問題名難易度解法・アルゴリズムソース備考
AICPC Score Totalizer Softwaread-hoc2007A.ccPKU 3325
BAnalyzing Login/Logout Records☆☆ad-hoc2007B.ccPKU 3326
CCut the Cake☆☆★ad-hoc2007C.ccPKU 3327
DCliff Climbing☆☆☆★ダイクストラ2007D.ccPKU 3328
ETwirl Around☆☆☆☆☆幾何・円と線分の交差判定2007E.ccPKU 3329
FDr. Podboq or: How We Became Asymmetric☆☆☆★DP あるいはキャッシュ付き再帰2007F.ccPKU 3330

2008 年

全問正解が3チームも出た年。F 以外は易しく、最難問題としての F は例年並。

おそらく来年は、難しい問題2題のレベルがあがるだろうと予想します。E が難しい問題のレベルとしては簡単すぎるため、F を解く時間を与えてしまっています。みんな確かに幾何は苦手です。しかし、、これぐらい単純だと苦にならないので、幾何問題として選手を苦しめるには至っていません。

問題問題名難易度解法・アルゴリズムソース備考
AEqual Total Scoresad-hoc2008A.cc
BMonday-Saturday Prime Factors☆★エラトステネスのふるい2008B.cc
CHow can I satisfy thee? Let me count the ways...☆☆構文解析2008C.cc
DTwirling Robot☆☆☆ダイクストラ2008D.cc
ERoll-A-Big-Ball☆☆☆★幾何・線分と線分の距離2008E.cc
FICPC: Intelligent Congruent Partition of Chocolate☆☆☆☆探索2008F.cc

2009 年

全問正解が1チーム。D は拡大グラフのダイクストラ、E は2部グラフの最大マッチングと、知識と経験がものをいう問題が並びました。5問以上正解は15チームもあるという、レベルの高い争いでした。5問正解しても予選落ちしたチームがついに東大以外からも出ました。上位陣向けに、中盤の問題をもう少し難しくしないとだめかも。F は幾何で難しそうなのだが、落ち着いて書いてみると意外とあっさりと書ける問題。F の解答ソースは長さが更新されるまでループということにしています。誤差がゆるいのでこれで大丈夫でしょうが、議論の余地はあるでしょう。

問題問題名難易度解法・アルゴリズムソース備考
ANext Mayorシミュレーション2009A.cc
BHow Many Islands?☆★ad-hoc2009B.cc
CVerbal Arithmetic☆☆dfs2009C.cc
DDiscrete Speed☆☆☆★ダイクストラ2009D.cc
ECards☆☆☆☆二部グラフの最大マッチング2009E.cc
FTighten Up!☆☆☆☆★幾何2009F.cc
2009-12-31

考えなければならないことを減らせる様に書く

次の3つのブログエントリがありました。

美しいプログラムの書き方についてですが、これをネタに何を考えながらコードを書くべきかについて議論します。

槍玉に挙がっているのは、次の3か条です。

  1. 変数のスコープは小さく抑える
  2. Do Not Repeat Yourself (DRYの原則) 同じコードは2度書くな
  3. 言語を極めよ

何人かは、それは「ケースバイケース」であると主張しましたし、それは間違っていません。しかし、ケースバイケースだと言うのは簡単ですが、それでは言われた方は何をしていいかわからず、結局そこから何も学ぶことができません。

そこで、このエントリでは、1つの指針を与えます。考えなければならないことを減らせるように書くということです。

変数のスコープは小さく抑える

変数のスコープを小さくすると、考えなければならないことを減らせます。変数が、そのスコープの中にしかないことは分かっているので、他を見る必要がないからです。

しかし、わざわざグローバルに参照できるところに変数をおくことで、考えなければならないことを減らせることもあります。もし、プログラムの様々な場所で、その変数に依存するような動作をするならば、きっとそれはグローバルにおくべきなのです。例えば、まれに変更される設定変数などが良い例です。ここで、グローバル変数と言っているのではなく、グローバルに参照できる変数と言っていることに注意してください。グローバル変数かもしれませんし、シングルトンの様なものかもしれません。

言語のいろんなパラダイム、例えば関数型言語やオブジェクト指向も、それぞれのやりかたで考えることを減らすのに成功しています。関数型言語は変数の書き換えを許さないことが多いですが、これは一度定義されてしまえばそれ以降変更されている箇所を探す必要がないという点で考えるべきことが少なくなっています。オブジェクト指向も、変数を変更できるのはオブジェクトのメソッドを通してのみ、ということになるためそのクラスのみを見ればよくなります。

Do Not Repeat Yourself (DRYの原則) 同じコードは2度書くな

これも、結局は考えることを減らすのに他なりません。しかし、これは*いつ考えるか*を減らすものです。

コピペコードは、その場で考えることを減らしています。しかし、後に変更をする場合には苦しむでしょう。これは思考を先送りにしていると考えることができます。これは、技術的負債に対応すると考えることができます。

同じコードを2度書かないようにするのは、今は苦しいかもしれません。しかし、上手く設計されたコードは純資産であり、将来考えるべきことを減らしてくれるでしょう。

言語を極めよ

これも、考えることを減らすことにほかなりません。言語はある程度極めて、息を吸うように記述できるぐらいでなければなりません。わざわざあれはどうかくんだっけ? と言語の機能を探すようでは、そちらに気を取られるばかりで必要なことを考える時間に支障がでるからです。

もちろん、極めるのは言語だけではだめで、アルゴリズムなどに関してもある程度は何も見ずに書けるようになっておく必要があります。

プログラムを書く以上、少なくとも一つの汎用言語をかなりの水準で極めておくべきです。できるだけモダンな奴が望ましいでしょう。関数型言語をおすすめしますが、C++でもJavaでも構いません。しかし、少なくとも一つの言語をきわめて置けば、新しい言語を学ぶときにも非常に役に立ちます。新しい言語のこの機能は、前にやった言語のあの機能とおなじ、というように覚えるべきことが少なくなっていくからです。

まとめ

将来無駄に考えなければならないようにならないかを今ちょっとだけ考えてからコードを書くのです。そして、余計なことを考えないでもよいように、考えなければならないことを減らすための投資をしましょう。それには言語の習得、アルゴリズムの習得など、様々な勉強が必要です。頑張りましょう。

2008-10-29

ACM-ICPC 国内予選 2008 年度

国内予選総評

2008 年度の国内予選は7月4日にインターネット上で行われ、およそ250チームが参加しました。試合時間は3時間。予選突破するためには、3問を素早く正解するか4問を解く必要がありました。例年3問解けばまずアジア地区予選に進出できていたことからすると、やや問題が例年より易しかったにせよ、選手のレベルが上昇しています。また、全問正解が3チームあり、上位層のレベルもあがっています。

以下、各問題を解説していきます。それぞれの問題に対して、難易度/目標時間/必要能力(実装力・数学力・知識)を示した後、問題の概要、そして問題の解説を行っています。

難易度は ☆ の数(最高5つ)で表しています。★は☆半分を表しています。

  • ☆の問題は、これを解けないようではもっと基礎的な部分を練習する必要があるような問題を表しています。
  • ☆☆の問題はアジア地区予選に出場するためには絶対に解かなければならない問題です。
  • ☆☆☆の問題がすべて解ければアジア地区予選に大学トップであればまず出場可能であるレベルを表しています。
  • ☆☆☆☆の問題は、上位を狙うならばぜひ解いてほしい問題です。
  • ☆☆☆☆☆は、まず時間内には解けない問題を表しています。

問題を解く目標時間は、問題を読み始めてからどれぐらいの時間で正解を出してほしいかと表しています。この目標時間は3段階に分けており、上位チーム/中位チーム/下位チーム向けの目標時間を記述しています。

問題を解く必要能力は、実装/数学/知識/応用の4つに分けて示しています。実装は実装のタフさを、数学は数学的知識を、知識はアルゴリズムの知識を、応用は必要とされるひらめきの力や基本的なアルゴリズムを適用することの難しさなどを表しています。

問題概要は、問題の概要を簡単にまとめて記述しています。

それでは、各問題の解説に入ります。おおよそ易しい問題ほど丁寧に解説してあり、問題に取り組む人のレベルに沿って解説してあるつもりです。

問題セットは、公式サイトから入手できます。

問題A Equal Total Scores

  • 難易:☆(大変易しい)
  • 目標:7分/10分/15分
  • 能力:実装1/数学1/知識1/応用1
  • 概要:太郎と花子に手札がそれぞれ n, m 枚与えられる。手札には点数がついており、太郎と花子の手札を一枚ずつ交換して二人の点数を等しくしたい。どの手札を交換すればよいか? 複数の交換方法がある場合、交換した手札の合計点が少なくなるものを選べ。

例年問題 A は非常に易しい問題が出題されます。これが一瞬で解けないようでは国内予選通過はままなりません。おおよその傾向ですが、問題 A は問題文に書いてあることをそのまま実装すれば良いようになっています。もし、問題 A が解けないようであれば、まず「どのようにすれば二人の手札の合計点を等しくなるようにできるか」を日本語で書き下してみることから始めましょう。

今回の場合、次のようになります。

  1. 太郎と花子の手札を読み込む
  2. それぞれの合計点を出す
  3. 太郎から手札を一枚、花子から手札を一枚選んで交換する
  4. 交換したときの太郎と花子の合計点を求める
  5. 等しければ解の候補。今まで解が出てなければそれを解とし、解が出ていれば交換した手札の合計が前に出た解よりか小さいかを確認し、小さければ解とする
  6. 選ぶ手札がなくなるまで 3 に戻って繰り返し
  7. 解が見つかれば解を表示。なければ -1 を表示。

まずこの作業をせずにプログラムを書こうとすると、問題 A が解けない様な初心者のうちは何を書いているのかわからなくなるでしょう。 問題 A がすらすらと解ける様になるまでは、まずこの作業をしてからそれをプログラムに直すようにしましょう。

では、これをプログラムに直していきます。ここでは STL を用いた C++ のコードを使って例示します。

まず、問題を読んでいる間に、手の空いた人がテンプレートコードを打ち込みます。

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

int main(void)
{
  // WRITE HERE
  return 0;
}

テンプレートを打ち込んで問題を理解したら実装の開始です。ICPC では入力/計算/出力がきれいに分かれることが多いので、私はいつも main 内で入力/出力を行い、計算部分は solve という名前の関数を作ってそこで計算を行っていました。ここでもそのように実装していきます。

太郎と花子の手札を読み込む

まず1行目に太郎と花子の手札の数 n, mが来ますので、それを読み込みます。

int n, m;
cin >> n >> m;

次に、太郎の手札が n 枚、花子の手札が m 枚来ますのでそれを読み込みます。読み込んだ手札を覚えておくために、配列、もしくは vector を用意します。

vector<int> tarou(n), hanako(m);
for (int i = 0; i < n; ++i) {
  cin >> tarou[i];
}
for (int i = 0; i < m; ++i) {
  cin >> hanako[i];
}

C++ であれば、特に速度を必要としない限りは vector を使った方が楽でしょう。(ただし、計算時間が厳しいと思ったときは普通の配列の方が速いことが多いので、普通の配列を使った方が良いでしょう。)

それぞれの合計点を出す

読み込んだ手札から、合計点を求めます。これは全ての手札の点数を足すだけなので簡単ですね。

int tarou_sum = 0, hanako_sum = 0;
for (int i = 0; i < n; ++i) {
  tarou_sum += tarou[i];
}
for (int i = 0; i < m; ++i) {
  hanako_sum += hanako[i];
}

もちろん、読み込むときに一緒に足してもかまいません。

太郎から手札を一枚、花子から手札を一枚選んで交換する

おそらく、初心者のうちはこういうところでつまるのではないかと思います。太郎の手札と花子の手札を全て列挙するには、二重ループを使う必要が有ります。

for (int i = 0; i < n; ++i) {
    // 太郎の i 番目の手札と
    for (int j = 0; j < m; ++j) {
        // 花子の j 番目の手札を選ぶ
        // ここに交換処理を書く
    }
}

これで、太郎の手札 tarou[i] と、花子の手札 hanako[j] が選ばれました。

交換したときの太郎と花子の合計点を求める

これはどうすれば良いでしょう? 太郎はもともと tarou_sum 点の手札を持っており、花子に tarou[i] をあげ、花子から hanako[j] をもらいました。従って、このときの太郎の点数は、tarou_sum - tarou[i] + hanako[j] です。花子も同様に hanako_sum - hanako[j] + tarou[i] です。

int tarou_changed_sum = tarou_sum - tarou[i] + hanako[j];
int hanako_changed_sum = hanako_sum - hanako[j] + tarou[i];

添字を間違わないように注意してください。

等しければ解の候補。今まで解が出てなければそれを解とし、解が出ていれば交換した手札の合計が前に出た解よりか小さいかを確認し、小さければ解とする

等しいかどうかをまずチェック。

if (tarou_changed_sum == hanako_changed_sum) {
  // 等しい
} else {
  // 等しくない
}

等しくない場合は、さっさと次にいきましょう。

continue;

等しい場合、今まで解が出ていたか、解が出ていたならば前に出た解より交換した手札の合計が低いかどうかを調べる必要が有ります。おっと、ここで解を覚えるための変数を用意してないことに気がつきました。ループの前に次を追加します。

bool found = false; // 見つかったら true にする。
int tarou_answer, hanako_answer; // 見つかったら答えをここに入れる。
それでは、等しい場合を書きましょう。
if (found) { // 解が見つかっていた
  if (tarou_answer + hanako_answer > tarou[i] + hanako[j]) {
    tarou_answer = tarou[i];
    hanako_answer = hanako[j];
  }
} else { // まだ見つかってなかった
  found = true
  tarou_answer = tarou[i];
  hanako_answer = hanako[j];
}

選ぶ手札がなくなるまで 3 に戻って繰り返し

これは3のループでもう書かれています。

解が見つかれば解を表示。なければ -1 を表示。

解があるかどうかは found に bool 値として入れておいたので、それをみれば良いはずです。

if (found) {
  cout << tarou_answer << ' ' << hanako_answer << endl;
} else {
  cout << -1 << endl;
}

さて、これではデータセット1つに対してしか解答していませんので、while でデータの終了が来るまでまわします。

while (true) {
  // n, m の読み込み
  if (n == 0 && m == 0) { break; }
  // それ以降
}

これでプログラムは終わりです。これをコンパイルして実行してみましょう。コマンドラインが使える人は

$ g++ A.cc
$ ./a.out < in.a

の様に、サンプルインプットを in.a として保存してそれを与えましょう。eclipse などの統合環境を使っている人は各自のやりかたでコンパイルしてください。Java などは eclipse であれば補完が効きますから、eclipse で記述するのをお勧めしますが、コンパイル + 実行はコマンドラインの方が速いと思います。

プログラムを書いたら、必ずサンプルインプットを与えてただしい出力がなされているかを確認してください。

慣れるまで、何度も同じ問題を解いてみてください。答えを覚えてしまってもかまいません。むしろ、覚えるぐらいまで解いてしまった方が良いでしょう。はじめのうちは、そのようにした方が早く実力がつくと思います。

問題 B: Monday-Saturday Prime Factors

  • 難易:☆★(易しい)
  • 目標:10分/15分/30分
  • 能力:実装2/数学2/知識2/応用2
  • 概要:7で割って 1 または 6 あまる自然数を考える。これを月曜土曜数と呼ぶ。1以外の月曜土曜数が、ほかの月曜土曜数で割れないとき、月曜土曜素数と呼ぶ。月曜土曜数が与えられたとき、それを割ることが出来る月曜土曜素数を全て出力しなさい。

問題 A よりは少し手強くなっています。なんとなく数学が絡んできて一瞬嫌な感じの問題に見えるかもしれませんが難しいものでは有りません。なんとなく難しそうな問題も、「簡単な小さな問題に分けて考える」と理解しやすくなり、またプログラムを書く上でも楽になります。簡単な問題に分ける場合、「どうやって作るかまだわからないけど、これがあったら後の計算が楽になる」というものを考えてみるのが得策です。この場合、もし「月曜土曜素数表が与えられていたら」どうするか? 素数を一つずつ試していって、与えられた数を割ることが出来るかどうかをチェックし、それを出力するだけですよね? つまり、もし月曜土曜素数表が小さい順に

vector<int> msprimes;

で与えられていたら、与えられた数 n に対して、

for (int i = 0; i < msprimes.size() && msprimes[i] < n; ++i) {
  if (n % msprimes[i] == 0) {
    cout << ' ' << msprimes[i];
  }
}

とやれば OK です。ということは、msprimes をどうやって作るかをうんうんうなって考えだせば良い訳です。

素数を求めるアルゴリズムといえば、エラトステネスのふるいが定石です。今回も、適用の仕方が少し違うだけで、同様に記述することが出来ます。今回の場合、「月曜土曜数 a が月曜土曜数 b の月曜土曜約数であるためには、a が b の普通の意味の約数であれば必要十分であると, 簡単に証明できる」という一文が問題文のなかにあり、これは結局 b をa で普通に割ってみて、割りきれたら a は b の月曜土曜約数である、ということを言っており、よけいなことを考えなくてもよくなっています。従って、月曜土曜素数版のエラトステネスのふるいは、次のように書けます。

vector<bool> p(300000, true);
p[0] = p[1] = false;
for (int i = 2; i < 300000; ++i) {
  if (i % 7 != 1 && i % 7 != 6) {
    continue;
  }
  if (!p[i]) { continue; }
  for (int k=2*i; k<300000; k += i) {
    p[k] = false;
  }
}

基本的に殆ど一緒で、月曜土曜数のみを扱うようになっています。少し無駄な処理がありますが、特に問題ない量なので、本番ではこのようにある程度書きやすさを優先させても良いと思います。

問題 C: How can I satisfy thee? Let me count the ways…

  • 難易:☆☆(やや易しい)
  • 目標:17分/30分/60分
  • 能力:実装3/数学1/知識2/応用2
  • 概要:真・偽・不明の3つの値を変数が取る。論理式が与えられたとき、その論理式の値が真になるような、変数の値の取り方の総数を求めよ。ただし、変数は P, Q, R しかない。

どちらかというと構文解析の問題。構文解析は ICPC アジア予選レベルでは頻出ですが、国内予選でもついに出てきました。ICPC で出てくる構文解析は難しいものではなく、再帰がちゃんと書ければ出来ます。アジア予選レベルではちょっと考えないとかけない問題も出ますが、今回の問題は素直に実装出来ます。

今回の問題は、P, Q, R が 0, 1, 2 のどれかしかとりません。構文解析の問題は、構文解析して構文木を作ってから変数に値を入れて実際に評価した方が良い場合と、構文解析と式の評価を同時にした方が良い場合があります。変数に入れる値の範囲が広い場合は前者の方が良いでしょうが、今回は最大 3 * 3 * 3 = 27 通りしかないので、P, Q, R をそれぞれの値で初期化してから構文解析と評価を同時に行った方が楽に記述出来ると思います。

さて、構文解析ですが、これは再帰に慣れた人なら楽に記述出来ますが慣れていないと難しいでしょう。慣れてない人は再帰についてこの機会になれることを勧めます。再帰は「信念」さえあれば書けます。それでは、再帰を書くための信念を身につけましょう。

int eval(const string& s, int& pos)

を、pos から始まる構文を解析して評価した値を返し、pos を構文の最後まで進める関数である、と思ってください。eval は、どう実装されているかわからないけど、とにかく今はそんな関数なのです。そう「信じてください」。つまり、eval は、式が

((2*2)+0)

だったら、pos が 0 のときは全てを構文解析評価して2を返して pos を 9 にし (すべての式を評価して pos を最後まで進める)、pos が 1 だったら、そこから始まる構文である (2*2) だけを解析して 2 を返して pos を 6 にする (+の位置まで pos を進める)、そんな関数であると「信じてください」。再帰はこの信じる心が重要です。そして、この「信じた関数を使ってない部分は信じた関数と同じ動きをする」ように記述していけば再帰はかけてしまうのです。

さて、そう信じたら、まず「再帰が必要ないところから」書き始めます。eval といういまよくわからない関数を使わなくても簡単に書けるところからスタートします。今回の文法を見ると、0, 1, 2 が来たら値はそのまま 0, 1, 2 を返します。これだったら書けますよね? 信じた関数と同じになるように、pos は読み込んだ後まですすめ、値をちゃんと返すようにします。

if (s[pos]=='0') { ++pos; return 0; }
if (s[pos]=='1') { ++pos; return 1; }
if (s[pos]=='2') { ++pos; return 2; }

とりあえず、これだけで済みます。これを eval の最初の方に書いておきます。

int eval(const string& s, int& pos)
{
  if (s[pos] == '0') {
    ++pos; return 0;
  }
  if (s[pos] == '1') {
    ++pos; return 1;
  }
  if (s[pos] == '2') {
    ++pos; return 2;
  }
  // ...
}

あと文法を見ると、マイナス、かけ算、足し算が残っています。マイナスは expr が1回しか出てないのでこれから始めましょう。マイナスは、最初がマイナスで、そのあと expr がくると書いてあります。なので、まず最初が - であるかどうか調べます。

if (s[pos] == '-') {
  ++pos;
  // ...
}

マイナスの符号を読んだら、pos を進めておくのを忘れないように。さて、次は expr ですが、ここで魔法を登場させます。eval は、初めに「信じたように」pos から始まる構文を解析して、値を返し、pos を構文の終わりまで持っていってくれる関数なのです。それを信じて使います。つまり、expr の構文解析と評価は eval がやってくれるのであとはそれに任せてしまうのです。マイナスは、0 なら 2 を、1 なら 1 を、2 なら 0 を返すので、eval を読んで得られた値を 2 からひけば良いでしょう。

if (s[pos] == '-') {
  ++pos;
  int v = eval(s, pos);
  return 2 - v;
}

これでマイナス部分が書けました。同様に + と * についても expr が出来たら同じように信じた eval を使って記述します。+, * に関しては、よく見ると a + b の値は a, b の大きい方、a * b は (a * b + 1) / 2 で書けてしまうのでそれを使っています。もしこの規則がわからなかった場合は、一つずつ (0 + 0) は 0, (0 + 1) は 1, というように全ての場合を記述してください。

if (s[pos] == '(') {
  int a = eval(s, pos);
  // pos は expr を読んだ後のはずなので、今は符号をさしているはずだ
  char c = s[pos++];
  int b = eval(s, pos);
  if (c == '*') { return (a * b + 1) / 2; }
  if (c == '+') { return max(a, b); }
  abort(); // ここの動作は定義されてないので、とりあえず abort しておく。
}

これで与えられた式が全て記述出来ました。実はこれで最初信じた eval が出来上がっています。実際に動かしてみましょう。

このように、再帰は最初に「関数が何をするのかを決めて」、再帰を書いている間はずっと「その関数は決めたことをしているものだ」と信じ、「それを使って条件一つずつを書いていく」ようにすればよいのです。

しばらくは練習が必要ですが、再帰を上手に書ける様になるととたんにプログラミングが上達します。しばらく練習しましょう。

問題 D: Twirling Robot

  • 難易:☆☆☆(標準)
  • 目標:30分/50分/120分
  • 能力:実装3/数学1/知識3/応用3
  • 概要:ロボットをスタートからゴールまで動かすときの最小のコストを求めよ。コストはロボットに与える命令で決定される。途中の道には標準の命令が書いてありこれはコスト0である。これを上書きするとき、命令に応じたコストがかかる。

ゴールまで行く最短コストを求める問題。いくつか解く方法はありますが、ここは素直にダイクストラのアルゴリズムを用いて解きたいところ。ダイクストラのアルゴリズムは、プログラムを書く人にとって「絶対に知っておかなければならない」知識の一つです。なるべく早く身に付けましょう。

ダイクストラのアルゴリズムとは、負のコストがないグラフが与えられたときに指定された開始点から各点までの最短路およびそのコストを求めるアルゴリズムで、ICPC では非常に良く使うアルゴリズムです。易しい問題ではダイクストラのアルゴリズムをそのまま適用すれば答えが出るものもありますが、グラフの作り方を少しひねらせる問題もよく出ます。グラフの頂点がいくつかの状態を取る場合に頂点を分割してその状態全てを頂点とみなすようなグラフを作ってからダイクストラのアルゴリズムを使う、という出題形式が多いように思われます。

今回の問題の場合、上下左右のどちらを向いているかで頂点を4つに分割したグラフ(これをもとのグラフを拡大したという意味で拡大グラフという)を作って、ダイクストラのアルゴリズムを使えば良いでしょう。ロボットへの命令を枝とし、そのコストは標準の命令であれば0、そうでなければ、命令に応じたコストを枝のコストとします。

問題E Roll-A-Big-Ball

  • 難易: ☆☆☆★(やや難しい)
  • 目標:45分/90分/解けなくてよい
  • 能力:実装2/数学3/知識4/応用3
  • 概要:グラウンドに引かれたコース(直線)に沿って大玉を転がす。障害物にあたらないような大玉の最大の大きさを求めよ。

幾何問題は例年1題は出題されますが、幾何問題は「ライブラリがものを言う」問題です。幾何のライブラリは豊富に用意しておきましょう。今回は線分と線分の距離を求めることさえ出来れば容易に解ける問題です。

今回の問題の場合、障害物の壁部分を線分として、スタートからゴールまで行く線分との距離を求めます。壁の高さ h とその距離 d に対して、最大の玉の大きさを求め、その最小値が答えとなります。最大の玉の大きさは次の様のして求められます。

d < h の場合: かべまでの距離が最大の玉の大きさなので d。

d >= h の場合、図を書いて方程式をたててしらべます。
三平方の定理より r2 = (r - h)2 + d2
従って、r = (h2 + d2) / 2h

なお、最初に既に障害物の中にした場合は、場合分けして答えを 0 とします。

問題は距離 d をどうやって求めるか、ですが、点と線分の距離のライブラリを持っていれば、線分と線分の距離は、両端の点ともう一つの線分の距離を求め、反対側も同じことをすれば OK というのはすぐにわかるでしょう。線分同士が交差している場合は別に判定し、距離を 0 としておきます。

最後に、許容誤差が指定されているので注意して出力します。

問題 F. ICPC: Intelligent Congruent Partition of Chocolate

  • 難易: ☆☆☆☆(やや難しい)
  • 目標:80分/解けなくてよい/解けなくてよい
  • 能力:実装4/数学2/知識3/応用4
  • 概要:正方形のチョコレートをつなげてできた板チョコレートを合同に2つに分けられるかどうか答えよ。ただし分けられたチョコレートは連結でなければならず、また正方形チョコレートを2つにわってはならない。

やや難しいが解ける問題。東大予選を戦うのでもない限り国内予選では解かなくても良いでしょうが、アジア予選では解いておきたい程度の問題です。この問題は基本的には2つにチョコレートを分けて合同判定を行う全探索を書けば OK です。チョコレートを分けるときは、切り取り線を入れるようにして切り取り線が交差しないように分けると、切り取られた2つのピースは連結になっています。あるいは、一つ端の正方形チョコレートを決めてそれを含むように一方のチョコレートを決めて、それと他方のチョコレートを比較するという方法でも大丈夫でしょう。

そうしてチョコレートが2つに分けられたら、あとは一方のチョコレートを反転したり回転したりして8通り生成し、比較します。

ソースコード

解答例を tgz で配布しています。公式の output と答え合わせをしています。

2008-07-10