結果

問題 No.425 ジャンケンの必勝法
ユーザー 🐬hec🐬hec
提出日時 2016-09-22 23:36:46
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 2,319 bytes
コンパイル時間 1,337 ms
コンパイル使用メモリ 170,644 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-17 19:41:26
合計ジャッジ時間 2,022 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using ll=long long;
using R=long double;
const R EPS=1e-9; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max<R>(x,0.0));}

const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};

// Problem Specific Parameter:

using vec=valarray<R>;
using mat=valarray<vec>;

const R eps=1e-10;

vec gauss_jordan(mat &a){
	const int n=a.size(),m=a[0].size();
	rep(i,n){
		int pivot=i;
		rep(j,i,n) if(abs(a[j][i])>abs(a[pivot][i])) pivot=j;
		swap(a[i],a[pivot]);

		if(abs(a[i][i])<eps) return vec();

		rep(j,i+1,m) a[i][j]/=a[i][i];
		rep(j,n) if(i!=j) rep(k,i+1,m) a[j][k]-=a[j][i]*a[i][k];
	}	

	vec x(0.0,n);
	rep(i,n) x[i]=a[i][n];
	return x;
}

int main(void){
	int p,q;
	cin >> p >> q;

	mat a(vec(0.0,102),101);

	rep(i,101) a[i][i]=1.0;

	rep(i,101){
		int up=min(i+q,100),down=max(i-q,0);

		if(up==i){
			const R coef=1.0/(1.0-1.0*(100-i)/100.0/3.0);
			a[i][down]-=coef*i/100.0/2.0;
			a[i][101]+=coef*(i/100.0/2.0+1.0*(100-i)/100.0/3.0);
		}else if(down==i){
			const R coef=1.0/(1.0-1.0*i/100.0/2.0);
			a[i][up]-=coef*(100.0-i)/100.0/3.0;
			a[i][101]+=coef*(i/100.0/2.0+1.0*(100-i)/100.0/3.0);
		}else{
			const R coef=1.0;
			a[i][down]-=coef*i/100.0/2.0;
			a[i][up]-=coef*(100.0-i)/100.0/3.0;
			a[i][101]+=coef*(i/100.0/2.0+1.0*(100.0-i)/100.0/3.0);
		}
	}

	vec x=gauss_jordan(a);

	cout.precision(20);
	cout << fixed << 1.0/3.0*(1.0+x[p]) << endl;
	return 0;
}
0