鴨研究室

鴨研究室
ACM/ICPC の誤答の分析
理学部　情報科学科　鴨研究室　４回生　08251887　谷口真穂
1 研究背景と目的
審判団の提示する入力データを各プログラ
ムに実行させ、正解と比べる作業も行った。
ACM/ICPC で得られた誤答プログラムを分析
することで、次以降の作題に役立てたいと
審判団は考えていた。しかし、分析の自動
化の困難性、次期アジア地区予選の作題の３研究結果、考察
ため難しい現状だった。(審判団の一員であ
る鴨浩靖も以前挫折した経験がある。)
本研究では、誤答を分析する事で次以降の結果の一例を挙げる。
作題に役立たせる事を目的とする。
誤答の中で、プログラム自体のミスかプ
ログラム自体は正解していたが提出するま
ACM/ICPC とは、ACM が主催する大学生を
対象にした世界的規模のプログラミングコでの操作ミスが原因で誤答に分類されてい
ンテストである。ICPC とは世界最古かつ最るかによって分ける事ができる事が分かっ
大の教育および科学コンピューティング協た。また、１つのチームが同じ問題で数回
提出している場合がある事が分かった。
会である。
詳しい事に関しては、卒業研究発表会と
卒業論文にて報告する事にする。
２研究内容
本研究は、ACM/ICPC の国内予選で集めら
れた誤答分類の有意性について考えるもの
である。特に、プログラムのどの節を重点
に黙視すべきかを問題パターンごとに考え
る事にする。
国内予選の全７問中２問は正解数が非常
に少なかったため、５問を研究対象にした。
本論文では、５問中３問について論じる。
問題を A,B,C と呼ぶ事にする。問題の傾向
は以下のものである。
A 入力値に応じた範囲内の素数を数える問
題。想定解法の一部は以下の通りである。
• エラストテレスの篩で素数判定表
を作り、増減を追いかける方法で小
さい方から順に値を求め表にする。
• 試し割りアルゴリズムを作り素数
判定して数える。
４まとめと今後の展開
来年以降の誤答分析を重ねることにより、
精密なデータになると考えている。
本研究の結果が、プログラミングコンテス
トの審判団にとって次以降の作題のために
役立つ事を期待する。
B　ある種のパズルを解く問題。想定解法の参考文献
一部は以下の通りである。
• 深さ優先検索あるいは幅優先検索
[1]ACM-ICPC: ACM International
• BFS か CFS
Collegiate Programming Contest Asia
Regional Contest 2011 in
Fukuoka
C　地区ごとの電力使用量と総供給電力が与 http://icpc2011.ait.kyushu-u.ac.jp/ja
えられたとき、ある基準で最も合理的な論
番停電計画を作成する問題。想定解法の一 [2]鴨浩靖
部は以下の通りである。
「Datalore」http://taurus.ics.nara• 動的計画法あるいはメモ化
wu.ac.jp/aldebaran/acm-icpc/
ACM/ICPC 解答の分析
奈良女子大学情報科学科数理情報学講座鴨研究室　久保田梢
1.研究の背景と目的
ACM-ICPC の審判は長年答案の分析を行い、
次回以降の作題に活かしたいと思っていた。
しかし、その手段としてプログラムを人間が
目視する以外方法がなく自動化できないこと、
また審判はアジア地区予選の作題をしなけれ
ばならないことなどから時間が取れず実際に
分析を行えずにいた。そこで審判に協力し、
答案プログラムの分析を行い今後の作題に役
立てようとした。
2.ACM/ICPC とは
ACM(the Association for Computing
Machinery)は、世界最古・最大の教育および
科学コンピューティング協会である。また、
ACM-ICPC(ACM International Collegiate
Programming Contest)は、大学生を対象とした
コンピュータープログラミングにおけるコン
テストである。日本から参加する場合、国内
予選→アジア地区予選→世界大会の三段階に
なる。
3.使用データ
ACM-ICPC2011 国内予選のデータを使用し
た。
4.分析方法と結果
今回の研究では国内予選を対象とした。ま
たこの研究は 2 人共同で行ったが、今回は研
究結果の一例だけ発表する。
プログラムを使用している言語(C,C++,java)
で分ける。いくつか解き方を想定し、目視で
確認していく。想定外のものが出てきた場合
どのようなアルゴリズムか考える。さらにそ
の中で、ライブラリを利用しているか、文字
列ライブラリをどれだけ使うかなども見てい
く。またスタックを自分で作る際、どのよう
なデータ構造を採用しているかなどでも分け
ていく。さらに判定式の式の違いも見ていく。
その分類結果から使用した言語とアルゴリズ
ムなどとの関係、言語ごとの正答率などもわ
かる。
2011 年国内予選問題 B の分析結果の一部
問題の概要
与えられた文字列が、( )と[ ]についてバラン
スしているか判定する。
この問題については以下の 2 つのアルゴリズ
ムが予想された。
⑴スタックを利用する
⑵括弧以外の文字を取り除いていく
しかし実際には⑵の方法は全体の 4％以下し
かなく、⑴が 80％以上を占め、予想されな
かった LL⑴ を用いたものが 2 番目に多く見ら
れた。この結果、審判が予想しなかったアル
ゴリズムでプログラムを書く参加者がいるこ
とがわかった。
5.まとめ
この結果は次回以降の ACM-ICPC の作題に
活用される予定である。また、プログラミン
グ演習の採点にも役立てることができる。さ
らに来年以降も続けていけばより精密な結果
が得られる。
6.参考文献
ACM-ICPC 2011 IN Fukuoka
http://icpc2011.ait.kyushu-u.ac.jp/ja/home

Download Report