SuperCon 2004参加記

毎年の夏に東京工業大学が主催するスーパーコンピュータコンテストというものが開かれる。予選を通過した約１０チームが東工大に通って本選問題を解くプログラムを作成し、そのプログラムをスーパーコンピュータ上で動かしてその解答の正確さと速さを競うコンテストだ。これは今年の大会に参加した際の記録である。
公開された予選問題を解くプログラム・レポート及び参加申込書をあわせてメールに添付して送信することで、正式な応募となる。２～３人で１チームを組み、本選ではそのチームで１つのプログラムを作成することになる。

今回参加したのは次のメンバーである：
宮崎（高三）、藤井（高一）、松永（高一）

高三の宮崎は受験がどうのこうのと心配され、高一の藤井と松永は夏休みの講習と本選期間が重なっているにもかかわらず、チームnomeanとして参加を決意した。なぜチーム名が「nomean」なのか？というのは、前回先輩方のチームが出場した際チーム名が「noname」だったので、その文字を入れ替えることによってnomeanとなったのだ。

予選問題は次のようなものであった：

素因数分解した時，重複するものも含めた素数ののべ個数がちょうど12個となる整数をSuperCon数と定義する。 例）3750000=2^435^7

与えられた整数n（ただし、10,000,000≦n≦20,000,000）に対し、nから始めて2004番目のSuperCon数を求めるプログラムを作成しなさい。ただし，与えられた整数nそのものがSuperCon数の時は、nを１番目のSuperCon数とみなします。

これは問題の一部分である。ルールや注意事項など詳細を知りたい方は、東工大のスパコンのホームページを参照して頂きたい。

最初私は数字を１つ１つ素因数分解して因数が１２個のものを挙げていき、２００４番目のSuperCon数を見つけよう、と考えた。しかしそれはあまりにも時間がかかりすぎる上、メモリの消費量も半端ではない。最初に2004番目のSuperCon数がありそうな場所までの素数をエラトステネスの篩ですべて求め、１つ１つ素因数分解していく、ということだ。このプログラムを家で作って走らせてみたところ、確か１５分ほどかかった。
しかし脳にアルゴリズム辞典がつまっているのであろう宮崎は１２個の素数を組み合わせてSuperCon数を求めるという方法でプログラムを作った。もちろん私もそのことは考えていたが、技術不足だったためか上手く作る方法を思いつかなかった。その宮崎が作ったプログラムでは約２５秒で解答が出せたという。具体的な解法としては、まずエラトステネスの篩で素数を求めて配列に保存し、それを掛け合わせて別の配列に保存していく。つまり、素数×素数＝②（因数２個）、②×素数＝③、③×③＝⑥、⑥×⑥＝⑫としてSuperCon数を求め、その2004番目を出力する。
改良を重ね、最終的に1秒未満で結果が出せるようになった。（もちろん、ＰＣの性能によってかかる時間は変わってくる。）実際に審査環境と同じにするためにVine Linux Ver2.6r4を物理部の1台のＰＣにインストールし、GNU C Compilerでもコンパイルできることを確認した。
締め切り前日にソースとレポート、応募用紙を添えてスパコンの大会宛にメールを送信。受理されれば確認のメールが返ってくるはずなのだが、数日後にメールチェックしても返信がこない。もしかして、記入漏れがあって受理されなかったのでは？と不安が募る。
宮崎がスパコン宛に問い合わせのメールを送った。返事が返ってきた。どうやらむこうの手違いで確認のメールが送られなかったらしい。こちらの応募は受理されているとのことで、とりあえず安心した。その後すぐに予選通過のメールが届いた。
予選を通過したチームは次のとおりである。

８月２日（月）開会式・見学など

大岡山駅を出ると、本当にすぐそこが東工大の正門だった。となりに東急ストアがあるし、商店街もある。東工大生はなんて恵まれているのだろうと思った。

開会式はキャンパス内の西９号館という場所で行われた。会場の入り口の受付で分厚い封筒と名札を手渡される。その封筒には炭素菌が入っていた。

