情報学ジャーナル■ 講演録 ■

Vol.5, No.3, February 2012, pp.1-15
ISSN 2185-6850

特集・情報がもたらすビッグバン 講演会

プログラミングの楽しさとACM 国際大学対抗プログラミングコンテスト
ACM 国際大学対抗プログラミングコンテスト 世界大会出場チームコーチ 今道 貴司

概要

文教大学情報学研究科主催「情報がもたらすビックバン」連続講演会の 1 回目として、ACM

国際大学対抗プログラミングコンテストの世界大会出場チームコーチをつとめる講演者が、プログラミ
ングとはどういうものか、次いで、自身がプログラミングでどういう研究をしているか、最後に、プログラミングコンテストはどのように行われているかについて、質疑応答を交えながら講演を行った、講演録である。(1) プログラミングとは何か、その意義と楽しみ、アルゴリズムの重要性などについて解説した。(2) 講演者の専門とする「組合せ最適化」の中から、特に図形の配置問題、充填問題について解説を行った。(3) プログラミングのコンテストにはどのようなものがあるかを挙げた上で、ACM 国際大学
対抗プログラミングコンテストについて紹介し、さらに参加した時の世界大会に参加したときの体験について述べた。

（2012 年 2 月 1 日受付）

文教大学大学院 情報学研究科〒 253-8550 神奈川県茅ヶ崎市行谷 1100
Tel 0467-53-2111(代表)，Fax 0467-54-3724
http://www.bunkyo.ac.jp/faculty/gs-info/

情報学ジャーナル Vol.5, No.3 (2012) pp.1-15

今道 プログラミングの楽しさ

情報学研究科「情報がもたらすビックバン」連続講演会

講演録

プログラミングの楽しさと ACM 国際大学対抗プログラミングコンテスト
ACM 国際大学対抗プログラミングコンテスト 世界大会出場チームコーチ 今道貴司

今道 ご紹介ありがとうございました。日本 IBM の今道です。今日はプログラミングの楽しさを伝えるような、おもしろい講演をしてくださいというふうにお願いされまして、普段こういうちょっと柔らかいタイプの講演はあまりしないのでちょっと緊張しているのですが宜しくお願い致します。
最初に自己紹介をしたいと思います。現在私は日本 IBM の東京基礎研究所で働いています。仕事としては最適化関係の仕事を専門として、研究としてやっています。その中でも特に私がやっているのは図形配置問題といって、ここに 2 つ絵を持ってきて、あとで紹介もするのですが、この上にあるのはたんぱく質ですね、このたんぱく質を立方体の容器にぎゅうぎゅう詰めにしたというような絵で、下の絵は日本地図があってこれを 10 枚、北海
道、本州、四国、九州とあるのですが、10 枚ずつ用意して、長方形の容器の中に詰めたという絵ですけれど、こんな感じで、コンピューターを使っておもしろい図形の配置を求めたいというのをやっています。
コンピューターとのつきあいは私の場合は非常に長くて、何で好きになったかというのは自分でもよくわからないんですけど、プログラミング歴というのは、私は今年もうすぐ30 になるのですが、だいたい小学校 6 年生くらいからプログラミングを始めて、もう 17年。コンテストというのもプログラミングを始めてだいたい同じくらいに参加するようになって、プログラミングのコンテストだけではないのですが、中学 1 年生の頃から 16 年く
らいいろんなコンテストに出てという感じですね。こんな感じでプログラミングを楽しんで今まで生きてきた。楽しんでいるだけでなく実際にそれを仕事にして研究もしてやっています。
連(※講演の出席者) はじめてさわった言語は何ですか？
今道
昔は PC98 っていう NEC が出したパソコンは何にもディスクとか何にも入れなくてもスイッチを入れただけでベーシックが起動するんです。それで遊んでたんですよね。
ゲームとか持ってないので、ゲームもプログラムも全部暗記して、パソコンを起動して打ち込んで暗記してゲームを、で遊ぶっていうのをやっていました。なぜかそういうのが、コンピューターに憧れて今までずっときたっていう感じです。
これが自己紹介で、今日のお話の内容ですけど、主に３つ、最初にプログラミングとはどういうものかっていうのを簡単に紹介して、その後、私が普段やっている研究の話、プログラミングでどういう研究をしているのかっていうのを紹介していきます。さっきもち
ょっと出ましたけど、図形の配置問題、充填問題をやっている様子を映したいと思います。
その後に、プログラミングのコンテストの紹介というので、その中でも特に世界大会に選手でなくコーチとして行ったりと、今日は ACM 国際大学対抗プログラミングコンテストの1

情報学ジャーナル Vol.5, No.3 (2012) pp.1-15

今道 プログラミングの楽しさ

紹介と、あと、参加した時の世界大会の様子を紹介したいと思います。ちょっと雰囲気を味わってもらえたらな、と思ってます。宜しくお願い致します。

