風船を割るゲーム#
説明#
週末、何社長は磁器口に遊びに行きました。街の側には小売業者が風船を割るゲームを開催していて、何社長はとても興味を持ちました。
店主は布を立て、その布には N*N の格子が描かれており、いくつかの格子には風船が吊るされていて、いくつかにはありません。
ゲームのルールは以下の通りです：
第 1 ステップ。観察。もし各行に少なくとも 1 つの格子に風船がなく、各列にも少なくとも 1 つの格子に風船がなければ、ゲームは終了します。そうでなければ第 2 ステップに進みます。
第 2 ステップ。サイコロを振る。店主は特製のサイコロを取り出します。このサイコロは N 面あり、1 から N までの N 個の数字が順に書かれています。プレイヤーは順番に 2 回サイコロを振り、最初に出た数字を x、2 回目に出た数字を y とします（注：出た数字はランダムです）。
第 3 ステップ。風船を割る。もし座標 (x,y) の格子に風船があれば、プレイヤーはそれを割らなければなりません。弾丸は 1 発 1 元です。
もしその格子に風船がなければ、その格子は無視され、プレイヤーは銃を撃つ必要はありませんが、プレイヤーは店主に 1 元支払う必要があります。
第 4 ステップ。続行。第 1 ステップを実行します。
何社長は神射手で、彼は百発百中の技術を持っています。彼はあなたに、現在与えられたこのゲームのために、終了するまでにどれくらいの費用がかかるかを計算してもらいたいと思っています。
入力#
最初の行には 2 つの整数 N と M があり、N は格子のサイズ、M はゲーム開始時に M 個の格子に風船がないことを示します。次の M 行には、各行に 2 つの整数 x,y があり、座標 x,y の格子に風船がないことを示します。
出力#
1 行に、ゲームを完了するための予想費用を実数で出力し、小数点以下 2 桁を保持します。
入力例 1#
5 2
2 3
4 1
出力例 1#
11.77
さらに多くの例については、wyx 大佬のブログをクリックしてください。
考え方#
この小売業者は本当にひどい！
f[i][j]を i 行 j 列を消去するための期待費用とします。
毎回選択する座標には以下の 4 つの状況があります。
- 割った行列の数に影響を与えない
- 割った行を 1 つ増やす
- 割った列を 1 つ増やす
- 同時に割った行列をそれぞれ 1 つ増やす
それぞれの期待値は以下の通りです。
- $f(i,j)\cdot \frac{(n-i)\cdot (n-j)}{n^2}$
- $f(i,j-1)\cdot \frac{(n-i)\cdot j}{n^2}$
- $f(i-1,j)\cdot \frac{i\cdot (n-j)}{n^2}$
- $f(i-1,j-1)\cdot \frac{ij}{n^2}$
したがって、
境界条件：
f[0][0]=0;
for(int i=1;i<=n;++i){
f[0][i]=f[0][i-1]+1.0*n/i;
f[i][0]=f[i-1][0]+1.0*n/i;
}
死にそうだ。
重要なのは、入力されるのは風船のない格子であることです。
私は hqx 大佬と一緒に長い間騙されました。
コード#
#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN=2000+5;
int hang[MAXN],lie[MAXN];
double f[MAXN][MAXN];
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
int x,y;
scanf("%d%d",&x,&y);
hang[x]=1;
lie[y]=1;
}
int h=n,l=n;
for(int i=1;i<=n;++i){
if(hang[i])--h;
if(lie[i])--l;
}
f[0][0]=0;
for(int i=1;i<=n;++i){
f[0][i]=f[0][i-1]+1.0*n/i;
f[i][0]=f[i-1][0]+1.0*n/i;
}
for(int i=1;i<=h;++i){
for(int j=1;j<=l;++j){
// f[i][j]=f[i-1][j]*1.0*i*(n-j)/n/n+f[i][j-1]*1.0*(n-i)*j/n/n+f[i-1][j-1]*1.0*i*j/n/n+f[i][j]*1.0*(n-i)*(n-j)/n/n+1;
f[i][j]=1.0*(f[i-1][j]*i*(n-j)+f[i][j-1]*(n-i)*j+f[i-1][j-1]*i*j+n*n)/(n*n-(n-i)*(n-j));
}
}
printf("%.2lf\n",f[h][l]);
return 0;
}