- BAD END -

…になるわけがなく、１１時ころから普通に開会式は始まった。主催者や色々な人からあいさつがあった。簡単な挨拶などがあり、自己紹介などがあった。その後、学術情報センター内の実習室（実際にプログラミングをするところ）やスーパーコンピュータの置かれている部屋などを見学した。スパコンの部屋はかなり涼しいというか寒い。そして昼食へ。
東急ストアにて、それぞれ思い思いの食品を購入。すぐに緑豊かな東工大キャンパスに戻り、ベンチに座ってそれを食べた。
……なお、この昼食では、「絶対にこの三人でピクニックに行きたくないな」と言う人間がいた。そんな、極めて静かな食事風景だった。

昼食を食べ終わった後、我々は西８号館のとある教室らしき部屋に連れて行かれ、監禁された。本選問題に関する説明を受けた。大会主催の渡辺先生と、松田先生が交代で説明された。この“授業”は１時間くらい続き、私は眠りそうになってしまった（というか、ちょっと寝た）。学校ではいまごろ講習が始まっているころであろう、そしてその授業に出ていたらこの時と同じようにまぶたが重く感じていたに違いない。

本選問題の大まかな内容：

まず用意されるのは、256×256(pixel)の白黒画像である。その画素１つ１つがＲＳＡ暗号方式によって暗号化された画像が、まず我々に与えられ、それを解読する。しかしながら単に暗号化された画像が与えられただけでは解読は非常に困難である。そこで画素ごとに解読のヒントとなる情報も与えられる。このヒントをもとにして解読していく。

←暗号化
解　読→

暗号化された画像eimagefileとヒント情報hintfileをもとに、できる限り元の画像を復元するプログラムを作成せよ、というのが今回の問題である。プログラムの性能は評価用に用意された１組のファイルに対して制限時間３分以内に出力された画像と、正解画像との画素の一致数で評価される。ただし異なるチームで同じ正解率の画像が出力された場合は、出力までの計算時間が短いものを良い方とする。

予選問題と同様、細かいルールやＲＳＡ暗号方式などについてはここでは割愛する。本選問題もスパコンのホームページにＰＤＦ形式で掲載されている。これから我々が考えたアルゴリズムの説明などに入るが、既に本選の問題の内容を十分に理解していることを前提にして書くので、少なくとも「チームnomeanが考えたアルゴリズムに興味がある」という方はあらかじめ詳しい本選の問題を読んでおいた方がいいかもしれない。

さて話は戻るが、先ほどの問題の講義の時にうちわやマウスパッド、毎年恒例スパコンのTシャツ、それと外国のチームとの親睦を図る為に翻訳機が配られた。「借りた」のではなく、「もらった」のである。翻訳機は１チーム１台なので、どこのチームでも争奪戦が起きることは必至であろう。我々のチームでは「最も外国のチームとコミュニケーションがとれた人」が最終的に所有権を得る、ということにした。

一行は恵比寿の日本SGI本社に到着、プレゼンを見たり説明を聞いたり（これだけは言える、どこのチームも興味を示していないことは確かだ。）して、その後懇談会が開かれた。立食パーティ形式で、各チームの自己紹介があった。さて、話し手を誰にするか。
宮崎「俺、舌が上手くまわらないから」
藤井「僕、あがるから」
「・・・・・・・」
松永「消去法かよっ」
いやぁ、松永は本当によくしゃべってくれた。偉い。

８月３日（火）プログラミング１日目

３～５日は朝８時から夜の８時まで、ぶっ通しプログラミングである（もちろん休憩などもあるが）。とりあえず実習室に入り、端末の電源を入れて教わったパスワードを元にスパコンにログインする。OSはUNIX、キーボードがHappy Hacking Keyboardときたものだから操作が大変。

