H27年度　情報工学実験および演習２　　　　　　　　　　　　　　　　　　　　　　　　　2015.4.30 MS(Ver.2)

ACMプログラミングコンテストを利用した実践的プログラミング

[背景]

　ACMプログラミングコンテスト[1][2]は米国計算機科学学会(ACM)が主催するプログラミングコンテストで，各国の国内予選[3]，地域予選（例えばアジア地区予選）を勝ち抜いたチームが毎年5月ごろに行なわれる世界大会でプログラミング，チームプレイの技を競うコンテストです．実際のコンテストでは簡単なプログラムがかければ解ける問題から，幾何学等の数学の知識，や複雑なアルゴリズムを組み合わせないと解けない問題まで，出題される7問程度の問題を3時間以内にとくプログラムを作成し，審判が用意したテスト入力データにたいして動作確認を行い正確に動作するまでの時間と解けた問題数でスコアを競うコンテストです．ACMコンテストでは，3人で１つのチームを構成し，各チームに割り当てられた1台のコンピュータを3人で共有してプログラム開発を行います．予選ごとに若干のルールが追加されることがあります．（例えば，最近の日本国内予選では日本語で書かれた問題も提供される）．コンテストでは単にプログラムが作れればよいというだけでなく，3人が1台のコンピュータをいかに効率よく使うかというチームプレイも重要になります．問題選択，問題理解，アルゴリズム設計，プログラム入力，デバッグを誰がどのタイミングで行なうかという戦略も重要です[4]．

　大学生のプログラミング技術を競う国際大会として，国内外から高い評価を与えられている大会で，当学科からもH20年から連続出場しています[5]．

[目的]

　プログラミングの授業を一通り終えた時期に，①授業の試験問題や演習問題ではない現実世界で起こりえる実践的な問題として与えられた課題を解決するプログラミング開発の経験と，②データ構造やアルゴリズムの知識をいかに活用して実際の問題を解くか，あるいは逆に複雑なデータ構造やアルゴリズムを使わない戦略を選ぶのか等々，非常に多くのプログラム戦略（解法）が存在するなかから，『限られた時間』で『正しく動くプログラム』[6]をつくるという（非常に短時間ではありますが）『工程管理』の経験をすること，③これらを通して『情報系の設計工学』を経験することが実験の目的である．

[実施形態] (全日程概要)

この実験では，4/30, (6/26), 7/9, 7/16 の3回に跨って実施します．本日(4/30)にこの後，早速学科内予選を行ないます．その結果をもとに，上位10名程度+αで３ないし4チームを構成し6/26(金) 16:30—19:30 に行なわれる国内予選に参加します．（他学年の学生とチームを構成する可能性もあります）．

　全員に出席義務がある2回目は　7/9(木) です[7]．3回目は7/16(木)ですが，国内予選に参加した人はこの日は出席を免除します．

各実施回毎の内容は以下のとおりです。

[1] 公式ページ　http://icpc.baylor.edu/

[2] 3分でわかるACM プログラミングコンテスト　http://icpc.iisf.or.jp/acm-icpc/3min/

[3] http://icpc.iisf.or.jp/

[4] http://xrds.acm.org/article.cfm?aid=1349341

[5]　今までの最高記録は修士1年生のチームがH22に出した120位台（@２問正解）です．

[6] 「コンパイルエラーが出ない」のと「正しく動く」のは全くことなります．特定の入力パターンのみで動くプログラムではなく，（仕様で定められる範囲の）いかなる入力データ（系列）に対しても正しく動く必要があります．

[7] 国内予選参加者は解けた問題数によっては7/9の出席を免除する可能性があります．