プログラミングとは何か
最初に、プログラミングとは何だろうというので、この企画を頂いた時にちょっと考えてみたんですけど、ウィキペディアから持ってきた内容によると、プログラミングとは「プログラムを作成することによって人間の意図した処理を行うようにコンピューターに指示を与える行為」だと。要はコンピューターを人間が思ったとおりに動かそうというのがプ
ログラミングです。
コンピューターというのは今の世の中あちこちにあふれています。コンピューターがな
いようなものっていうのもかなり少なくなったんじゃないかなって思うくらい色々なもの
がコンピューターによって構成されています。例えば、小さなものだと携帯電話のようなものもあれば普通のパソコンもありますし、大きいものだとスーパーコンピューターというのがあって、色んなものがコンピューターで使われています。これらは当然コンピュー
ターでプログラムがなければ動かないので、プログラミングというのがなければただの塊でしかない。
プログラミングっていうのはひとつその世の中を支える技術、重要な技術であるというような真面目な話もあるのですが、実際そういう固い話は抜きにして、では何が楽しいの
か、ちょっと考えてみました。
さっき話もしたのですけど、今、色んなものにコンピューターが入っていて、実際にそのプログラミングっていうのはそれを動かすための道具なので、プログラミングができると何が嬉しいかいうと、まず色んな機械を制御することができる。最近だと、掃除機みた
いなやつでも小さいコンピューターがあって人間がプログラミングして動かすこともできるものもあるらしいと聞いてますし、実際そういうふうに機械を制御することができる。
また、さっきちょっと話を聞いたんですけど、ゲームを作ることができる。さっきシュー
ティングゲームを作る話を聞きましたが、色んなゲームを作って実際自分で遊んだり、人で遊ばしたりすることができる。実際ゲームというのは非常に大きい産業になっています、
特に日本では。で、遊ぶだけでなくて、便利なツールも作ることができて、ワープロを作
ったりというのは大変ですけども、例えば実験で使うようなツールを作るというようなのは割とよくやるようなことですし、そういったプログラミングができると自分にとって便利なものを作ることができる。これもひとつの楽しみです。
私が一番プログラミングで楽しいなと思っているのは、好きな計算をすることができる。
コンピューターっていうのは、計算をする為のもので、これを使うとどんな計算でも一応することができる。
一昔前っていうかコンピューターがない時代は、計算をするっていうのは非常に大変なもので、例えば、ひとつ逸話を持ってきたのですが、ドイツの数学者、ルドルフ・ファン・
コイレンという人は円周率を計算していました。しかも生涯かけて円周率の計算をしていたんですよ。でも全生涯かけて求めた円周率は 35 ケタ。すごい大変なんですね。35 ケタなのに生涯かけるくらい大変で、計算っていうのは大変で、当然、手でやるのでちゃんと正
しいかどうかも検算してやらなくちゃいけないので大変なんですね。で、昔の円周率の結果とかみると、何桁目から間違ってましたみたいなのが後で判明することもあるわけです。
ところが、今は非常に高性能なパソコンがあるので、普通のパソコンであっても 100 万桁くらいの計算だったら簡単にできますし、最近の円周率の世界記録ははっきりとは覚え

2

情報学ジャーナル Vol.5, No.3 (2012) pp.1-15

今道 プログラミングの楽しさてないですけど確か普通のパソコンにちょっとハードディスクとかメモリを強化したようなものを使って計算をしたっていうふうに聞いてますので、そういうふうに通常のパソコンを使って、昔だったらあり得ないような計算ができるようになったと。またそれがすごいなっていうのでぼくはそれが好きなんです。
さっきもでましたけれど、コンピューターの性能っていうのは今年々向上していて、可能性っていうのは広がっているんですね。携帯電話に入っているような小さいコンピューターであっても、下手したら一昔前のスーパーコンピューターくらいの性能はあるようなものも今はあるかもしれませんし、今コンピューターってのは直接筐体を買ってこなくてもクラウドコンピューティングといって、例えばアマゾンとかのコンピューターを簡単に借りることができる、クレジットカードひとつあれば。割と高性能のものであっても。そういうふうにして、本当にコンピューターで計算をするってのは手軽になっている。プロ
グラミングっていうのを非常に楽しむことができる環境になっています。
もちろん楽しいことだけでなくて、プログラミングには苦労も伴います。じゃあ何が大変かって一番大変なのは意図したとおりに動かすのは、意図したとおりのプログラムを作るのは難しいんですね。まず何が大変かっていうと、こんなことさせたいなってアイデアはあるんですけども、そのアイデアはちゃんと詰めて、最後まで詰めておかないと、ざっ
くりした状態のアイデアだとだいたい内部に矛盾を含んでいるかもしれないので、実装してみると何かうまくいかないなっていうのが、内部の論理が矛盾を含んでいると当然うまくいきません。ちゃんとアイデアが詰めてあっても実際プログラムを書くっていうのはな
かなか手間がかかるので、うっかりミスが紛れ込んだりすると当然動きません。
たぶん、そういう経験はよくあるんじゃないですか。よくある話で、特にこのどっちがっていうのが大変で、ここら辺の苦労っていうのはプログラミングによって時にはやめた
いなっていうこともあるくらいの苦労です。意図したとおりに動かすのが難しいだけでな
くて、意図したとおりには動くのだけど、ものすごく効率が悪い。簡単に言うと、計算に時間がかかるっていうのも結構あるんですね。
ここはアルゴリズムが重要っていうので次のページにいくんですけども、いかにその効率のよい手順を考えてやるかっていうのがポイントになります。もちろんそういう苦労はあるのですが、こういう苦労があるからこそこのプログラミングっていうのはプログラムが期待したとおりに動いた時に達成感が非常に大きくて、ぼくなんかはうまいこと行った
時に嬉しくなる、っていうような感じです。
アルゴリズムっていうのがさっきあったんですけども、これは必ずしもコンピューターと直結しているわけではなくて、これは基本的には問題を解くための手順、何かその与えられた課題を解くための手順ですね。このアルゴリズムっていうのはいかに効率的な手順を考案できるかっていうのが重要で、同じことをするにもより少ない手順でできるような、その手順を考えてあげることが重要です。
これはコンピューターの可能性を広げるポイントになっていて、コンピューターってい
うのはムーアの法則に従ってトランジスタの数がどんどん増えていって性能も向上しています。でも、それだけではコンピューターの可能性を広げるには足らなくて、人間が知恵をしぼってコンピューターの性能を引き出すようなそういう優れた手順を考えること、ア
ルゴリズムを考えてあげる必要があるのですね。
実際に今、人類はそういう苦労という努力をしているので色々成果が出ていて、例えば将棋や囲碁というのは、一昔前にチェスで IBM のディープブルーが世界チャンピオンを破って、そういう時はまだ囲碁や将棋っていうのはまだまだ弱い状態だったのですけど、昨3

情報学ジャーナル Vol.5, No.3 (2012) pp.1-15

今道 プログラミングの楽しさ