とりあえず、printfでも使って文字を表示するプログラムを作る。普段はVisual C++を使っているが、端末上ではエディタはMule、そしてコマンドラインでいちいちコンパイルしなければいけない。「F7」一発でビルドしちまう開発環境とは大違いだ。Makefileを作って簡略化するという手もあったが、だいたいそのようなもの作ったことないし作り方さえしらない。昨日の説明の時に渡された分厚い冊子にUNIX端末の使い方やMPI、その他色々あってその中にMakefileの作り方なるものがあったが、見てもよく分からなかったので（というか分かろうとしなかったので）断念。

さて、テストプログラムのコンパイルはできたのでいいものの肝心の暗号化すべきファイルやヒントファイルがないと解答プログラムの作成ができない。昨日の説明ではサンプル問題がでるはずなのだが、まだできてないとか。

数時間後、ようやくサンプル問題Bがでる。サンプル問題は何種類かあり、Aが審査用と同じようなまじめに作った問題。今回出たBが簡単に解ける問題。なんとヒントのhardnessが全部１２（つまり、下位１２ビットがマスクされている）という問題だ。とりあえずこのサンプルを元にしてプログラムを作成していく。
今回の問題の基本的な解法は、\( C_{i,j} \)（\( i=ｙ \)座標、\( j=ｘ \)座標とした、\( i×256+j \)）を復号化関数\( d_{rsa} \)によって復号化したものが\( m_{i,j} \)であるから、ヒントを元に完全な\( m_{i,j} \)を求めて、その最下位ビットと暗号化された画像の画素との排他論理和を求めて元の画像の画素を得る、という方法だろう。もう１つの手段として法nを素因数分解してRSAセットを破るという方法が考えられるが、１００ビット整数の素因数分解などそう簡単にはできない。
ヒント情報は\( m_{i,j} \)の下位ビットいくつかをマスクしたものだから、マスクされた部分を総当たりか何かによって求め、暗号化関数\( e_{rsa} \)によって順々に暗号化する。（暗号化関数は公開鍵を用いて簡単に作成できる。）その値が元の\( C_{i,j} \)に戻ればその\( m_{i,j} \)が正しい値ということになる。
もしマスクされた部分を１ずつ足して総当たりで求めていくとなると、最大で２のhardness乗回暗号化関数を呼び出すことになる。hardnessは１～３５だから、もしもhardnessが３５だったら、最大で２の３５乗、つまり34,359,738,368回も計算しなくてはならない。これはいくらスーパーコンピュータとはいえ、３分では絶対に無理である。
このようにして\( C_{i,j} = 0 \)から順に解いていこうとするとどうなるか・・・もしも\( C_{i,j} = 2 \)がhardness35だったら、そこで時間がかかってあっという間に３分を過ぎてしまう。
そこで分かる人なら思いつくであろう、ソートである。hardness順にソートして小さい分から求めていけば、少ない時間でたくさんの画素を求めることができる。我々はクイックソートを用いた。（おそらく他チームも使っているだろうが。）
さらに昨日宮崎が思いついたのは、マスクされた部分を１ずつ足すのではなく、２ずつ足していく方法である。２ずつ足していくとなると最下位ビットは変化しないが、そこがミソなのである。２ずつ足していって最下位ビットを０のまま変化させずに調べていき、もしも見つかったら最下位ビットは０のまま、見つからなかったら最下位ビットは必ず１になる。そうすれば最大でかかる時間は２分の１になる。

完成した\( m_{i,j} \)を暗号化するには\( m_{i,j}^{e}\ mod\ n \)をとればよい。eはかなり小さい数なので、暗号化関数\( e_{rsa} \)においてそれ程工夫する必要はない。（数日後にeを17に固定する、と発表された。）これはべき乗の方法としては有名であろう、まず\( m_{i,j} \)を２回掛けて２乗を求め、さらにそれを２回掛ければ４乗分がもとまる。４乗を２回掛けて８乗、８乗を２回掛けて１６乗、そしてその１６乗分ともとの\( m_{i,j} \)を掛ければ見事５回の乗算で１７乗が求まる。同じものを１７回掛けるやり方より３分の１以下の時間しかかからない。

