結果

問題 No.3615 Ge Gusser
コンテスト
ユーザー keisuke6
提出日時 2026-08-06 14:29:53
言語 C++17
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 577 ms / 3,000 ms
+ 231µs
コード長 1,146 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,230 ms
コンパイル使用メモリ 214,340 KB
実行使用メモリ 36,480 KB
最終ジャッジ日時 2026-08-06 14:29:58
合計ジャッジ時間 5,315 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
サンプル 0 % AC * 3
小課題1 40 % AC * 8
小課題2 40 % AC * 15
小課題3 20 % AC * 27
合計 2.5 * 100% = 250 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct SEG{
private:
	int n;
	vector<int> node;
public:
	SEG(int N){
		n = 1;
		while(n < N) n *= 2;
		node.resize(2*n+1);
	}
	void add(int i, int x){
		for(i++;i<=n;i+=i&-i) node[i] += x;
	}
	int f_(int i){
		int ans = 0;
		for(;i>0;i-=i&-i) ans += node[i];
		return ans;
	}
	int f(int l, int r){
		return f_(r)-f_(l);
	}
};
signed main(){
	ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	srand((unsigned)time(NULL));
	int N,M;
	cin>>N>>M;
	vector<double> P(1<<N);
	P[0] = 1;
	vector<int> A(N);
	for(int i=0;i<N;i++)for(int j=0;j<M;j++){
		char c;
		cin>>c;
		if(c == 'o') A[i] += (1ll<<j);
	}
	double ans = 0;
	for(int i=0;i<(1<<N);i++){
		bool p = false;
		int cs = __builtin_popcountll((unsigned long long)i);
		{
			int now = (1ll<<M)-1;
			for(int j=0;j<N;j++)if(i&(1<<j)) now &= A[j];
			int c = __builtin_popcountll((unsigned long long)now);
			if(c == 1) p = true;
		}
		if(p){
			ans += cs*P[i];
			continue;
		}
		int n = N-cs;
		for(int j=0;j<N;j++)if(!(i&(1<<j))) P[i|(1<<j)] += P[i]/n;
	}
	cout<<fixed<<setprecision(15)<<ans<<endl;
}
0