昨日思いついたゲーム
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の解いた問題数で抜かれたし...。
とりあえず蟻本を持ってけばなんとかなるかもとか...。
楽しみです。わくわく。
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
