JavaChallenge2012で考えるAI対戦型ゲームのデザイン
Competitive Programming Advent Calendar Div2012の22日目の記事になります。
遅刻しました、申し訳ありません。
最近、自分は2つのプログラミングコンテストProgramming Contest
に運営側として関わらせていただきました。
特にJavaChallenge2012はルールの作成を担当したので今回はAI対戦型コンテストのルール設定について思うことを書きたいと思います。
主にゲームの解説になるので、ルールを読んだ方、参加者以外にはピンとこないかもしれませんがご容赦ください。
JavaChallenge2012とは
- 国際大学対抗プログラミングコンテスト、ICPCのアジア予選の余興として行うプログラミングコンテストだよ
- 対戦型ゲームのAIをJavaで書いて戦わせるよ
- 今年は事前に
- 公用語はICPCと同じく英語
ルール概要
詳しいルールはこちらのマニュアルより。
マニュアルによるとGalconっていうゲームとカタンの開拓者達を合わせた感じのゲームらしいです。
マップ詳細
- HEXマップの頂点と辺部分を使用
- プレイヤーは2人〜6人まで
- マップ中にランダムに40個の拠点が置かれる
- 所有者のいる拠点からは毎ターン資源とロボットが生まれる
- 各資源は銀行と取引したり、ユーザー間で取引できる
- 各拠点は初期ロボット数、産出される資源数、産出されるロボット数などが異なる
ルール
- ロボットを他のプレイヤーのロボットと同じ地点に送ると、対になって消失し、多い方のプレイヤーのロボットが残る。
- 拠点にある他プレイヤーのロボットより1個以上多くのロボットを送ることで拠点の所有者が交代する
- 初期配置選択フェーズの後各プレイヤーが順に200ターンの行動を行う
初期配置選択フェーズ
- 拠点を"プレイヤー1→プレイヤー2→…→プレイヤー6→プレイヤー6→…→プレイヤー1"の順で2つ選択
各ターンの行動
プレイヤー1から行動を開始する。以下の行動は自分のターンに好きなだけ行うことが出来る。
- ロボットの起動
- 自分の所有している拠点にいるロボットを別の拠点へと移動させることが出来る。
- ロボットは1辺を1ターンに1ずつ移動する。
- 攻め込むルートを指定することも出来るが、省略すると最短ルートを自動的に計算して侵攻する
- ユーザー間交渉の値段の提示
- 資源、個数、金額のペアで提示する。その条件は1ターンの間他プレイヤーが確認、取引を受けることができる。
- 提示されている条件を受ける
- 提示された資源の個数の一部のみに対して取引を行うことも可能
- 銀行との売買
- 資源をお金に換えることが出来る
- 拠点のグレードアップ
- 決まった資源を使用して、拠点をグレードアップすることが出来る。資源生産量を2倍,4倍、ロボット生産量が2倍,4倍にするグレードアップがある
勝利条件
200ターンを終えるか,拠点を所有しているプレイヤーが1人だけになった時に終了、以下の基準で順位が決まる（上が優先）
- 生き延びたターン数
- 終了時点での制圧数
- 総ロボット数
- 資源を売った額+所持金の合計
ルールの設計について
今回JavaChallenge2012のゲームを作るに際して、普通の対人戦ゲームと異なる点として、盤面を数値の形で評価しやすいようなルール設計にすることを考えました。
また一方で、AI対戦型ゲームの場合は人間がロジックを考えるリソース、コード量、実際の計算時間をゲームのどの部分に割くか自由に決めることに注目しました。
今回のゲームでは最初の行動が非常に重要なゲームとして設計しました。イメージとしては初期配置が半分、最初の50ターンの立ち回りが半分ぐらいといったところ。見た目にはどんどん制圧していきマップをトップのプレイヤーの色に染め上げるのは綺麗だけれども、逆転を誘発するルールはなく100ターン経過後のトップと200ターン経過後のトップはほとんど変化していません。
数値化について、、ロボットの所持数、総生産力、各資源の所持数、各資源の総生産力などをAPIから呼び出せ、またゲーム画面上でも確認出来るようになっています。
ルールをモデル化すると、ロボットの個数の差で拠点を制圧する力関係が決まるため、ロボットの個数を増やすことをゲームの目的とみることが出来ます。そして、ロボットの個数を増やすことは各拠点のロボット生産力を合計した、総ロボット生産力を高めることに繋がります。
ロボット生産力を高めるための行動としては、
- 資源を使って拠点をアップグレードし、資源生産力を増加
- 資源を使って拠点をアップグレードし、ロボット生産力を増加
- ロボットを使って拠点を制圧、資源生産量、ロボット生産力を増加
こんな感じでモデル化することが出来ます。初期配置についても、初期のロボット数、ロボット生産力の高さ、資源の内容、資源生産量、また周りの拠点との距離や周りの拠点の生産力、をユーザーが独自で数値化すると、良さげな初期配置の評価が出来たのではないかと思います。
取引については上述の通り、最初の数ターンの行動が非常に大事なので、そこで最善手を選ぶと、銀行との交渉、ユーザー同士の交渉を持ちかける意味はあるように思います。けれども、少なくとも2チームのプレイヤーが取引を実装していないと無駄になることもあり、限られた時間の中で手をつけたチームはほとんどなかったため、今回はルールとしては死んでしまいました。
それ以外では、既に敵に所有されている拠点の場所を考慮したり、敵の侵攻ルートを考慮し消滅を避ける戦術、狙われにくくする戦術などの工夫が上位チームやゲストチームで見られました。
サンプルコードについて
限られた時間の中でAIを作成してもらうために、サンプルコードは
- サンプルコードを読んだだけでAPIが理解出来る
- 拠点を評価順にソートするコードなど強いAIを作るための部品を揃えておく
- サンプル自体は弱く、改良しがいがあるものにする
を意図して書きました...が、思った以上に強くなってしまいました。
サンプルを改良したつもりでももとのサンプルを超えられなかったという悲鳴を聞いたり、サンプルコードと提出されたコードを戦わせるとサンプルコードが上位に入ってしまった...など。
弱くなるように色々なパラメータをいじったはずが依然として、強かったというのは、そもそもサンプルで用意した、「自分の所有しているすべての拠点に対して、ロボットが一定数以上あれば、そこから最も近い拠点を攻撃する」という行動が理にかなっていたためでした。
ルール設計側がサンプルを書くと気付かずについついゲームの本質を突いてしまうので、そこを弱くする修正は念入りに行った方が良さそうです。
告知
- さっきから何度か貼りましたが、JavaChallenge2012のウェブサイトが完成しました。結果や、ゲームのダウンロードが可能です。
Bogobogosortについて
遅いソートアルゴリズム
Bogobogosortという、名前からして恐ろしいソートアルゴリズムを知ったきっかけはtodo314さんのこのPostからでした。
ボゴソートより計算量の大きいソートアルゴリズムってあるのかしら。論文あるか調べてみようかな。
遅いソート方法というと、どこまでの無駄が許されるのかという話になってくる気もしますが、例えば以下のURLではkinabaさんが情報量が0である比較を除いた計算量について考察されてます。
今回のようにボゴソートのO(n*n!)がソートアルゴリズムとして許容されるとなると、結構なんでもありな気がしてきます。
まず、よく知られているソートアルゴリズムでボゴソートと同じくらいの計算量を持つものには
- ボゴソート：ソートされたものが見つかるまでrandom_shuffle
- ボゾソート：ソートされるまでランダムに選んだの2つの要素を交換
- permutation sort ：順番が揃うまでnext_permutation
などがあります。
その時のTLでみたアルゴリズムではstacさんの
1/2の確率でランダムにnext or prev permutationを行う
というアイデアが秀逸でした。ランダムウォークみたいな話です。計算量はO((n!)^2)辺りになりそう。
Bogobogosort
そうしていると、todo314さんからbogobogosortがあるとのPostが。気になる。
Bogobogosortというソートアルゴリズムがある。ぱない。
詳細はこのサイトより。以下はその抄訳と説明。英語に抵抗ない人はリンク先を読んだ方が良いと思います。
DM's Esoteric Programming Languages - Bogobogosort
Bogobogosortは、有名なbogosortを基にしたソートアルゴリズムで、これを理解するにはまずボゴソートの細かい部分を理解する必要があります。
- リストがソートされているかチェックし、されていれば停止、違えばStep2へ
- リストをランダムに並び替える
- Step1に戻る
比較が線形時間、ループが平均n!/2回で、計算量O(n*n!)という、非常に効率的なアルゴリズムです。
Bogobogosortの特徴はリストがソートされているかどうかのチェックに再帰を用いることです。再帰というのは常にgoodでcoolですから。
Bogobogosortではボゴソートのチェックの部分を以下のようにします。
- 元のリストをコピーしたリストを作成します。
- コピーしたリストの先頭からn-1要素をbogobogosortを使ってソートします。
- コピーのn番目の要素がn-1個の要素の最大値より大きければ、コピーはソートされている。違えばコピーの順番をシャッフルし、もう一度Step2からやり直す。
- ソートされたコピーが元のリストと同じかどうか比較する。
これをボゴソートのStep1で行われるようにしたものがbogobogosortです。
C++での実行結果は
n Time (seconds)
1 0.0000
2 0.0000
3 0.0008
4 0.0054
5 0.0745
6 450
7 一晩中動かしたが終了せず
コードが載ってないので書いてみました。
- bogosortのC++による実装
- bogobogosortのC++による実装
n=6でも終わらないんだけど...あれれ?
bogobogosortぐらいになると乱数の使用回数が馬鹿みたいに多いので、乱数生成にMTとか使った方が良かったのかもしれません。
計算量がアッカーマン関数程度になるような面白いものを見つけたい。
昨日思いついたゲーム
1.3つの正整数の組(a,b,c)が入る集合を考える。
2.集合に初期値(a0,b0,c0)を含める。3.
集合に(a,b,c)が含まれている時
d1 = (b+c)%a
d2 = abs(b-c)%a
d3 = (b*c)%a
を作り、d1,d2,d3が0でないものを
(b,c,d1),(b,c,d2),(b,c,d3)として集合に含まれる4.すべての要素が3の条件を満たすまで要素を追加する。
5.要素の個数を数える。
なるべく要素が大きくなるようなものを見つけたい。
性質
0
JOI予選の問題を解いてみる
現役の時は参加しなかったので、参加するのは去年に引き続き二回目。
準備ができてなかったどころか寝過ごしたのでひどい。
1問目
問題
食事a,b,c,ドリンクd,eが与えられる。食事とドリンクをセットで注文すると50円引きになる。最も安いセットの価格を出力する。
方針
数値a,b,cの中の最小値とd,eの中の最小値を足して50を引いた値を出力する
#include<iostream> #include<cstdio> #include<vector> #include<string> #include<algorithm> using namespace std; int main(){ int a,b,c,d,e; cin>>a>>b>>c>>d>>e; cout<<(min(min(a,b),c)+min(d,e)-50)<<endl; return 0; }
2問目
問題
組み合わせ対戦結果から順位を求める。
方針
スコアでソートして順位を割り振った後に、チームidでソートして出力。
解答
#include<iostream> #include<cstdio> #include<vector> #include<string> #include<algorithm> #include<utility> using namespace std; typedef pair<int,int> PII; int score[100][100]; int main(){ int n; cin>>n; vector<PII> points(n); vector<PII> ranks(n); int a,b,c,d; for(int i=0;i<n*(n+1)/2;i++){ cin>>a>>b>>c>>d; if(c==d){ score[a-1][b-1] = 1; score[b-1][a-1] = 1; } else{ score[a-1][b-1] = c>d?3:0; score[b-1][a-1] = d>c?3:0; } } for(int i=0;i<n;i++){ int p = 0; for(int j=0;j<n;j++){ if(i!=j){ p += score[i][j]; } } points[i] = PII(p,i); } sort(points.begin(),points.end()); reverse(points.begin(),points.end()); int sc = -1,rank = 0; for(int i=0;i<n;i++){ if(points[i].first != sc){ sc = points[i].first; rank = i; } ranks[i] = PII(points[i].second,rank); } sort(ranks.begin(),ranks.end()); for(int i=0;i<n;i++){ cout<<ranks[i].second+1<<endl; } return 0; }
3問目
問題
みんながよくやる金額当たりのカロリーを最大化する問題。基本料金、カロリーが決まっているピザにトッピングを乗せる。トッピングの値段は一律で、カロリーのみが違う。
方針
トッピングのカロリーの大きい順にソートして、トッピングを足していった時の(カロリー/金額)の最大値を取る。
解答
#include<iostream> #include<cstdio> #include<vector> #include<string> #include<algorithm> using namespace std; int main(){ int n,cost1,cost2,cal1; cin>>n; cin>>cost1>>cost2; cin >> cal1; vector<int> cal; int cc; for(int i=0;i<n;i++){ cin>>cc; cal.push_back(cc); } sort(cal.begin(),cal.end()); reverse(cal.begin(),cal.end()); int ans = cal1/cost1; int m = 0; for(int i=0;i<n;i++){ cal1 += cal[i]; cost1 += cost2; ans = cal1/cost1; m = max(ans,m); } cout<<m<<endl; return 0; }
4問目
問題
メニューが3種類あり、いくつかの日食べるメニューは決まっている。
3日続けて同じメニューが現れない条件で、メニューの決め方は何通りあるか。
10000で割った余りを出力する。
方針
前二日のメニュー9通りx日数でDPを掛ける。同じメニューが3日続いていたり、メニューが決まっている日を考慮する。
解答
#include<iostream> #include<cstdio> #include<vector> #include<string> #include<algorithm> using namespace std; int dp[9][100]; int menu[100]; int main(){ for(int i=0;i<9;i++){ for(int j=0;j<100;j++){ dp[i][j] = 0; } } for(int i=0;i<100;i++){ menu[i] = -1; } int n,k; cin>>n>>k; int a,b; for(int i=0;i<k;i++){ cin>>a>>b; menu[a-1] = b-1; } if(menu[0] == -1&&menu[1] == -1){ for(int i=0;i<9;i++){ dp[i][1] = 1; } } else if(menu[1] == -1){ for(int i = 0;i<3;i++){ dp[menu[0]*3+i][1] = 1; } } else if(menu[0] == -1){ for(int i = 0;i<3;i++){ dp[i*3+menu[1]][1] = 1; } } else{ dp[(menu[0])*3+menu[1]][1] = 1; } for(int i=2;i<n;i++){ for(int j=0;j<9;j++){ dp[j][i] = dp[j/3][i-1] + dp[j/3+3][i-1] + dp[j/3+6][i-1]; } dp[0][i] -= dp[0][i-1]; dp[4][i] -= dp[4][i-1]; dp[8][i] -= dp[8][i-1]; if(menu[i] != -1){ for(int j=0;j<9;j++){ if(j%3 != menu[i]) dp[j][i] = 0; } } for(int j=0;j<9;j++){ dp[j][i] %= 10000; } } int sum = 0; for(int j = 0;j<9;j++){ sum+= dp[j][n-1]; } cout<<sum%10000<<endl; return 0; }
問題5
問題
ハニカム構造で出来たマップに建物があり、それを取り囲むイルミネーションの長さを求める問題。
イルミネーションは外から見える場所にのみ設置する。
方針
外側からbfsを掛け、「外側」を特定する。それぞれの建物が「外側」に面している個数を数える。
解答
なぜか01がくっついた文字列の入力だと勘違いしていたのでstringで実装してます。
ハニカム構造ライブラリとか持ってないや。
#include<iostream> #include<cstdio> #include<vector> #include<string> #include<algorithm> #include<queue> using namespace std; typedef pair<int,int> PII; int main(){ int w,h; cin>>w>>h; vector<string> field; string s; for(int i=0;i<h;i++){ string s=""; int a; for(int x=0;x<w;x++){ cin>>a; if(a==0)s+="0"; if(a==1)s+="1"; } field.push_back(s); } queue<pair<int,int> >qu; for(int i=0;i<h;i++){ qu.push(PII(0,i)); qu.push(PII(w-1,i)); } for(int i=0;i<w;i++){ qu.push(PII(i,0)); qu.push(PII(i,h-1)); } while(!qu.empty()){ PII p = qu.front(); qu.pop(); int x = p.first; int y = p.second; if(x>=0 && x<w && y>=0 && y< h){ if(field[y][x] == '0'){ field[y][x] = '-'; qu.push(PII(x+1,y)); qu.push(PII(x-1,y)); qu.push(PII(x,y+1)); qu.push(PII(x,y-1)); if(y%2 == 1){ qu.push(PII(x-1,y+1)); qu.push(PII(x-1,y-1)); } else{ qu.push(PII(x+1,y+1)); qu.push(PII(x+1,y-1)); } } } } for(int y=0;y<h;y++){ for(int x=0;x<w;x++){ if(field[y][x] == '0') field[y][x] = '1'; cout<<field[y][x]; } cout<<endl; } int count = 0; for(int y=0;y<h;y++){ for(int x=0;x<w;x++){ if(field[y][x] == '1'){ int c = 6; if(x<w-1) c -= field[y][x+1] == '1'; if(x>=1) c -= field[y][x-1] == '1'; if(y<h-1) c -= field[y+1][x] == '1'; if(y>=1) c -= field[y-1][x] == '1'; if(y%2 == 1){ if(x>=1){ if(y<h-1) c -= field[y+1][x-1] == '1'; if(y>=1) c -= field[y-1][x-1] == '1'; } } else{ if(x<w-1){ if(y<h-1) c -= field[y+1][x+1] == '1'; if(y>=1) c -= field[y-1][x+1] == '1'; } } count += c; cout<<c<<" "; } else{ cout<<0<<" "; } } cout<<endl; } cout<<count<<endl; return 0; }
EPOCHまつやま 2011 予選問題
あれ、一つ前の記事が去年の予選問題の記事だ。id:wand125:20101119:1290133106
日記全く続かないなー。
id:ichyo さんがEPOCHの記事を更新していたのに影響を受けて自分も記事を書くことに。
ソースは先週ハードディスクが壊れたので無し。
一問目：グループに分けて数字をさがせ！
問題概要
N 個の正の整数が与えられたときに、その整数を
A: 1 回しか登場しなかった整数のグループ
B: 2 回以上登場した整数のグループ
にわける
B の中の最大値を b とし、A の中で b 番目に大きな整数 (大きいものから数えて b 番目)を出力するプログラムを作成する。ただし A に属する整数が b 個未満の場合は,グループ A の中の最小値を代わりに出力する。
入力
N <= 500000
値はint型に収まる
解法
素朴に書いてみる。
- 配列に入れるO(n)
- N個の整数を素朴にソートしてO(nlog(n))
- 一つしか出てきていないものを配列Aに追加&Bの最大値を求めO(n)
- Aのb番目を出力O(1)
結果
O(nlog(n))
setを使って書いた銀杏さんのコードより速かったのでこっちが採用されました。ソースは銀杏さんの記事 id:ichyo:20111017:1318846796 を参照。
ほとんどが入力時間だと思うからそんなに高速化の余地はないと思うの。
二問目：文字列変換ポイントの計算
問題概要
N個の文字列が順に与えられる。
開始時のスコアを0とし、連続した文字間について
追加 S の先頭,末尾または途中に一文字だけ追加する.(例: epoch → eapoch)
削除 -1点
S から一文字だけ削除する.(例: epoch → epch)
変更 +2点
S の中の一文字だけを別の文字に変更する.(例: epoch → epach)
一つ前の文字と同じ それまでの得点を2倍にする
それ以外 それまでの得点に関わらず0点になる
文字列を順に見ていき、最終的な得点を求める。
最終的な得点はint型に収まることが保証されている
入力
N <= 100000
文字列の長さは255文字以下
解答
書きかけでやめました。提出は100%がいちょうさんのコード
一番工夫がしにくそうなイメージだったけどどうなんだろう。
三問目：三問目：足し算になっているのは?
問題概要
N個の数字が与えられる。数字の間に+,=の順で演算子を入れ
51042552 → 510+42=552のように等式を成立させることの出来る数字の数を数える。
ただし、分けた後も含め、数列の先頭に0が含まれていても構わない。
000130026039 → 00013 + 0026 + 039
N <= 10000
桁数は1000桁以下
解答作成
9/30の昼間時点で銀杏さんのコードが遅かったのでこれは締め切りまでに作らないと書かないとと思ってたら
銀杏さんが13:00頃に改善して数百倍速になったのでその時点で自分のコードは捨て、そっちの最適化をしてました。
最終日の数時間で仕上げるとかそれは違うプログラミングコンテストや...
高速化
数値の比較部分がループの最深なのでここのループ内を改善するのが良いだろうと考える。
char a,b,c;にそれぞれ'0'〜'9'までの数値が入っているとして、
その加算&比較の処理で繰り上がりを求めるのに除算はいらないんじゃない？(どうせ1か0だし)
剰余はいらないんじゃない?(どうせその数自身か10を引いたものなんだから)
みたいな感じで演算子やif文をなるべく減らしたりしてました。2割ぐらい速くなった気がしました。
アルゴリズム
この問題の計算量は
- (1) +,=を入れる組み合わせの数
- (2) +,=で分けた数値の加算&比較
のかけ算で求められそうです。が、1,2の両方で枝刈りが発生します。
(2)では等式が成立しているかどうかを調べるだけなので桁数ごとに比較を行い、一致しなかった時点で打ち切ることができます。
(1)では、(2)で成り立ったものが一つでも見つかった時点でそれ以降の組み合わせは考える必要がないので打ち切ることが出来ます。
平均的なケースの場合(2)の比較で等式が一致する確率は各桁ごとに1/10なので
比較回数の期待値は1+1/10+1/100… = 10/9 回
すなわちO(1)です。
けれども、この問題の条件である等式を満たすケースこそが最悪ケースとなり、O(n)回必要です。
(1)の比較について、+と=の入れ方をすべて挙げると桁数をnとしたときに(n-1)C2 = (n-1)(n-2)/2の組み合わせがあるので普通に試すとO(n^2)掛かってしまいます。
このオーダーを減らす方法は各チーム毎に差が出そうです。他のチームがどのような方法を取ったのかは知らないので、ここからは自分のチームの解き方になります。
まず、先頭の0がなかった場合を考えます。
正の整数二つの足し算なので
Cの桁数 は max(Aの桁数,Bの桁数) または (max(Aの桁数,Bの桁数)+1) となります。
よって、'='の位置(Cの桁数)を動かすと、各位置に対して'+'の入る位置は4通りに絞られることになります。
この4種類を考えれば十分です。
この条件では'='は桁数の後ろ1/3から1/2まで動かせば良いです。
次に、先頭位に0が入る状況を考えます。
桁の最初に0が来ることがあるのでそのままではこの方法で桁数から位置を絞ることが出来ないように見えます。
そこで以下のように変更します。
まず、00123→123のように与えられた数字の先頭位の0をすべて無視します。
'+'を入れた位置の左側の文字列の長さがそのままAの桁数と考えることが出来ます。
'='を右端から1つずつ動かしながら
Aの桁数 = Cの桁数
Aの桁数 = Cの桁数-1
Bの桁数 = Cの桁数
Bの桁数 = Cの桁数-1
となる4通りについて調べます。ただしBの長さをCの桁数の長さで区切った際、
区切った部分のすぐ左が'0'の時は'0'以外の数が現れるまで、Bの桁数が変わらないことに注意します。
Cの桁数は'='のすぐ右側が'0'でなければ'='より右の部分の長さを代入し、そうでない時はループの1つ前の値のままにしておくことで求められます。
桁数をnとした時の平均計算量は
'='の入れ方が
n - 2 - (最上位の0の数の期待値)
通りで
'+'の入れ方が
4 + (Bの最上位の0の数の期待値)
0の数の期待値はそれぞれΣ1/10^n = 1/9なので
平均計算回数は(n-2-1/9) * (4+1/9)回、すなわちO(n)です。
また、途中で等式を満たす組み合わせがあった場合、枝刈りが発生します。
よってこの問題の平均計算量はO(n)になります。
最悪ケースはBの先頭に0が続いたとき…?でもさすがにそれがオーダー変えるようなケースは考えなくて良いよね…。
すたっきゅん(@stac_task) に悪いケースとして1が666個,2が334個続くケースがあったけど、5秒ぐらい掛かってました。
プログラムを書く際に意識した点
- なるべくデータ構造に配列を使う。
setなどを使う時も使用するメモリ量が決まっていればロスを減らすため、配列で実装しようと考えていました。
メモリアクセスの観点からも配列の効率が良さそう。
- ボトルネックとなっている部分を改善する
プログラム全体の時間の1/100しか占めない部分を改善しても仕方がないので無視します。
- 枝刈りがなるべく効果的に働くようにする
問題3とか、もう少し改善点がありそうですね…。
感想
- 今回の場合、プログラム自体のボトルネックもだけど問題1,2,3の中で問題3の改善が大きそうだった。
- 問題3がチームによって解き方に差が出そうで良問っぽい。
- 今年は銀杏さん2問、自分1問、去年が自分2問、銀杏さん1問なのでバランスが良い
- 問題3の銀杏さんのソースにBの先頭の0の処理が書いてなかったような気がするのだけど、だいじょうぶなの。
- 運が良かった…?
- 本選出場のみなさま、お会いできるのを楽しみにしてます。
- 今年もスライドがんばる
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の解いた問題数で抜かれたし...。
とりあえず蟻本を持ってけばなんとかなるかもとか...。
楽しみです。わくわく。