今だと将棋や囲碁っていうのは結構強くなっていて、実際に将棋のプロと勝負をするような状態になっています。これも当然コンピューターの性能が上がっただけでなくてアルゴ
リズムがすごい進化したからこそここに達成、今の現状があってまたさらに未来もあるという状態です。
また、違うネタですが、これは最近、今年の 2 月にあった話なんですけれども、「ジョパ
ディ」っていうアメリカで人気のあるクイズ番組があるんですけど、もう何十年も続いている。その番組で、IBM のワトソンていうコンピューターシステムがあるんですが、それが世界チャンピオンの 2 人に勝利したっていうような出来事がありました。クイズを理解して答えを出すっていう、ちょっと将棋や囲碁というゲームとはまた違う難しさ、自然言語処理の難しさとか色々あるんですが、そういうのを含んだものであっても人間を凌ぐことができたっていうのでひとつの大きな出来事でした。これもそのコンピューターの性能がよくなっただけで達成したわけではなくて、自然言語処理やデータマイニングの優れたアルゴリズムが考案されたことも大切でした。
これはそのクイズ番組の 1 シーンなんですけど、この真ん中にいるのがワトソンのシス
テム、実際には裏にでかいコンピューターがあって、それはアバターっていわれる表に出ている部分なんですが、こういうふうになってます。
アルゴリズムの実際の例っていうので、ちょっとこの例はみなさんには簡単すぎるかもしれませんが、数の整列を持ってきました。1 から N まで書かれたカードがあって、それがランダムになって切られています。それを昇順に整列しまして、普通の方法って書いてあるんですけど、挿入ソートという言われる方法でやると、そのカードの山、その中から一番小さいカードを選んできて、それをどこかに新しい山として置きます。その残った山からまた次に 2 番目に小さい、その残った山の中で 2 番目に小さいカードを選んで、さっき置いたカードの上に置きます。それを繰り返すことによってその山が整列された状態になるんですね。これが挿入ソートっていうもので、これはだいたい N の 2 乗くらいの手順が必要になります。
速い方法でクイックソートっていうのがひとつ例でありまして、カードの山から、これはさっき１枚ずつ最初の山から選んでいったんですけど、適当にカードの山から１枚選んでやって、その選んだカードの番号と山を比べてやって、そのカードの番号より小さいカードと大きいカードの山っていうのに 2 つのカードの山に分けてやる。分けたカードの中でまた同じことを繰り返すっていうのをやるとだいたい N log N くらいの手順でできて、実際どれくらいこの手順の数が変わってくるかというと、このグラフが書いてあるんです
けど、下の赤い線がこの下の早い方法で、上の青い線が普通の方法です。カードの数が X、横軸になってるんですけど、どんどんカードの数が増えるにしたがってここの差が、手順の数がどんどん差が開いていく。いかに同じことをやりたいにもかかわらず、その手順、良い手順を効率の良い手順を考えてやることによって、その必要となる手順の数っていうのが変わってくるわけです。だから、いくらコンピューターの性能が上がるって言ってもそこに期待するだけでなく、いかに良い手順を見つけてやるかというのがひとつ努力する
価値があるポイントなんです。

私の取り組んでいる研究そんな中、私がどんな研究をやっているかっていうのを、ここから紹介したいと思います。私が取り組んでいる分野というのは「組合せ最適化」という分野で、求めたいものっ
ていうのは何かしらの順序であったり、割り当てのような組合せ構造を持つような最適化

4

情報学ジャーナル Vol.5, No.3 (2012) pp.1-15

今道 プログラミングの楽しさ

問題、一番良い順序とか一番良い割り当てを見つけてくるような問題です。
例えば最短路の問題っていうのはたぶん授業か何かでやったと思うんですけど、A 地点から B 地点に行くような、一番移動時間が短くなるような道を見つけてくださいっていうもので、これは道路の組合せ、最も良い道路の組合せを見つけていくというような問題です。
そういうふうな組合せ構造というようなものです。この組合せ最適化の中では効率的にことができないというふうに信じられている。効率的というのは細かいことは言わないんですけれど、それなりに実用的な時間内に解くことができないというふうに信じられている問題の種類があります。ここで解くことができないというのは最適なものを求めることができないという意味なんですけれども、そういう問題があります。そういう問題に対して、この分野で色々アプローチがあって、おおまかに 2 つあるのですが、ひとつは厳密解法というので、全ての解の組合せを試してやって、その中で一番良いものを見つけてやる、当然一番良い答えが見つかるんですが、効率的に解くことはできない、時間がかかる。ただし、問題の特徴をうまく利用して試す組合せの数を減らすという努力をするんです。これはちょっと次のチャートで出ます。
もう 1 個は近似解法というもので、これはもう最適なものを見つけるのはちょっとあき
らめようというもので、そのかわり理論的に最適解からのずれを保証してやろうという話もありますし、後は実験的な手法っていうのもあって、実験的にそれなりに答えを出すっていう手法もあって、こっちの話が後でまた出ます。ここは代表的なものには遺伝的アル
ゴリズムというのがあります。ここで紹介する研究の 1 つなんですが、矩形のストリップ
パッキングといわれるものです。これはどういう問題かというと、このような容器と長方形の集合が与えられている問題です。これは、この容器っていうのは、幅のここは固定なんですけど上が空いている状態になっています。この与えられた長方形をこういうふうに配置してやって、こんな感じになんですけれど、その時にこの高さですね、必要と高さっていうのを、最も高さを最小化するっていう問題がストリップパッキングっていわれる問題です。この問題は応用として VLSI の設計であったり、あとは紙などのロール状の材料から部品を切り出す、そういう応用がある問題です。それに対して私たちのグループでは厳密な解法を求める研究をしています。内容を紹介しようと思います。
基本的には１枚ずつ長方形を置いていって全てのパターンを試すっていうのが基本戦略
なんですけれど、どういうふうに長方形を置くかっていうことを説明したいと思います。
今は途中段階でもう数枚すでに長方形が置かれている状態を考えます。それがこの絵だと思ってください。こんな感じで４枚長方形が置いてある状態の時にエンベロープというものを定義してやります。それがどういうものかというと、置いてある長方形と置いてない部分の階段状の境界をエンベロープというふうに呼んでやるんですけれど、その際に階段状なので角がこのように４点あるんですが、この角のどこかに新しい長方形を１枚置いてやる。そうやって新しい配置を作るというのをやるんですけれど。そうすることによって、
実は全ての長方形の配置を試すことができるっていうのを示すことができます。
さらに実行可能解は、これは専門用語なんですが、ここでは配置のことですね。今この高さを最小化するっていう問題を考えていたんですけれど、今この高さ H っていうのを適当な高さで固定してやって、この高さの中に長方形が入るかどうかを判定するっていう問
題を考えます。その際に実際にここの高さを固定してやった時に、そこに入る長方形の配置があるかどうかっていうのを高速に見つけることができるっていうのがこの部分なんですけれども、実際ほとんど長方形の配置っていうのは、ここの途中段階の階段も段数っていうのが非常に少なくなるっていう特性があるので、それを利用してここの段数を制限す5

