日本の ICPC の幾何問題は、世界のそれと比べてレベルが高いという話を聞いたことがあります。
日本が幾何を得意としているのかどうか私には分かりかねますが、ここでふと、パソコン甲子園にも面白い幾何の問題があったことを思い出しました。
今日はパソコン甲子園2005本選問題28「ケーキ屋」を紹介しましょう。

問題はパソコン甲子園公式サイトの例題ページにて公開されていますが、こちらにも転載します。

ケーキ屋さんが、まちまちな大きさのロールケーキをたくさん作りました。 あなたは、このケーキを箱に並べる仕事を任されました。 ロールケーキはとてもやわらかいので、他のロールケーキが上に乗るとつぶれてしまいます。 ですから、全てのロールケーキは必ず箱の底面に接しているように並べなければなりません。 並べ替えると必要な幅も変わります。

ファイルから、n個のロールケーキの半径・・・・・・・・と箱の長さを読み込み、それぞれについて、箱の中にうまく収まるかどうか判定し、並べる順番を工夫すると箱に入る場合は "OK"、どう並べても入らない場合には "NA" を出力して終了するプログラムを作成してください。
ロールケーキの断面は円であり、箱の壁の高さは十分に高いものとします。 ただし、ロールケーキの半径は3以上10以下の整数とします。 つまり、ケーキの半径に極端な差はなく、図 (b) のように大きなケーキの間に小さなケーキがはまり込んでしまうことはありません。 また、ケーキの個数 n は12個以下とします。

http://www.pref.fukushima.jp/pc-concours/2007/03/pdf/2005honsen.pdf

某所からの「Codelogy にエントリを投稿しろ」という圧力が大きくなってきたので、自作の XML ライブラリでも紹介してお茶を濁そうかと思います。 とは言っても、業務に使用しているものなので、ちゃんと使えるレベルには仕上がっています。

前回のエントリ では、副作用を分離することで、バグを減らすことができる、という話から、Haskell がそのような副作用の分離に向いているということについて書きました。
今回は、IO 制御の分離について、Haskell のコード 2 つを比較しながら書いてみようと思います。

「一番好きなソートアルゴリズムは何ですか？」
この質問に対する回答により、人間は以下のように分類することができます。

クイックソート

→ 何をおいてもパフォーマンスだろ派

マージソート

→ エレガントなアルゴリズムが好きです派

選択ソート

→ 簡単に書けるのがいいよ派

ボゴソート

→ いくらなんでもひねくれすぎです。

……という冗談はさておき、今回は私が使用しているソート (クイックソートの変種) を紹介します。

1. 一般的なソートアルゴリズムの問題点

この間のインタプリタをはじめから・・・で問題がありご指摘を受けました。
ですので次回より修正を行い、今回は GPGPU を使った計算についてやりたいと思います。

今回 nVidia の GeForce 8800 GTX というボードが手に入りましたので、専用の言語 （現在 GF8x 系のみで動作可能） であるCUDAを利用したいと思います。