ドミニオン日本選手権で最下位卓に居た話
ドミニオン日本選手権、予選午後の部に参加しました。
試合結果と主な反省点について。
目標
- 自分のプレーをする
- サプライをみた段階である程度方針を決める。
- いくつか浮かんだら相手の動きを見て決めたりも。
- やったことのないプレイはしない
1回戦 4番手 4位
- 建て直しプレイをしたことも封土プレイをしたこともなかった。
- 特殊勝利点を見ずに建て直しを撃ちながら地下墓所と金貨を買って8金を目指すプレイを狙う。
- 負けました。建て直しや特殊勝利点をやってなかったという分かりやすい敗因
- ブドウ園とかも同じく使ったことのない特殊勝利点だったり。
- 特殊勝利点を知らないドミニオンは本来の魅力が半分って言ってもいいと思うのでぜひ出来るようになりたいね。
2回戦 1番手 4位
- 地下貯蔵庫、村、浮浪児、祝宴、泥棒、行進、書庫、伯爵、祝祭、秘術師。
- 書庫、伯爵、祝祭が目立つ。5金出して伯爵でさっさと圧縮したい。
- なぜか初手で浮浪者銀を購入、銀銀か、5金が出したいので祝宴でも良かった。
- そのまま3ターン目、4ターン目に5金出なかった。
- 四位確でプレイ続けるのつらい。
ここで最下位卓へ
3回戦 2番手 3位/3人
- 狂信者が一人でそのまま一人が勝利。
- 死の荷車、餌には困らなかったけどだめだったか。
- アタックを何人が使うかの感覚が4人戦と変わるから、そこに慣れてなかったのがつらかった点かも。
- ドベとっても1点貰えるのうれしい
4回戦 4番手 1位/4人
- 騎士に1人、青空市場に自分ともう一人、青空市場が1位2位
- 自分は青空改築で金貨を増やすプレイ
- 騎士の人は民兵効果の騎士ともう1枚騎士を入れてた。
- 手札に堀と2枚青空市場がある時に、民兵付きの騎士を撃たれて堀を公開せずに騎士で廃棄された方が得だったのかもしれない。
- 属州を買わずに金貨改築で公領を買っていれば3点増えたのでそれはプレイミス
- 二位と10点差つけて一位
結果
7点
70位/95人
- おつかれさまでした
- くやしいのでドミニオン始めるかも
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の処理が書いてなかったような気がするのだけど、だいじょうぶなの。
- 運が良かった…?
- 本選出場のみなさま、お会いできるのを楽しみにしてます。
- 今年もスライドがんばる