しばらくして昼食。近くの豚カツ屋へ。私は外食をあまりしないので、こういう店に入るのは初めてに等しい。とりあえず全員カツ丼を注文する。
食べ終えて店を出ると、口々に感想を言う。
宮崎「結構よかったな」
藤井「まぁよかったね」
松永「全然ダメ」
松永は結構豚カツには厳しいようだ。私はまずくなければ味なんてどうでもよかったが。

実習室に戻りしばらくプログラミングをした後、休憩タイム。全チームが休憩室に集まっておしゃべりしたりおかしを食べたりする時間だ。そこで東工大のスパコンを管理しているという日本SGI社の坂本さんが、不思議な絵が印刷された紙を数枚眺めていた。ふつうに紙を見ても変な模様にしか見えない。しかし、目の焦点をずらすことによってある立体が浮かび上がるというのだ。私も早速チャレンジしたが、結構難しい。かろうじて見えたのが「星がへこんで見える」ものだった。

午後８時の終了時間、夏とはいえこの時間になれば日は落ちて空は真っ暗になる。そうして家路につく。首都圏以外から遠征しているチームは近くのホテルに泊まるそうで、そういうチームに限って費用の援助も出るらしい。

８月４日（水）プログラミング２日目

プログラミングができる端末が置いてある実習室は２つあり、昨日は実習室２を使っていた。実習室２を使うチームは少なく、部屋はとても静か。助言をしてくれるチューターの方も時々しか来ない。それに比べ実習室１はとても賑やかで楽しいとか。実は昨日の帰り際、宮崎が「なぁ、向こうの方が楽しそうだから明日から向こうの実習室行かねぇ？俺こんな静かな所嫌なんだけど」と言っていた。更に向こう側は１つの机に端末が３つ並んでいるので、3人で1チームだった我々にとって作業しやすいとか言ってきたのである。（実習室２側は１つの机に２つしか並んでいない。）
先に東工大に着いた私と松永はそんな言葉を思い出してはいたが、静かな場所が好きだったのでそんな主張を完全に無視して昨日と同じ部屋へ行き、パソコンを起動。その内やってきた宮崎が不満ありげに私たちの後ろの席についた。

とりあえず宮崎がプログラムの基盤を組み、私と松永が補助的な部分（？）を作るという形でプログラミングを進めた。私は資料を参考にMPIによる並列化を行い、松永はアルゴリズム辞典を参考にクイックソートの部分を作成した。

昼食は東急ストアで各々好きな弁当や総菜を買い、休憩室で食事。

そして和やかな休憩の時間、松永が浅野の意外な過去を語り出す。
「浅野学園を建てた浅野宗一郎はもともと、浅野セメントという会社を経営していた。その浅野セメントには１つの問題があった。セメントを作るときに煤煙がたくさん出てしまう、それによって近隣の住民から苦情が出た。その苦情を打ち消す為に、総一郎は新たなセメント工場の設立に走った。そして、見つけたセメント工場の設立場所が今の浅野学園の敷地。山を開いてセメント工場を建てられるようにしたが、その頃と同時に煤煙を防ぐフィルターが開発され、浅野セメントにも導入される運びとなった。そして浅野セメントでも煤煙の問題は解消し、移転しなくてもすむようになった。山を開いてセメント工場を造ろうとしていた土地はどうしよう…、そうだ、学校にしよう！ということでその土地に浅野学園が建てられた。」
なかなか興味深い話である。私も宮崎も知らなかった。

サンプル問題Aが公開される。流石に真剣に作った問題なだけあり、Bとは比べものにならないほど解くのが難しい。
昨日までのような基本的な考え方のみを用いると、制限時間内に正解率９０％以上を出すことはほぼ不可能に近い。そこで本選問題詳細の最終ページに今回の解読のヒントとして、次のような式が紹介されている。

\[ \begin{equation} \left. \begin{alignedat}{2} d_{rsa}(C_1) \\ d_{rsa}(C_2) \end{alignedat} \right\} \Rightarrow d_{rsa}(C_1 \times C_2) \equiv m_1 \times m_2 \mod n \end{equation} \]