情報学ジャーナル Vol.5, No.3 (2012) pp.1-15

今道 プログラミングの楽しさるっていうのはヒューリスティック、発見的手法っていうのが有効です。
実際にどういうふうな感じで進むかっていうと、こんな感じの空の長方形からはじまって、ここにまだ置いていない長方形を 1 枚置いてやるっていう 6 つの状態ができます。1、2、ここは長方形の番号だと思って下さい。そうすると１枚長方形を置くといま角が１個だ
ったのが角が２個になってこんな感じの階段があるんですが、ここに角があるのでそこに新しい長方形を１枚置いて、こんな感じでどんどん新しい状態を作っていくというのを繰り返すことによって、全ての配置を試すことができます。ただここで１個問題になってくるのは、今ここに１置いて２をここに置いて上に 3 を置いた状態がここにあるのですが、実は別のルートからも行くことができて、１置いて上に３を置いて横に２を置くっていうことができるんですね。今までは適当に角があるからっていって全部試してしまうと同じ配置を何度もチェックすることになるんですね。そういうふうに無駄があるのでそれを除く方法っていう効率的な方法を考える必要があります。その方法を紹介したいと思います。
どういうことをやるかっていうと、新しい長方形を置いた、配置ってのができると、その配置に対して親っていうのを定義してやります。親子関係っていうのを定義してやります。親子関係をどういうふうに定義するかっていうのは次のチャートですけれど、例えばこれの親はこれですよっていうふうな親子関係を 1 に決めてやると、これとそれからのこの配置を作ってやると、これとこれが親子関係にならない、今これとこれが親子関係、これとこれが親子関係でないので、これは親子関係でないのでここはチェックしませんよというような感じで無駄を排除する。こういう仕組みを導入してやることによって、大きく探索の無駄を省くことができます。実際にその親子関係をどういうふうに定義してやるかっていうのがこれなんですが、今この I っていうのは最後に置いた長方形としたときに、この J っていうのを、最後の置いたやつの下辺の Y 座標と新しく置く J っていうやつの上辺の Y 座標を比べた時に、こっちの下のほうが小さくなるような場合にのみ、新しいのを置く。こういうふうなルールをつけてやると実はさっきのことが簡単にチェックできるっていうのがあって、そういうふうにして探索を大幅に効率化することに成功しました。
実際にはもっと色々テクニックを駆使してるんですが、それをやることによって従来、最適な答えっていうのが知られてなかった長方形の配置っていうのを私たちのグループは
見つけることに成功しています。それがちょうどこの 2 つの絵になってまして、実際この長方形の数はこれだと 60 枚くらいあるのですが、この高さを最小化するっていう意味だと、
これよりも高さを縮めることができないっていうのをチェックしています。これが一番良い配置です。60 っていうと配置の組合せは膨大にあるんですけれど、うまく先ほどのようなテクニックを駆使することによって実用的な時間でチェックすることができるようになります。こんな感じの研究がひとつあります。
今は長方形の話だったんですけれども、長方形以外にも色々やっていて、また次に紹介
するのは多角形の話です。非凸多角形になります。どんな感じになるかっていうと、さっきは長方形だったやつが、こんな感じの多角形になるっていうような問題です。これもさっきと同様に紙とか布とか鉄板とかの切り出しに応用があるような問題です。では、これに関しては、さっきは厳密に最適な答えを求めるっていうのをやっていたのですが、こっちはちょっと難しめの、問題が難しくなっているので、こっちの研究成果としては、私たちが作ったのは、厳密な答えではなくて近似解ですね、それなりに答えを実験的に求めるとういようなことやっています。
その論文を書いた時にはベンチマーク問題ってのがあって、何人かの研究者が競い合っていくつか問題で、それまで知られていなかった最も良い解を更新することに成功してい6

情報学ジャーナル Vol.5, No.3 (2012) pp.1-15

今道 プログラミングの楽しさます。簡単にどういったやり方でやったかっていうのを紹介しますと、こんな感じに適当に多角形を置いてやります。これがスタート地点なんですけれども、このスタート地点からちょっとだけ容器を縮めてやります。縮めてやるとなんかちょっとはみ出すやつがいるので多角形を再配置してごちゃごちゃって再配置してやるとこんな感じになります。で、また成功するとちょっと縮めてやって、そうするとまたいくつかはみ出すので、また再配置を行うと。これを繰り返すことによって、どんどん容器の幅を短くしていくと。そういうふうなやり方をやっています。
ポイントとしてはどういうふうに多角形を再配置するのかっていうのはあるんですが、そこの詳しい部分は紹介しないんですが、ざっくり紹介しますと、こういうふうな多角形
同士っていうのは、もし衝突していた場合にどれだけ 2 つの多角形がめりこんでいるのかという度合いを最小化する問題を、非線形の最適化の手法を利用することによってうまく取り除くアルゴリズムを作りました。それによって例えばこういう感じの配置があった時に赤い部分が重なっている部分なんですけれども、重なっている度合いがペナルティとしてつくような最適化問題を作って、この重なっている度合いを小さくするっていう操作を高速に行うことができます。

プログラミングコンテストについて研究の話はこれぐらいにして、あとはプログラミングコンテストの紹介をしたいと思います。さっきの研究の話っていうのはよりよい方法、誰も作ったことのない答えを求めた
いとかそういうので頑張っていて、それはそれで楽しいんですけれども、コンテストっていうのも楽しいっていう話です。コンテストとはどういうものかっていうと、だいたいその現地に人が集まる場合もありますし、インターネットで集まる場合もあるんですけれど、課題のプログラムっていうのが与えられて、それをその課題を達成するようなプログラム
をより正確により早く実装することを競うものです。制限時間があってその中でプログラ
ムを書かなきゃいけないので非常に緊張感がある、さっきの研究とは違って、非常に緊張感のあるプログラミングになります。何が楽しいのかっていうのは、生で友達と競争できるっていうのが楽しいですし、実際集まって競う場合は同じような趣味を持った人たちなので、そういう人たちと会って色々話ができるっていうのが非常に楽しい。例えば後で出てくる世界大会の話になると、世界中からマニアックな人たちが集まってくるので非常に楽しい世界なんですね。
どんなコンテストがあるかっていうので紹介しますと、結構色々あって、例えば今も行われている最中ですけれども、スーパーコンピューティングコンテスト（Supercomputing
Contest）っていうのが高校生対象に行われていまして、また後で紹介する ACM 国際大学
対抗プログラミングコンテスト(ACM ICPC)、これがあります。あとは数学オリンピックの兄弟分で情報オリンピックってのがありまして、これは中学生、高校生が対象になります。
あと他にも先週末あった ICFP というプログラミング言語に関するカンファレンスのコン
テストなんですけれどもそういうコンテストもありましたし、あと企業がやっているようなのだと、Top Coder とか Google Codejam とかこんな感じであって、色んなコンテストっ
ていうのは趣味としている人たちが集まるっていう感じです。この中でこの 2 つですね、
上の 2 つは私がもともと参加者の紹介をしたいなと思います。
スーパーコンピューティングコンテストっていうのはちょっと紹介したいんですけれど
も、現在は東工大と阪大が主催している、高校生を対象にしたプログラミングコンテストです。昔は東工大だけが主催してたんですけれども、何が特徴かっていうと高校生にスー

