EPOCH@まつやま2010 予選問題
2010年の 11/27,28に愛媛県で開かれる第4回EPOCH@まつやまの本選にid:ichyo さんとチームふわふわドーナツで参加することになりました。
以下、予選問題について。
EPOCH＠まつやまとは
愛媛大学が主催する、与えられた問題を解くプログラムを速く正確に作ることをゲーム形式で競うコンテストです。
プログラミング人口の裾野を広げることを目的とし、プログラミング初心者から中級者を対象としているため、参加に以下のような制限があります。
大学生以上を対象とした競技形式（早く正確に解く）のプログラミング大会などで全国大会・国際大会相当で入賞した経験のある方はご遠慮ください．
過去のEPOCH本選成績を考慮します．すでに次の２つの条件のうちどちらかに該当する方はご遠慮ください．
過去２回本選最終ステージに出場している．
過去３回本選第一ステージに出場している．
大会趣旨をご理解のほどよろしくお願い申し上げます。
上の文を文字通りに受け取ると、
ICPCの国内予選を通過した経験があればだめ。
高校生以下を対象とする大会で、どれだけ好成績を残していても参加可能。
上級者は空気を読みましょう。
といった感じになるでしょう。
この制限で強い人が出てくるとすれば、プログラミングコンテストで上位入賞経験のある高校生や、ICPC国内予選で上位をだったが同じ学校でさらに上位のチームが複数いて出場できない、いわゆる学内予選*1に引っ掛かった人でしょうか
自分や銀杏さんのような、「C/C++を大学に入って使い始めたばかりの学部1年生」っていうのは向こうの想定している参加者層の一つじゃないかなとか勝手に思ってます。
予選、申し込み
EPOCH@まつやまでは、大会申込みの時に簡単なプログラミングの問題を３題解き、その解答とソースコードを提出し、その評価によって20人の本戦参加者が選ばれます。
予選に何チームぐらいの応募があるのかはわからないけれど、第一回、第二回は約140チームの応募があったそうです。たぶん愛媛県松山市がほとんど。
課題プログラムの評価というのは数値化されていませんが、公式ページには評価基準として以下のように書いてあります。
以下の手順（1）〜（4）で順位付けを行い，その結果を参考に実行委員会にてチーム選定を行いました．
（1）正確さ
テストデータを使って（ダウンロードいただいているものだけでなく別のものも使います）正しい出力が得られるかどうかをチェックします．
（2）実行速度
正解数（（1）正確さ）が同じ場合，すべての入力データに対する実行時間の合計が小さいほど上位とします．
実行はすべてのプログラムに対して当方で同じ条件で行います．
C, C++, Java ではそれぞれ条件が異なりますので，当方でその違いを（不利にならないよう）可能な限り調整します．（試験の成績でいうところの「偏差値」に相当する考え方を導入します）
（3）メモリ使用量
実行速度に差が無い（あるいは極めて小さい）場合はメモリ使用量の小さい方を上位とします．こちらも C, C++, Java では条件が異なりますので，当方でその違いを（不利にならないよう）可能な限り調整します．
（4）提出の早さ
上述の（3）までの手順でも差が付かない場合は提出の早い方を上位とします．
その他、同水準のチームが並んだ場合に、年齢やチーム、所属などで出場チームを決定するとあります。
とは言っても、本戦ではビンゴゲームやアタック25がプログラミングコンテスト仕様になったものですが、
テレビのクイズ番組やのど自慢の出場者選抜よりはよっぽど公平な基準で決められていると思います。
東京と京都のペアで変わった組み合わせだから出られる可能性が上がるんじゃないかと、とこはるさんは言ってたけれど、
「東京と京都の大学1年生枠」とかあったら自分のチームととこはるさんのチームで被ってしまうんじゃないかとか。
この基準を元に、プログラムのどこに力を入れれば良いかを考えると、問題で与えられる入力の個数が100万個あったりするなど、
アルゴリズムによって実行時間の差が十分に開くため、正しい出力を出すプログラムでなおかつ実行速度が速いものを目指せばよさそうです。
また、他の基準として、公式サイトに載っている情報処理学会への掲載記事には第一回の予選の評価基準として、以下のように書いてありました。
正答率は約 1/3 であった(3 問正解は 49 チーム).全テストデータについて正答していたチームのみを対象とし, チェックすべき数が少なかったこともあって,
1 名の教員がすべてのコードをチェックした.主に次の3項目について,レポート採点の感覚で 1 件ずつチェックした.
1)プログラムの体裁 インデントやコメント,空行を使って見やすいコードになっているか
2)変数名,関数名 目的や意図が分かるような名前付けを行っているか
3)プログラムの基本構造 構造化プログラミングが意識されたコードになっているか
それぞれの項目について 2 点満点を基本とし,改善すべき部分が見られるようであれば,その程度によって 1 点 ないし 2 点を減点した.
プログラムの良さを評価する上 で主観や個人の好みは避けられないが,今後参加チーム数が増加することを考えると,より客観的・定量的な基準・方式を導入することが必要だろう.
これは第一回の評価基準で、おそらく入力ケース数も少なくプログラムで差がつかなかったため、このような基準となったのだろうけど、
この基準でいくと目指すべきコードは
コメントを書かなくてもわかるようなコードを目指す。
なるべく無駄を省き、シンプルで分かりやすいコードを書く。
要するに、普段どおり書けばいい。
となります。
今回の予選でも、ソースコードにチェックが入るのは間違いないので、こういった書き方を意識したほうが良いのかもしれません。
予選第一問 数列の構成は同じ？
数列 X = {2,5,7,9,3} と 数列 Y = {7,5,9,5,7,9,3,2} は見た目は違うが、
どちらも2,3,5,7,9と、同じ整数から構成されているため、これを同じ構成の数列と呼ぶことにする。
複数の数列が与えられた時に、構成の異なる数列がいくつ存在するかを答えよ。なお、数列の個数Nは100,000万以下、登場する整数は1以上1000未満,整数の個数は256個以下で、数列の終端は-1で表される。
同じ要素の個数や順番を無視した集まりは、数学では数列ではなく集合(英:set)と言われます。
C++では、要素の集合を管理するコンテナであるsetを使います。
集合の集合の要素数を求めるので、setの中にsetを入れればよさそうです。
#include <cstdio> #include <set> int main(){ int n,y; scanf("%d",&n); set<set<int> > nums; for(;n>0;n--){ set<int> x; while(true){ scanf("%d",&y); if (y==-1)break; x.insert(y); } nums.insert(x); } printf("%d\n",(int)nums.size()); return 0; }
今確認したところ、提出したコードにはミスがあって、内容そのままでcstdioの代わりにiostreamをincludeしてました。
自分の環境 i686-apple-darwin10-g++-4.2.1 (GCC) 4.2.1 (Apple Inc. build 5664) では何も(-Wallをつけても)エラー無く通ったけど、
今確認したら、いちょうさんの環境では
epoch01.cpp: In function ‘int main()’:
epoch01.cpp:8: error: ‘scanf’ was not declared in this scope
epoch01.cpp:19: error: ‘printf’ was not declared in this scope
とエラーが出てました。向こうが直してくれたのか、向こうの環境でたまたま通ったのかは知らないけれど、ヒヤッとした...
予選第二問 素数暗号
0〜10,000,000までの整数列が与えられ、最後は-1で終わっています。
一行目から順に整数を読み、その数値が素数pであれば、1からpまでの素数の個数を52で割った余りp%52を
アルファベット大文字、小文字に対応させ、合成数であればアンダースコア_に対応させる。この規則に従って解読し、文字列を出力せよ。
銀杏さんのソースコードを提出しました。
1000万までの素数とその順番をエラトステネスのふるいによって求めるプログラムだったと思います。
自分の学校から応募したid:tokoharu-sakuraさんとid:osa_kさんに聞いてみると、
二人とも1000万までの素数をソースコードに埋め込んでいたみたいです。フォームで応募するのが重そう...。
予選第三問 n番目に大きい分数は？
N個の分数の中でn番目に大きいものを入力と同じ形で出力してください
分数は a/b (a,bは-10000以上10000以下の整数,b≠0)の形で表されます。ただし 10<=N<=1,000,000とします。
n番目の要素を求めるのに、
c++のソートアルゴリズムのひとつであるnth_elementを使用します。
ちなみにSTLのソートアルゴリズムには計算コストの低いものから、
partition,stable_partition,nth_element,partial_sort(&partial_sort_copy),sort,stable_sort
があり、nth_elementまではO(n)で実行することができます。
分数は分子と分母の構造体として持ち、有理数として比較を行いました。
#include<string> #include<vector> #include<algorithm> #include<functional> #include<cstdio> struct Fraction { int numer; int denom; bool operator >(const Fraction& f) const { if (f.denom*denom>0) if (numer * f.denom > denom * f.numer) return true; else return false; else if (numer * f.denom > denom * f.numer) return false; else return true; } }; int main(){ int n,m; vector<Fraction> frac; scanf("%d %d",&n,&m); for(;n>0;n--){ int a,b; char s; scanf("%d/%d",&a,&b); Fraction f; f.numer = a; f.denom = b; frac.push_back(f); } nth_element(frac.begin(),frac.begin()+m-1,frac.end(),greater<Fraction>()); printf("%d/%d\n",frac[m-1].numer,frac[m-1].denom); }
また、includeが変なことになってました。気を付けないと...
予選突破について
6/15〜9/30の応募期間で、
最終提出が9/29,9/30だったとこはるさん、osa_kさんが共に本選に参加していることから、
提出期間はあまり関係がなかったみたいです。
やっぱり、だいたい実行速度で決まったのだろうな...と。
この記事がEPOCH予選通過のための参考になれば幸いです。
本選に向けて
ちょっと最近アルゴリズムより開発の方に寄ってる気がする...。
昨日、銀杏さんにAOJの解いた問題数で抜かれたし...。
とりあえず蟻本を持ってけばなんとかなるかもとか...。
楽しみです。わくわく。