\( C_1 \)と\( C_2 \) が \( m_1, m_2 \) に復号化できれば、その \( m_1, m_2 \) 用いて \( C_1 \times C_2 \) が簡単に復号化できるということだ。２，３などの小さい数が復号化できれば、この式によって更に多くの画素を復号化できる。しかしこの方法を用いるには、ヒントから完全に \( m_1, m_2 \) を復元しなければならない。昨日の２を足していく方法だと最下位１ビットしか分からない場合があるので、一緒に使うことができないのである。

とりあえず、hardnessの小さい順に \( m_{i,j} \) を求めていき、ある程度処理した後に残りの中から上の式で求められるようなものを探しだし、計算するようにした。

８月５日（木）プログラミング３日目

今日も私と松永は宮崎より早めにきた。いつものように実習室２の方へいく。そしてその後に宮崎がやってきてしぶしぶ後ろの席へ。
今日はどのチームでも焦っているはず、というのは午後から全てのプロセスを停止し、審査時と同じ64CPUを用いて各チームのプログラムを走らせるテストがあるからだ。普段は他のチームのことを考え4CPUまでに制限されている。無論うちのチームだってその時のためのプログラムが仕上がってないので、焦りまくりである。

宮崎から渡されたソースの並列化はできたものの、上手くいかない。なぜか途中で止ま ってしまうのである。GSICの山梨さんやSGIの坂本さんに相談したが分からないとか。

時間はあっという間に過ぎ、昼になった。流石に腹が減ったので、近くの担々麺の店へ行く。担々麺専門店ということで、メニューはほとんど担々麺。辛なし、並辛、中辛、大辛というものがあるらしい。ふつうのラーメンも売っていたので私はそっちを選んだ。宮崎は辛なしを、松永は並辛を選んだ。
松永がそんなに辛くないといい、宮崎は後悔したようだ。もちろん私は、「まずくなければなんでもいい」。

さっさと昼食を食べ終えて、部屋に戻ればもう２時。３時のテストまで１時間あまりである。結局まともに動くようなプログラムは完成せず、休憩時間兼テスト時間はやってきてしまった。
ほとんどのチームでまともに動くプログラムができていなかったようである。うちのチームも１０分という限られた時間のなかでデバッグしたもののそれらの努力はほとんど意味のないものだった。

しばらくして、私が並列化したソースが動かない原因がようやく分かった。ヒントからの復号化が終わったものにはフラグを立てて後に同じ計算をしないようにしているのだが、そのフラグをマスター（ＭＰＩのランクが０）しか初期化していなかったのである。というわけで、他のＣＰＵ上で動くプロセスがそれぞれ異なるフラグを持っていた為にそれぞれ違った動作を起こし、ＭＰＩ同期のところで止まってしまったのである。このことを言ったら坂本さんに背中を叩かれた。
この状態でなんとか正解率６０％を達成、９０％以上だと入賞は確実だろう。０％だったら「影の優勝」である。

その後宮崎が書いたソース部分にバグが見つかる。それを直そうと色々いじっていると、突然動かなくなる。そして何がおかしいのか分からないまま、本日のプログラミングは終了・・・。

８月６日（金）プログラミング４日目（最終日）

宮崎に先手を打たれた。先に来て実習室１に行ってしまったのである。後から来た私と松永はその隣の席へと座る。椅子がちょっと気に入らなかった。

最終日の今日はプログラミングの時間がいつもの半分。午後１時までに審査用のプログラムを提出しなければならない。

とりあえず、printfを入れまくって実行箇所を追跡、昨日終わり際に残したバグを取る。こういうときにVisual C++みたいなデバッガがありゃ楽なのに……。
更に私は昨日頭の中で考えた画像の補完を提案した。まわりの求まっているピクセルを元に、求まっていない箇所をある程度予測するのである。松永はそれを初日に思いついていたようである。しかし今の今まで忘れていたとか・・・