7

情報学ジャーナル Vol.5, No.3 (2012) pp.1-15

今道 プログラミングの楽しさ

パーコンピューターを貸してくれるんですね。スーパーコンピューターを使って何か競えっていうのでスーパーコンピューターを使わせてくれるっていうのは非常に楽しくて、これは当時懐かしいので１枚写真を持ってきたので、これは僕なんですけれども、これはたぶん高校１年生か２年生の時のぼくで、本当にスーパーコンピューターなんかは雲の上のような存在だったので、これを使って何か遊ばせてくれるっていうのは非常に感銘を受けた印象を覚えています。
連 このコンテストはチームで出るのですか？
今道 はい。そうですね。このコンテストは確か３人チームかな。そうですね。もちろんチームでなくて個人で出てもいいんですけれども、確か１チーム３人まで入れました。
連 この時は何人で出たんですか？
今道 この時は３人ですね。これがぼくで、あとこの人とこの人が同じ高校の同級生です。
連 高校生でまわりの人からしたら珍しくなかったですか？
今道 そうですね。これはクラブが、そういうクラブに入っていたので、コンピューターを使うクラブっていうよりは無線部だったんですけれども。無線部って意外とコンピューターと関係があって、昔は、無線もやるしコンピューターもやるっていうクラブに当時入っていて、ちょうど先輩から紹介されて当時受けた。どんな問題が出たかっていうと、例
えば出たひとつが、三角形ビリヤード問題ってのがあって、三角形の底辺があって、このここからビリヤードの玉を打ってガンガンガンって当たって返ってくるんですけども、当たって返ってきた時に何回か当たると元の位置に戻ってきて同じ方向に飛び出すような形になるような打ち方がどれくらいあるかっていうのを調べる、という問題が三角形ビリヤード問題。例えばこういう問題が出たりとか、あとはさっき紹介した長方形、矩形の充填問題がありましたよね。あれも 98 年、ぼくが高校２年生の時かな、その時の問題で、実際にその後の研究でやってるっていうので、本当に付き合いが長いなっていうふうに思いますね。ちなみに、この当時優勝した高校生が考えたのと同じアイデアがほぼ同時期にイタ
リアの偉い先生たちのグループも同じくらいの時期に論文として出しているので当時の優勝した人は本当にすごかったんだな，と後になって気づきました。ぼくはこういう研究を、
このプログラミングを使って研究をやるっていう大きいひとつのきっかけとなったコンテ
ストです、これは。やっぱり何か、当時は学校で好きなもの同士集まるっていう感じだったんですけれども、こういうふうにコンテストに来ると日本中から集まってくるわけですから、猛者たちが。なんか話を聞くとあいつらはすごいなと。やっぱコンピューターを使う人っていうのは 97 年、98 年頃はあまりいないので、学校ではけっこうすごい扱いなんですけれども、こういう所へ来ると全然そんなことはない、上には上がいっぱいいるっていうので、非常に印象深い事件でしたね、私にとっては。
中高とこんな感じでやっていて、大学に入ってからやったのは、ACM 国際大学対抗プロ
グラミングコンテストっていうもので、これは非常に由緒ある大会で、アメリカの計算機学会が 1977 年から前身の大会はもうちょっと前から行われているらしいのですが、この大会自体は 77 年から主催しているコンテストでもう 30 年以上続いているコンテストです。

8情報学ジャーナル Vol.5, No.3 (2012) pp.1-15

今道 プログラミングの楽しさ

これは主に大学生、大学院生が対象になっていて、あとでちょっと出ますけれど３人チームのコンテストです。これは非常に大きいコンテストで、去年の例で出しますと、２つ予選があって最後が世界大会なんですけれども、最初に国内予選があって、それは世界各国で行われるのですが、だいたい去年の結果を見ると、世界 88 ヵ国、30 万人以上の学生が参加したっていうふうに書いてありました。
ちなみに今年(2011 年)の国内予選は 24 日に行われる、もうすぐ行われます。今から登録するのは間に合わないんですけれども、ぜひよかったら、結果はたぶんいろんなブログとかで紹介されると思うので、興味があれば見てもらいたいなと思います。
その国内予選では、大学対抗プログラミングコンテストなので大学からチームを選抜してその代表のチームが戦うっていうコンテストなんですけれども、大学内予選をだいたい兼ねているような感じになっています。そうした大学で絞られたチームが今度地区予選、世界各地で地区予選が行われるんですが、そこで競います。だいたい去年でいうと 2010 年
9 月から 12 月に行われて、アジアの地区予選っていうのもアジア各地で行われて、日本でも行われます。
去年は NII ですね。
世界各地で地区予選が行われて、だいたい 25,000 人 8,000
チームが参加するっていう大きいものですね。ここから絞りに絞られたチームが世界大会に行くことができて、世界大会っていうのは 2011 年 5 月 27～31 日なので 1 か月くらい前から行われまして、ぼくも朝 4 時くらいまでずっとインターネットの生中継を見ていたんですけれども、なかなか大変だったんですけれども、いや本当に手に汗握るすごい熱戦で、105 チームが戦うのを見てました。
どんな感じの競技かっていうと、1 チームは 3 名の選手と 1 名以上のコーチで構成されています。試合をするのはチームの 3 名の選手だけで、コーチっていうのは基本的には試合
中は選手に関与できないことになっています。普段の練習の手伝いをしたり、現地に連れて行くお手伝いといったそういう感じの仕事です、コーチは。制限時間がだいたい 5 時間
で、10 問くらいの問題が与えられているので、それをいかに早くより多く解くかっていうのを競います。間違えてもいいんですけれど、間違えるとペナルティがつくので正確に解くことが重要です。
ポイントになってくるんですけど、コンピューターは 1 チーム 1 台だけしか与えられません。3 人いて 1 台しかないのでうまくやる、うまくそこをどうまわすかっていうのがポイントになってきます。あとはノートの持ち込みが可で、基本的な解法っていうのはその持ち込むノートにメモしておく、ですね。どれだけそこに充実したものを持っていくかっていうのもひとつポイントになっています。
日本人にとってはポイントなんですけど、公用語が英語で、大会中はあらゆる説明とか質問とかが英語で行われるので、時々英語が苦手だと厳しいことがあるらしいということです。
あとはちょっとポイントっていうことでそうですね、さっきちょっと言ったんですけれ
ど、PC が 1 台しかないので、どういうふうに役割分担するかっていうチームワークが大切になってくるものです。あとは問題が英語で与えられているので、どれだけ英語に慣れているかっていうことですね。早く問題を読んだほうが当然有利になるので、やっぱネィテ
ィブの人に負けないくらいのスピードで読めたほうがよい。あと問題全部は解けないような難易度に設定されているので、うまく取捨選択して解いていくっていうのが大切になってきます。やっぱり一番どれが簡単かうまく選べないと、初っ端からつまずいてしまうとテンポが悪くなってあとで苦労するってことも何度も見たことがあります。
あと何よりも大切なのは練習で、とにかくこのコンテストで上位にいくには、練習に練9

