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の解いた問題数で抜かれたし...。
とりあえず蟻本を持ってけばなんとかなるかもとか...。
楽しみです。わくわく。
SRM 485 DIV2 参加記
3回目のtopcoder、今回こそはレートを上げたい。
250
指定した範囲の価格帯で、末尾に連続する9が最も多くなるような数*1のうち、最も高いものを出力する問題。
与えられた価格帯の最大値以下の数で9がn個続く数を価格帯の最小値を下回らない範囲で順に求め、最後に求まったものを出力する
例:4325の場合
4325,4319,4299,3999
class MicrowaveSelling { public: int mostAttractivePrice(int minPrice, int maxPrice) { int result = maxPrice; int d = 10; while(minPrice<=(maxPrice+1)/d*d-1){ result = (maxPrice+1)/d*d-1; d*=10; } return result; } };
値の範囲が100万までなので1ずつ調べてる解法などもありました。
結果
Systemtest Passed
500 偶数がこわいの
等差数列の、偶数の項を奇数になるまで2で割り続けることで、できる奇数だけの数列が与えられ、
そこからもとの等差数列を求める問題。
複数解が出る時は辞書順で最小のものを出力する。
解がsigned int型の範囲に収まることが保証されているので一つの項に掛けることのできる2の数は32回未満、
よって、与えられた初項と第二項が取りうる値を順にループで変化させ、
その差を公差になっている等差数列を作ることができるかを調べました。
class AfraidOfEven { public: vector <int> restoreProgression(vector <int> seq) { vector <int> r; r = seq; bool ans = false; for(r[0] = seq[0];;r[0] *= 2){ for(r[1] = seq[1];r[1] > 0;r[1] *= 2){ int diff = r[1]-r[0]; ans = true; for(int i = 2;i<seq.size();i++){ r[i] = seq[i]; while(r[i]<r[i-1]+diff&&r[i]>0){ r[i]*=2; } if(r[i]>r[i-1]+diff||r[i]<0){ ans = false; break; } } if(ans)break; } if(ans)break; } return r; } };
えっと、元の数列のすべての項が偶数になることはないから、
公差が偶数だとしたらすべて奇数で等差数列を既に満たしている状態であり、
それ以外の場合は公差が奇数になるので、
元の等差数列の偶数番目を取り出した数列か奇数番目を取り出した数列のどちらか片方には奇数しか現れないため、
与えられた等差数列を１つ飛びに取り出せば、どちらかはもとの等差数列の一部になっているというのを聞いた。
ふーん。
結果
Systemtest Passed
1000
開いたけど見てない
結果
oox
1025→1149
はじめてレーティング上がった！
AIコンテストに参加してきました。
ぼくのかんがえたさいきょうのAI
10/16に品川シーサイド楽天タワーで行われた楽天テクノロジーカンファレンス2010のイベントとして開催されたAIコンテストに参加してきました。
概要
ゲーム説明
CastleAttackというゲームのAIを作りました。
詳しいゲーム説明は公式ページのゲーム説明ドキュメントを参照
> http://www.washi.cs.waseda.ac.jp/rakuten-waseda-pc2010/question.html
図：ゲーム説明ドキュメントより
手前から時計回りに配置された赤、青、緑、黄の４チームがこの順で行動するターン制で、自分のターンには、自分の色のタイルと兵士を動かすことができます。
全員が行動したのを1フレームとし、一試合は1000フレームで行われます。
カーソル
カーソルは2x2の大きさを持っていて、位置座標と回転方向(時計回り、反時計回り)を定めることで、カーソル内の4つのタイルを時計回りまたは反時計回りに回転させることができます。
ただし、自分のタイルがカーソル内に存在しなかったり、兵士がカーソル内に存在するような位置にカーソルを持ってきても回転させることはできません。
図：ゲーム説明ドキュメントより
兵士
自分のタイルまたは、門の上を、毎ターン左右上下に１歩ずつ動くことができます。
相手の小門または大門に入ることで相手のScoreを削って自分のものにすることができます。
相手の門に入ったあと、その兵士は消滅し、自国の大門に新しい兵士が現れます。
残りフレーム数が150を切ったあと、自国から出現する兵士はスーパー兵士となり、
相手国の門に入ったときに獲得できるScoreはそれまでの2倍となります。
スコア
すべてのチームが初期スコア100を持った状態から開始します。相手の兵士に攻めこまれた国は以下に定める倍率の分のScoreを失い、攻め込んだ国がその分のScoreを得ることができます。
図：ゲーム説明ドキュメントより
結果
予選
グループ1位通過(1位4回,2位5回,3位1回)
決勝トーナメント
1回戦1位
準決勝1位
決勝(２本先取）
決勝1回戦 1位
決勝2回戦 2位
決勝3回戦 2位
というわけで、準優勝でした。やった！
優勝以外特に賞品はないみたいです。
戦略
カーソルの移動
ゲームの状況を評価する関数を作り、自分のターンに、すべてのカーソルの動かし方を試した時に最も評価値が高くなるような行動を取るようにする（いわゆる一手読み）
すべての盤面について、その盤面が自分がどれくらい有利な配置になっているかを定めることが出来れば、それが大きくなるようなものを選択していくことで自動的に理想的な形に近づく
評価の方法はいろいろあるが、自分から見た盤面位置の一つ一つにScoreを割り当て、自分の色のタイルがある位置のScoreの総和を評価関数とした。
盤面の位置にポテンシャルを持たせて高くなる方向に推移するため、アリ地獄のように勝手にタイルが集まってくる。
理想の形
左右の門と自国の門の近くはScoreが高くなるようになっている。
兵士の移動
カーソルと違ってこだわるところは少なく、基本的に相手への門が完成していれば、そこを目指すようなものを作ればよい。
詳しい仕様はソースを参照。
評価関数を使うかどうか
今回のAIではカーソルは1フレーム毎に評価をしたが、兵士AIは評価関数を使わずに、経路を保持してそれを進むようなアルゴリズムだったが、
もし、兵士の動きを評価関数で定めるとしたら、「獲得できるScoreをその門までの距離で割ったものが大きくなる方向に進む」などとすれば良いかもしれない。
先読みについて
オセロや将棋など、二人ゲームでは評価関数を先の方の手まで調べることで、より正確な強さを評価できるようになる。
今回は一手にそんなにたくさんの処理を行えないということとと、４人が行動するため先読みが難しいこと、
さらに、一手で形成がひっくり変わるオセロや将棋などと違って、形成が有利かどうかは大体線形に変化することから*1、先読みは行わなかった。
実装すれば、あと２手動かしたら経路が完成するとか、そういうのを調べたりできたかもしれない(が、時間がかかったりうまく動かないかも)。
バグ
「敵兵士のいる位置を評価対象に含めない」を実装したつもりだったが、提出したソースでは消してしまっていた。
[10/10/11 20:22:05] とこはる: 基本のできてないＡＩは負けるよ…
ごめんなさい
[10/10/15 0:17:32] とこはる: やっぱり他プレイヤーの動きをカーソルの動きに考えなかったことの被害は甚大で、優勝は無理だろう
わかったからそんな責めないで...
このバグのせいで、崩された自国のタイルを修復する時に相手の兵士のいるカーソルを選んでしまい、結局防げないままになることが多く、Uriboさんのように、相手正門に兵士ごと突撃するアルゴリズムにはめっぽう弱くなった。
あっさりと正面が崩される...。
本番で見られた動き
序盤に得点の高いチームを狙うようなアルゴリズムを持った他のチームに狙われることを防ぐために、序盤は攻撃を控えたほうが良いというのをウサギィさんが実装していた。
最初は取られた分の得点は後で取り返せば良いと考えていたけれど、決勝２回戦ではWantzが最初にScoreを取ることで他のチームに狙われることで良い形を作れなかったりしたので、
ものすごく効果を発揮していた。
この辺りも調整が難しそうなところだけれども。*2
ソース
本番で使われたものから上記のバグを修正したもの。
Wantz2.java
http://w125.sakura.ne.jp/wiki/index.php?plugin=attach&pcmd=open&file=Wantz2.java&refer=CastleAttack
Emacs導入
ふと、テンプレート自動挿入機能が使いたくなったので、
この機会に本格的にEmacsを使ってみようとaquamacsから、CarbonEmacs http://homepage.mac.com/zenitani/emacs-j.html へと移行。
カレントディレクトリに.emacs.el ファイルを作り、こんな感じに設定しました。
;;行数表示
(line-number-mode t)
;; Macのキーバインドを使用、optionをメタキーにする
(mac-key-mode 1)
(setq mac-option-modifier 'meta)
;;shift+カーソルキーで範囲選択
(setq pc-select-selection-keys-only t)
(pc-selection-mode 1)
;;ビープ音を消す
(setq visible-bell t)
;; タブキー
(setq default-tab-width 2)
(setq indent-line-function 'indent-relative-maybe)
;; フォント設定
(if (eq window-system 'mac) (require 'carbon-font))
(fixed-width-set-fontset "hirakaku_w3" 10)
(setq fixed-width-rescale nil)
;; ウィンドウ設定
(if window-system (progn
(set-background-color "Black")
(set-foreground-color "White")
(set-cursor-color "Gray")
))
;;テンプレート設定
(require 'autoinsert)
(setq auto-insert-directory "~/source/insert/")
(setq auto-insert-alist
(append '(
("\\.cpp" . "template.cpp")
) auto-insert-alist))
(add-hook 'find-file-hooks 'auto-insert)
;;透明度
(add-to-list 'default-frame-alist '(alpha . 85))
;; ビープ音を消す
(setq visible-bell t)
;; ElScreen タブ化
(require 'elscreen)
(if window-system
(define-key elscreen-map "\C-z" 'iconify-or-deiconify-frame)
(define-key elscreen-map "\C-z" 'suspend-emacs))