宮崎がすぐに補完をする関数を作成した。その名も「kakikomi関数」。さすが宮崎、識別子に日本語をローマ字に直したものを用いる癖がこんな場所でも現れるとは。素数やべき乗も「sosuu」「beki」といった具合で関数名に採用してしまう恐ろしい技だ。（実を言うとべき乗の関数を「bbeki」（最初のbはbignumの略）と名付けたのは私だったりする。）でもそういうのはまだ許せる、というのはその言葉で関数の内容が分かるからだ。しかし今回はどうだろう？「書き込み」と言われて「補完」という言葉が思いつくだろうか？私はちょっと無理があると思うが。
なんとこの関数を使うだけで正解率が８０％に上昇。その後１０秒ごとに途中経過の画像を出すようにした。その後、４つ全てのサンプル（A,B,C,D）をテストしてみた。だが、なぜか簡単な問題のはずであるサンプルBを解こうとすると異常終了してしまう。不安が募る・・・
結局サンプルBが解けないバグを残したまま、プログラムを提出してしまった。

〆切の午後１時前、みんなでカウントダウン。終了時刻を迎え、全員が休憩室に移動。インタビューに備えて感想などをまとめる。
インタビューが終わって午後２時半ごろ、昼食を食べていないことに気づく。もういいや、という感じでそのまま物理部の様子を見に行く。

８月７日（土）発表会・閉会式

この日は記念撮影があるとのことでほとんどの人がスパコンのＴシャツを着ている。場所は初日と同じ９号館の多目的ホール。席についておとなしく待つ。

センター長などの人々から挨拶があり、主催の渡辺先生が今回の問題について説明。そしていよいよ各チームの発表。チームの発表ではメンバーが壇上に上がり、伊藤先生から質問を受け、それに対して説明などして答えていくという形式だ。他チームによると前年までは各チームでプレゼンテーションを用意して発表するという形式だったらしい。私は壇上だとかなりあがるので２人に任せた。おふたりさんに感謝、感謝。
休憩時間、チューターさんが持っていたカードゲーム「ワードバスケット」で遊ぶ。これがなかなか面白くて、ただのしりとりゲームなのになかなか言葉が出てこない。語彙力が試される変わったカードゲームだ。

そしてついに審査発表。３位からの発表で、まわりは静まり、息をのむ。
そして画面に現れた文字が・・・「nomean」だった。
拍手の中、壇上に上がり楯とメダルを受け取る。本当に入賞するとは思わなかった。
２位は中国チーム「china」、１位は麻布高校「nemui」だった。

１位のnemuiチームの結果を見てみると、173秒の時に78%だったのに、178秒の時で急に99.81%まであがっている。一体なにをやらかしたのだろうか・・・。それにしても１位と２位は僅差だ。それに比べりゃうちの82%なんて全然ダメ。（しかもあのサンプルBが解けないバグに引っかからなかったのもある意味奇跡だ）
式が終わり、お別れパーティが開かれる。初日の懇談会と同じ立食パーティ形式で、初日よりも、この大会の中で仲が深まったのであろう、たくさんの人が喋っていた。話すのが苦手な私は隅によっていたが・・・。みんなで大会の終了を祝って乾杯、そして食べ放題・飲み放題。
GSICの山梨さん＆SGIの坂本さんの強力タッグでじゃんけん大会が開かれる。ルールは簡単、坂本さんとじゃんけんをして勝ったら生き残り、それ以外は負け。何回か繰り返して最後に残った人たちにSGIグッズなどの景品プレゼント、という単純なもの。景品は電卓、バッグ、携帯ストラップなど結構なバリエーション。私はトートバッグを手に入れ、最後に松永がスパコンの巨大ポスターを手に入れた。
振り返ればこのひと時が最も楽しく、盛り上がったと思う。