情報学ジャーナル Vol.5, No.3 (2012) pp.1-15

今道 プログラミングの楽しさ

習を重ねて色んなアルゴリズムとか、色んなパターンを覚えなければならない。それでやらなきゃいけないので、なかなかモチベーションも大変で、基本的な練習方法っていうのは、ネットに色々問題があるので、それを何千問も上位のチームは解いているらしいという話を聞きます。国内だと、OB・OG 会ってのがあって私も所属はしてるんですけれど、そこは模擬国内予選とか地区予選を主催していたり合宿を主催しているので、そういうのを通じてはプログラミングコンテストの仲間が時々会ったりとかネット上で対戦したりっ
ていうふうにして練習をしたり交流活動をしています。あとは合宿っていうのは効果があって、直接会うと非常に盛り上がります。ちょっとどういう感じかをせっかくなので紹介します。これは 2007 年の大会のビデオです。
連 東京で行われたんですか？
今道 そうですね。2007 年は東京で世界大会が行われて、私はボランティアスタッフとして参加させてもらいました。会場は舞浜のヒルトンで行われました。世界中の人たちが集まってきて、みんな猛者です。食事の風景ですけども、これぼくですね、ちらっと映ってますけども。後で実際の風景も紹介しますけども、コンテストといっても実際にコンテス
トだけやっているわけではなくて、交流するイベントであったり、テクノロジーを紹介するイベント。今ちらっと映ったのはルビーの開発者のまつもとさんです。これディズニー
シー、みんな選手が遊びに行った時の動画で、こんな感じですごい世界の強豪プログラマーたちがディズニーシーを練り歩きました。日本文化の紹介。書道をやったりとか。あとはダンスダンスレボリューションとかこんな感じで遊んだりしてみんな仲良くするっていう。これは会場ですね。試合会場。ちょっとこれは時系列順には出ていないので余興で流れているやつも入っていますけれども。こんな感じで問題が与えられて、PC が与えられて、紙で書いてガリガリやっている人もいながら、プログラムを書くっていう人もいる、そん
な役割分担をしながらやってます。
連 開発環境とか向こうで用意されているんですか？
今道 はい。もちろんそうですね。指定の環境があって、それでやるっていう。最近だとLinux でやるっていうことが多いですね。
連 Window ではなくて？
今道 そうですね。
ずいぶん昔は Windows だったこともありますけども、ぼくの記憶では。
もうちょっと試合の風景が見やすいやつが。これは 2009 年のこれはカナダで行われた時のやつです。この画面が若干見やすくなっています。これいま風船がきてるんですけれども、問題に正解するとその問題の色ってのがあって、その問題の色の風船がもらえます。風船を見るとどのチームが何を解いたかわかるようになっています。こんな感じで辞書のようなものを持ってきたりとか。これもコードも読めるくらいの解像度です。風船の色を見てどの問題が解けるかっていうのを知るのがひとつのポイントになっていて、2005 年かな、
上海大会の世界大会に行った時は、試合が終わった時にうちのチームのところに優勝したチームのコーチがやってきて、君たちのおかげで優勝できたって言うんですよ。何のことかなと思ったら、最後の 1 問、その優勝したチームが最後の 1 問何を解くか迷っていた時10

情報学ジャーナル Vol.5, No.3 (2012) pp.1-15

