ACM-ICPCについての解説

こんにちは、スカイアーチネットワークスの並木と申します。

今年の２月から中途入社しました。

学生時代はプログラミングをゴリゴリと書いておりました。

今日はそのプログラミングの大会についてお話させていただこうと思います。

さて、皆さんはACM-ICPCコンテストというものをご存知でしょうか？

今回、テックブログ初の投稿内容として、ACM-ICPCコンテストについて紹介したいと思います。

１．ICPCとは

これは、大学対抗のプログラミングの世界大会のことです。

Association for Computing Machinery - International Collegiate Programming Contest(ACM国際大学対抗プログラミングコンテスト)

これを略したものがACM-ICPCとなります。

長いですね。

通称はICPCと呼ばれます。

毎年3万人以上が参加する大規模な大会です。

世界大会に参加するためには、まず地方予選を通過しなければなりません。

日本予選⇒アジア地区大会⇒世界大会

この順番で勝ち残らなければなりません。

アジア地区大会からは英語で問題を解かなければなりません。

したがって、難易度も高くなります。

参加条件はいたって簡単です。

各大学で3人チームを作って応募するだけです。

２．出題される問題

さて、それでは具体的にどんな問題を解くのか見てみましょう。

日本予選で出題された問題の一例です。

------------------------------------------------------------------------------------------------------

整長方形

高さhと幅wがともに整数である長方形を考えよう．そのような長方形を整長方形と呼ぶ．以下，この問題では横長の整長方形，すなわち w > h である整長方形のみを考える．

横長整長方形の大小関係を次のように定めよう．

1. 対角線の長さが短いほうが小さい．
2. 対角線の長さが同じならば，高さの低いほうが小さい．

与えられた横長整長方形に対し，それより大きい最小の横長整長方形を求めよ．

Input

入力全体は複数のデータセットからなる．データセットの数は100以下である． 各データセットはひとつの横長整長方形を記述しており，その高さhと幅wがひとつの空白で区切られた以下のような1行である．

h w

各データセットについて，hとw（>h）は，ともに，1以上100以下の整数である．

入力の終わりは，ひとつの空白で区切られたふたつの0から成る行によって示される．

Output

各データセットに対し，それに記述されている横長整長方形より大きい最小の横長整長方形の高さhと幅w(> h) とを，整数でひとつの空白文字で区切って1行に出力せよ．出力にはこれら以外の文字があってはならない．

なお，この問題の入力で与えられる横長整長方形に対しては，それより大きい最小の横長整長方形の高さと幅はともに150を超えないことが分かっている．

また，この問題では横長整長方形の大小を決めるために対角線の長さの大小比較を用いているが，これは対角線の長さの二乗の大小比較を用いても同じことであ る．対角線の長さの二乗の大小比較を用いることにより，浮動小数点計算の誤差によって生じうるトラブルを避けることができる．

【2013年ACM-ICPC日本予選過去問より一部抜粋】
-------------------------------------------------------------------------------------------------------------------------------------

この問題の趣旨を簡単に説明します。

要するに、長方形の対角線の長さを比較していく問題です。

問題は数学的思考を問う問題が多く出されます。

それだけでなく、多くの問題で読解力が必要とされます。

プログラミングができるだけでは解くのが難しいです。

さらに、どの問題でも共通することがあります。

それは決められた条件の中で値をインプット・アウトプットしなければなりません。

限られた時間の中で問題を解くというのが難しそうです。

３．世界大会での日本の成績

ほぼ毎年東京大学と京都大学が世界大会に出場しています。

他にも名のある大学が出場しています。

しかし、2012年までで大会開催以来1ケタの順位にランクインする大学が2000年時7位の京都大学を除いていませんでした。

そんな中で東京大学は2013年大会で３位、2014年大会で7位、2015年大会で世界3位と輝かしい成績を残しました。

2年連続1ケタという順位は素晴らしいですね。

しかも、参加大学数が2000年の時より倍になっています。

この勢いで多くの日本の大学が1ケタの順位になってほしいです。

頑張れ！日本！！

一応、世界大会における日本の大学の結果について記載されているリンクを張り付けておきます。

ICPC世界大会における日本の大学結果：http://icpc.iisf.or.jp/finals/

４．まとめ

以上がICPCについての説明です。

私も大学にいたころはプログラミングを中心に勉強していました。

しかし、ICPCの問題を見てみると難しくて解けません。

もしこの投稿を見て興味を持ってくださった方は、ぜひICPCの過去問を解いてみてください。