ここにnomeanチームが作成し委員会に提出した予選問題の解答プログラムのソースを記載する。興味のある人だけ見ればよい。興味のない人はこのページだけ破って捨ててもかまわない。ちなみにソースは作ってそのままなので読みやすい工夫などは全くしていない。本選問題のソースは紙面の都合（載せると十数ページ消費する。地球環境に優しく！）と一般のPCではコンパイルできないなどの理由で記載しない。どうしてもみたい場合は物理部のHPへ。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238

/*
 * チーム nomean 予選問題解答
 * 作成：ほとんど宮崎
 */
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define FIRST_PRIME 2
#define N 30000
#define answer 2004
int MUGEN;
int prime[N];
int prime2[N];
int prime4[N];
int prime8[N];
int prime12[answer];
int min_prime2[N];
int min_prime4[N];
int min_prime8[N];
int max_prime2[N];
int max_prime4[N];
int max_prime8[N];
int n;
int junban[N];
int suuji[N];
int prime_n[N];
int cache[N];

void new_insert(int *suuji, int pos,
                int a, int b)
{
    int c;

    c = MUGEN / a;
    if (c >= b)
        suuji[pos] = a * b;
    else
        suuji[pos] = MUGEN;
    return;
}
void new_sort(int *suuji, int *junban)
{
    int cach, i;

    cach = junban[0];
    for (i = 1;
         suuji[junban[i]] < suuji[cach];
         i++)
        junban[i - 1] = junban[i];
    junban[i - 1] = cach;
    return;
}
void inssort(int *junban, int first, int last, int *suuji)
{
    int i, j;
    int aaa;
    for (i = first; i < last; i++)
    {
        aaa = junban[i];
        for (j = i - 1; j >= 0 && suuji[junban[j]] > suuji[aaa]; j--)
            junban[j + 1] = junban[j];
        junban[j + 1] = aaa;
    }
}
void mod(int *moto, int *moto_p, int *moto_lp,
         int *kekka, int *kekka_p, int *kekka_lp)
{
    int i;
    MUGEN = moto[0] * moto[N - 1];
    for (i = 0; i < N; i++)
        kekka[i] = MUGEN;
    for (i = 0; i < N; i++)
    {
        junban[i] = i;
        prime_n[i] = moto_p[i];
        new_insert(suuji, i, moto[i], prime[prime_n[i]]);
    }
    inssort(junban, 0, N - 1, suuji);

    for (i = 0; i < N; i++)
    {
        // 配列をソート
        new_sort(suuji, junban);
        // 配列の一番を出力
        kekka[i] = suuji[junban[0]];
        kekka_p[i] = prime_n[junban[0]];
        kekka_lp[i] = moto_lp[junban[0]];
        // 配列の一番を更新
        prime_n[junban[0]]++;
        new_insert(suuji, junban[0], moto[junban[0]], prime[prime_n[junban[0]]]);
    }
    return;
}
void square(int *moto, int *moto_mp, int *moto_lp,
            int *kekka, int *kekka_mp, int *kekka_lp)
{
    int i, ichi;
    int nanika[N];

    MUGEN = moto[0] * moto[N - 1];
    for (i = 0; i < N; i++)
        nanika[i] = N;
    for (i = N - 1; i >= 0; i--)
        nanika[moto_lp[i]] = i;
    for (i = 0; i < N; i++)
    {
        junban[i] = i;
        prime_n[i] = i;
        prime_n[i] = nanika[moto_mp[i]];
        if (prime_n[i] == N)
            suuji[i] = MUGEN;
        else
            new_insert(suuji, i, moto[i], moto[prime_n[i]]);
    }
    inssort(junban, 0, N - 1, suuji);
    for (i = 0; i < N; i++)
    {
        // 配列をソート
        new_sort(suuji, junban);
        // 配列の一番を出力
        ichi = junban[0];
        kekka[i] = suuji[ichi];
        kekka_mp[i] = moto_mp[prime_n[ichi]];
        kekka_lp[i] = moto_lp[ichi];
        // 配列の一番を更新
        prime_n[ichi]++;
        while (moto_lp[prime_n[ichi]] < moto_mp[ichi] && prime_n[ichi] < N)
            prime_n[ichi]++;

        if (prime_n[ichi] == N)
            suuji[ichi] = MUGEN;
        else
            new_insert(suuji, ichi, moto[ichi], moto[prime_n[ichi]]);
    }
    return;
}
void square_mod(int *moto1, int *moto1_mp, int *moto2, int *moto2_lp, int *kekka)
{
    int i, ichi;
    int nanika[N];

    MUGEN = moto1[0] * moto2[N - 1];

    for (i = 0; i < N; i++)
        nanika[i] = N;

    for (i = N - 1; i >= 0; i--)
        nanika[moto2_lp[i]] = i;
    for (i = 0; i < N; i++)
    {
        junban[i] = i;
        prime_n[i] = nanika[moto1_mp[i]];
        if (prime_n[i] == N)
            suuji[i] = MUGEN;
        else
            new_insert(suuji, i, moto1[i], moto2[prime_n[i]]);
        while (suuji[i] < n)
        {
            prime_n[i]++;
            while (moto2_lp[prime_n[i]] < moto1_mp[i] && prime_n[i] < N)
                prime_n[i]++;
            if (prime_n[i] == N)
                suuji[i] = MUGEN;
            else
                new_insert(suuji, i, moto1[i], moto2[prime_n[i]]);
        }
    }
    inssort(junban, 0, N - 1, suuji);
    for (i = 0; i < answer; i++)
    {
        // 配列をソート
        new_sort(suuji, junban);
        // 配列の一番を出力
        ichi = junban[0];
        kekka[i] = suuji[ichi];
        // 配列の一番を更新
        prime_n[ichi]++;
        while (moto2_lp[prime_n[ichi]] < moto1_mp[ichi] && prime_n[ichi] < N)
            prime_n[ichi]++;
        if (prime_n[ichi] == N)
            suuji[ichi] = MUGEN;
        else
            new_insert(suuji, ichi, moto1[ichi], moto2[prime_n[ichi]]);
    }
    return;
}
// エラストテネスのふるいで素数を生成する
void init_prime(int *kekka)
{
    int cach2[N], cach1[N], i, j, h, pos;

    pos = 0;
    for (h = FIRST_PRIME;; h += N)
    {
        for (i = 0; i < N; i++)
            cach1[i] = 0;
        for (i = 0; i < pos; i++)
        {
            for (j = cach2[i]; j < N; j += kekka[i])
                cach1[j] = 1;
            cach2[i] = j - N;
        }
        for (i = 0; i < N; i++)
        {
            if (cach1[i] == 0)
            {
                kekka[pos] = h + i; // h+i は素数
                for (j = i; j < N; j += kekka[pos])
                    cach1[j] = 1;
                cach2[pos] = j - N;
                pos++;
                if (pos == N)
                    return;
            }
        }
    }
}
int main()
{
    int i, min_prime0[N];

    scanf("%d", &n);

    init_prime(prime);

    for (i = 0; i < N; i++)
        min_prime0[i] = i;

    mod(prime, min_prime0, min_prime0, prime2, max_prime2, min_prime2);
    square(prime2, max_prime2, min_prime2, prime4, max_prime4, min_prime4);
    square(prime4, max_prime4, min_prime4, prime8, max_prime8, min_prime8);
    square_mod(prime4, max_prime4, prime8, min_prime8, prime12);

    printf("%d", prime12[answer - 1]);

    return 0;
}
// == End of file ==

最後に

まずこの長ったらしくてとてもわかりにくい文章をここまで読んでくれたみなさんに感謝。細かい説明まで読んでくれた人にはもっと感謝。
更に上のソースコードをじっくり読んで何がどうなっているか分かった人にはもっともっと感謝。（正直いうと宮崎が書いた上のソースは私もあまり理解できなかったのですが）

プログラミングっていうのはやっぱり面白いです。この大会で実感しました。
もしも来年、本選期間が夏休みの講習に重ならなかったならば、また頑張ってみたいと思っています。
（今回は予選通過通知が来た後に気づいたので仕方なく サボりました。 欠席しました。）