今道 プログラミングの楽しさに、彼らは誰かどこかのチームが解けている問題を選ぼうっていうのを考えていたらしくて、たまたまうちのチームが誰も解いてなくて、珍しい問題を解いてたんですよね。あの色をあのチームはあげているから彼らは解けるっていってこの問題を選んだと。君たちのおかげで最後の問題が解けたと言われて、それを聞いた時はめっちゃ悔しかったですね。
本当に。なんか優勝を手助けしたっていうような感じなんですけど、もちろんぼくはコーチで、選手でないので、選手の悔しさはもっと大きいんだと思うんですけど、それでも話を聞いたときはやられたなっていう感じで、なかなか難しいもんです。
最近の結果っていうのをちょっと紹介しますと、だいたいこれがここ数年の世界大会の優勝チームで、2007 年、2012 年今年のやつもありますけども、国を見るとポーランド、ロシア、ロシア、中国、中国と、伝統的に旧東側諸国が強い。強化にも力を入れていて強い。
ここにどういうふうにして日本チームが上位に食い込んでいくかっていうのは、日本にとっても大きいテーマなんですけれども、なかなかうまいこといっているわけではない。もちろん日本人もどんどんレベルが上がっているんですけれども、なかなかやっぱそういうのは難しい。今年の結果は、2011 年の結果は東大も京大も参加して両方とも 27 位という結果です。日本チームの最高記録は 2000 年の大会で京大が 7 位になったということもある
んですが、この記録を抜くっていうのが一つ大きい課題では、将来こういうところに名前が出るといいなという風に思ってます。
どんな課題が出るかっていう一つ例をもってきました。今年の 2011 年の一番簡単だった
問題 K というやつなんですけども。多角形が与えられていて、この多角形が平行移動してすり抜けるんですけど、その際に必要となるこの幅を最小化してくださいという問題です。
多角形があるので、多角形を落とす場合には好きに回転させることができて、うまく回転させることによってここの幅を短くしてくださいという問題です。これは割と簡単な問題
でこんな感じのものもあるんですけど、実際にはアルゴリズムを思いつくのも大変もある
し、実装が大変なのもあるし、両方大変なのもあってなかなか世界大会は一筋縄ではいかないという感じです。
私の ICPC の参加歴というと、主に 2000 年から 2003 年までは京都大学のチームの選手として参加してて、私自身の結果というのは世界大会に及ばなくて、当時アジア地区予選、最後 2003 年の年ですけど日本大会でも 6 位で終わりました。そのあとコーチをやって私がコーチをやったチームは選手が努力したおかげで 2005 年、2006 年とも世界大会に出ることができました。そのあと先ほどもちょっとございましたが東京大会、ボランティアスタッフとして参加をしています。年の世界大会の様子っていうのは紹介しますと、この時出場したのは、世界大会に行ったのは私たちの京大のチーム、この青い T シャツを着てるのと、私が京大チームで、あと東大のチームは黄色い T シャツを着ている。これは明治大学の石畑先生で日本のリージョナルコンテストディレクターという形で、選手とかそういう形ではないですが、スタッフとして参加されています。
上海大会は基本的には世界大会は非常に豪華な環境で行われてまして、浦東といわれる
上海の非常にいい場所で、夜景も直接ホテルから見えるようないい場所で、いいホテルに泊まりました。だいたいどんな感じが行われるかっていうと、上海に入って登録をした後に、最新のテクノロジーを紹介するようなセッションがあって、そのあと練習のセッションがあって、余興のコンテストですね。本番のコンテストの前に、本番の問題とは違ってちょっと違うコンテストが行われます。後でこれ出ますけど。違う練習のコンテストがあって、それをやった後に本番のコンテストがあって、表彰式とかがっていう感じになります。これはさっきのテクノロジーを紹介するセッションなんですけど、基本的には遊ぶっ

11

情報学ジャーナル Vol.5, No.3 (2012) pp.1-15

今道 プログラミングの楽しさて感じですね。みんなでリラックスして遊ぶってもので、この時は上海科学技術館で遊び放題で遊び、あとは観光にも行ったりします。上海の観光にみんなで行ったり、ホスト校の上海交通大学の学生さんがガイドをしてくれ観光したりという感じです。
あとは本番のコンテストは別の余興のコンテストということで、この時はパラレルチャ
レンジという名前だったんですよ。何をするかというと BlueGene といって、当時日本の地球シミュレーターを抜いて世界一になったぐらいの時期だと思うんですけど、わざわざアメリカから中国に持ち込んで、それで選手たちにこれを使って戦わせる。何やるかっていうとサッカーゲームなんですけど、選手を制御するようなプログラムを書いてよりたくさん得点を入れるようなゲームですね。簡単に言うと。そういうプログラムの AI を作るのを競うっていう。さっきの課題をより早く解くっていうのとはちょっと違って AI を競うタ
イプのコンテストですね。そんな感じの審判のオッチャンですけど、サッカーの帽子かぶって、フランクな感じに結果を見るんですけど、こういう風な感じで試合の様子を見ながら楽しむと。余興のコンテストでは京大チームは 2 位になって大喜びしているっていうような感じです。賞品は MP3 プレーヤー。これは審判の人たち。さっきも出ましたけど、だ
いたいこれが会場の様子で 1 チーム 3 人で PC1 台と。問題を解くと風船が上がるということになります。この時の結果は京大が 29 位で東大はちょっと苦労したんですけど順位なしでした。
連 順位なしっていうのは 1 問も解けなかった？
今道 そういうわけじゃないんですけど、ある順位より下になると順位なしという形になります。表彰式。いろいろなハプニングもあったりしてなかなか楽しいんですけども。こんな感じでさっきのサッカーのゲームで入賞したので表彰されているところです。余興がなかなか豪華で、近所にあるすごい大きいコンベンションセンターでディナーがあって、こういう風に、今の人はわかんないかもしれませんが女子十二楽坊みたいな人たちが演奏しているっていう。竜も舞うわ、獅子舞も舞うわ、っていう会場なんです。みんな大変だ
ったねとか言いながら飯を食うと。いろいろイベントもあって、獅子舞についていくと、チャイナドレスを着た人たちがずらっと並んでいるような所があって、そこを通り抜けて
いくと、いきなり上海雑技団の雑技がスタートして「おおっー」ていいながらみんなで見て、ていうような次から次にイベントがある。最終的には川辺に連れて行かれて何が始まるかと思ったら、いきなり花火が上がって現地の人もびっくりみたいな感じで盛り上がって、めでたしめでたしという感じでコンテストは終わった。非常に楽しいイベントですね。
実際にはコンテスト期間中は他の大学のチームといろいろ話もしたりという感じなんで。
2006 年も基本的には変わらない。参加チームは京大のチームは一緒で、みんな青い、濃いのが京大で、薄いのが東大ですね。京大チームはメンバーは変わってないです。湯浅先生が追加で参加されてます。この時の開催地はアメリカテキサス州のサンアントニオというところで行われまして、ICPC のヘッドクオーターがある Baylor 大学というところがホストをしています。ちょうどたしか 30 周年かなんかで記念のコンテストでした。僕もあまり
詳しくは知らないんですが、アラモの砦というので有名というので紹介された場所だそうです。
スケジュールは基本的には変わってなくて、練習があって、今度 Java Challenge っていう名前になっていますが、これもさっきの AI を戦わせるタイプの余興のコンテストで、宇宙船を操って戦うっていうコンテストです。それが終わったあと本番があるっていう感じ

12

情報学ジャーナル Vol.5, No.3 (2012) pp.1-15

今道 プログラミングの楽しさです。毎晩夜はインターネットカフェミみたいなのがオープンしていてみんなメールチェ
ックしたりとか、別のチームの人と遊んだりしてます。定番だと巨大チェスで、でかいチ
ェスが持ち込まれているので腕に自信のある連中がチェスで戦うと。昼はプログラミングしてるのに、夜はチェスをやっているというなかなかみんなすごいなって思いながら見てるわけなんですけども。こんな感じの開会式があってという感じで、練習のあと基本的にはコンピューターを使ってここのコンピューターになれるっていうのがメインの目的なので、なんかいろんな練習の問題が与えられるんですけど、わざと間違えてどういった結果が返ってくるかいろいろやるっていう、まあちょっとしたコツがあるんですけど、基本的にはいろいろやって楽しむっていう感じです。この時は南の方の州なのでメキシコ近いのでタコスが多いんですね。毎食のようにタコス食べててみんな飽きてきたので、日本食レ
ストランに行ったらとても日本食と思えないものが出てきてびっくりしたっていう感じです。
これは AI を戦わせるタイプのコンテストです。余興のコンテスト。宇宙船を操るっていうゲームです。この年は珍しくて、選手のみが普通はやるんですけども、選手だけじゃな
くてコーチ専用のセッションもあって、その時ぼくは偉い先生 2 人に囲まれてやったんですけども、残念ながら結果は散々だったんですね。こんな感じで本番前日は、みんな上を見上げているんですけど、このレストランの天井部分が 360 度スクリーンになってて、そこに画面が出てるんです。ここで各チームが戦うっていうのを眺めているって感じのやつです。
世界大会の様子はこんな感じになってまして、これは開始直前で、会場の前にみんな集
まって入場を今か今かという感じで待ちます。そこで優勝トロフィーが出てきて好きな人
は触りたい人は触るって感じで、みんなワーっと触るっていうのがこんな感じの絵です。
京大チームがはしゃいでいる絵です。このトロフィーが欲しくてみんな頑張っている。会場はこんな感じになってて、やっぱり構図は似ていてさっきと違って丸テーブルみたいな感じになってるですけどコンピューターと数台の、コンピューター一台に 3 人いる。風船が上がると正解。この年は結果としては東大も京大も正解数は 3 でともに 19 位という感じ
で、残念ながら上位には入れなかった。
コンテストが終わると最後はみんなで楽しむっていう感じで、この年はロデオショーを見に行って、こんな感じの。ロデオショーを見たりロデオを見たあとはみんなでバーベキューをするっていうのでこれを、よくわかんないですけどもボーリングぽいゲームですね。
ボーリングぽいってなんか玉当てみたいな感じで当てて落とすゲームとか、縄投げのゲー
ムです。なんかカントリーミュージックが流れてみんながダンスしたりとか、そんな感じ
でみんなほんとに楽しむっていう感じのイベントがあって、すごい交流を深める。仲良くなった者同士また練習をしたりとか、なんかそういういろいろするわけですね。まあそん
な感じで非常に楽しむことになってます。
時間過ぎてるのでまとめに入りますけど、プログラミングって何が楽しいっていうと新しい計算ができるっていうのが楽しい。計算ができるってだけでなく競い合うっていうのも非常に楽しいっていうことです。私のメッセージとしては。今年の ICPC ももうすぐ始まるのでよかったら注目してやってください。ということで締めさせて頂きます。ありがとうございました。
根本研究科長 ありがとうございます。1 時間でお願いしていたので、時間はまだあります。
残りはディスカッションの時間にしたいと思います。質問でもいいし、今日の話を聞いて

13

情報学ジャーナル Vol.5, No.3 (2012) pp.1-15

今道 プログラミングの楽しさ触発されたことを何かコメントがほしいってことでもかまいませんので何かどうぞ。
今道 本当に何でもいいですよ。
長瀬(※講演の出席者) アルゴリズムを考える時間なんですけど、1 日練習量ってどれくらいやるんですか。コンテストに向けてとか。
今道 コンテストに向けての場合は、正直な話、ぼくが選手時代は世界大会へ行けなかったチームなので練習はさぼり気味だったんですね。だから 1 日 1 時間、2 時間くらいで根をあげてたんですね。本当はそれを毎日できるかっていうところなんですけれども。
長瀬 長くやるっていうより毎日。
今道 そうですね。もうちょっと長くやることも重要だし、毎日やることも両方重要なんですね。本当にその強豪チームっていうのは毎日ちゃんと練習しているし、ちゃんと量も質も伴う練習をしているので、聞くと自分には真似できないなっていう根気のいる世界です。
根本研究科長 関連なのですが、アルゴリズムってすごくたくさんありますよね。でもそんなに何千もトレーニングを体験していくと、逆にこれだけ押さえたら、まさしく基本だ
なっていうようなアルゴリズムのセットがあるように思えるのですが、それは実際あるのでしょうか。そのセットっていうのはだいたいどれくらいの種類というか、アルゴリズムの基本は何本くらい身に付ければ良いっていうのは目安ありますか？
今道 まず基本的にはセットっていうのはあって、例えば問題を見たときに、だいたい簡
単に分類するんですね。よくあるのが、動的計画法だとか、幾何の問題だとか、それほど数は多くないんですが、種類に分類して解くっていうのがあります。ただ、いくつぐらいだったかは今思い出すことができません。すみません。
〈講演終了〉

14

情報学ジャーナル Vol.5, No.3 (2012) pp.1-15

今道 プログラミングの楽しさ

著者略歴
今道 貴司

Takashi Imamichi

1981 年生．2009 年 3 月京都大学大学院情報学研究科数理工学専攻修了．博士（情報学）．2010 年 4 月に日本アイ・ビー・エム株式会社入社．東京基礎研究所に配属．図形の充填問題を中心に組合せ最適化の研究に従事．

情報学ジャーナル
情報学ジャーナル Vol.5, No.3

2012 年 2 月 29 日発行

代表者: 根本 俊男
発行所: 文教大学大学院 情報学研究科〒 253-8550 神奈川県茅ヶ崎市行谷 1100
電話：0467-53-2111(代表)ファックス：0467-54-3724（大学院準備室）

e-mail: gsinfo@www.bunkyo.ac.jp
http://www.bunkyo.ac.jp/faculty/gs-info/
編 集: 文教大学大学院 情報学研究科 研究公開推進委員会
編集長 岡野 雅雄，委員 関 哲朗

ISSN: 2185-6850

15