#998657 (C++23) No.3275 Minesweeper on Graph

提出ソース
結果

問題	No.3275 Minesweeper on Graph
ユーザー	Arleen
提出日時	2024-07-31 14:06:11
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	33 ms / 2,000 ms
コード長	15,277 bytes
コンパイル時間	4,679 ms
コンパイル使用メモリ	308,472 KB
実行使用メモリ	6,948 KB
最終ジャッジ日時	2024-07-31 14:06:20
合計ジャッジ時間	8,290 ms
ジャッジサーバーID （参考情報）	judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 40
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define um unordered_map
#define us unordered_set
using namespace std;
const ll md1 = 998244353;
const ll md2 = 1e9 + 7;
const ll infll = LLONG_MAX;

typedef tuple<ll, vector<string>> query;
typedef vector<vector<ll>> twodint;

//==========
//入力ツール
//n個の入力を1つの整数リストとして受け取る
vector<ll> intlist(ll n){
	vector<ll> v;
	for(ll i = 0; i < n; i++){
		ll a;
		scanf("%lld", &a);
		v.push_back(a);
	}
	return v;
}

//n行の入力を文字列のリストとして受け取る
vector<string> strtable(ll n){
	vector<string> v;
	for(ll i = 0; i < n; i++){
		string s;
		cin >> s;
		v.push_back(s);
	}
	return v;
}

//1行m個の整数の入力をn行受け取ってリストにする
twodint intlisttable(ll n, ll m){
	twodint v;
	for(ll i = 0; i < n; i++){
		v.push_back(intlist(m));
	}
	return v;
}

//n個のクエリを先頭だけ整数、他を文字列のリストとして受け取る
vector<query> getquery(ll n){ //cin入力後に使う場合は、直前にgetline(cin)で改行を取り除く
	vector<query> v;
	v.clear();
	string s;
	getline(cin, s);
	for(ll i = 0; i < n; i++){
		stringstream ss(s);
		ll qr;
		vector<string> vs;
		ss >> qr;
		string inpt;
		while(ss >> inpt){
			vs.push_back(inpt);
		}
		v.push_back({qr, vs});
		getline(cin, s);
	}
	
	return v;
}

//==========
//出力ツール
//リストの中身を空白区切りで出力
template <typename T>
void printwithspace(vector<T> v){
	for(auto it = v.begin(); it != v.end(); it++){
		if(it != v.begin()){
			cout << " ";
		}
		cout << *it;
	}
	cout << endl;
	return;
}
//2次元リストの中身を1行ごと、空白区切りで出力
template <typename T>
void twodprintwithspace(vector<vector<T>> v){
	for(auto it = v.begin(); it != v.end(); it++){
		for(auto it2 = (*it).begin(); it2 != (*it).end(); it2++){
			if(it2 != (*it).begin()){
				cout << " ";
			}
			cout << *it2;
		}
		cout << endl;
	}
	return;
}

//==========
//unordered_map用の各種操作
//keyのリストを生成
template <typename T1, typename T2>
vector<T1> keys(um<T1, T2> d){
	vector<T1> v;
	for(auto it = d.begin(); it != d.end(); it++){
		v.push_back((*it).first);
	}
	sort(v.begin(), v.end());
	return v;
}

//valueのリストを作成
template <typename T1, typename T2>
vector<T2> values(um<T1, T2> d){
	vector<T2> v;
	for(auto it = d.begin(); it != d.end(); it++){
		v.push_back((*it).second);
	}
	return v;
}

//==========
//数え上げ
//1次元数え上げ
template <typename T1, typename T2>
ll cntx(T1 itr, T2 x){
	return count(itr.begin(), itr.end(), x);
}

//2次元数え上げ
template <typename T1, typename T2>
ll twodimcntx(T1 itr, T2 x){
	ll sm = 0;
	for(auto it = itr.begin(); it != itr.end(); it++){
		sm += cntx(itr, x);
	}
	return sm;
}

//1次元全要素数え上げ
template <typename T1, typename T2>
unordered_map<T2, ll> cntall(T1 itr){
	unordered_map<T2, ll> d;
	for(auto it = itr.begin(); it != itr.end(); it++){
		d.try_emplace(*it, 0);
		d[*it]++;
	}
	return d;
}

//2次元全要素数え上げ
template <typename T1, typename T2>
unordered_map<T2, ll> twodimcntall(T1 itr){
	unordered_map<T2, ll> d;
	for(auto it = itr.begin(); it != itr.end(); it++){
		for(auto it2 = (*it).begin(); it2 != (*it).end(); it2++){
			d.try_emplace(*it2, 0);
			d[*it2]++;
		}
	}
	return d;
}

//==========
//計算ツール
//最大公約数
ll gcd(ll x, ll y){
	if(x < y){
		return gcd(y, x);
	}
	if(x % y == 0){
		return y;
	}
	return gcd(y, x%y);
}

//最小公倍数
ll lcm(ll x, ll y){
	ll g = gcd(x, y);
	return (x * y) / g;
}

//フィボナッチ数列生成(0-indexで、a_0 = 0, a_1 = 1, 第n項まで生成)
vector<ll> genfib(ll n, ll m){ //m = 1ならmd1、m = 2ならmd2、それ以外ならmの値でmod
	ll md = m;
	if(m == 1){
		md = md1;
	}
	else if(m == 2){
		md = md2;
	}
	vector<ll> v = {0, 1};
	for(ll i = 1; i < n; i++){
		auto it1 = v.end() - 1;
		auto it2 = v.end() - 2;
		v.push_back(*it1 + *it2);
	}
	return v;
}

//各桁の総和
ll digitsum(ll x){
	string s = to_string(x);
	ll sm = 0;
	for(auto it = s.begin(); it != s.end(); it++){
		sm += *it - '0';
	}
	return sm;
}

//popcount
ll popcntll(ll x){
	return static_cast<ll>(__builtin_popcountll(x));
}

//xの累乗リスト(0乗からn乗まで)
vector<ll> powtable(ll x, ll n, ll m){ //m = 1ならmd1, m = 2ならmd2, それ以外ならmでmod
	ll md = m;
	if(m == 1){
		md = md1;
	}
	else if(m == 2){
		md = md2;
	}
	vector<ll> v = {1};
	for(ll i = 0; i < n; i++){
		ll lst = *v.rbegin();
		v.push_back((x*lst) % md);
	}
	return v;
}

//==========
//素数関連
set<ll> primeset;
vector<ll> primelist;

//素数テーブル生成
void genprimeset(ll n){
	ll start = 2;
	if(primelist.size() != 0){
		start = *(primelist.rbegin()) + 1;
	}
	set<ll> ps = primeset;
	for(ll i = start; i <= n; i++){
		ps.insert(i);
	}
	auto it = ps.begin();
	ll m = *it;
	while(m*m <= (*ps.rbegin())){
		ll now = m * 2;
		while(now <= (*ps.rbegin())){
			if(ps.find(now) != ps.end()){
				ps.erase(now);
			}
			now += m;
		}
		it++;
		m = *it;
	}
	primeset = ps;
	return;
}

//素数テーブルの初期化
void primeinit(ll x){
	genprimeset(x);
	primelist.clear();
	for(auto it = primeset.begin(); it != primeset.end(); it++){
		primelist.push_back(*it);
	}
	return;
}

//素数判定
bool isitprime(ll x){
	if(x < 2){
		return false;
	}
	ll sr = static_cast<ll>(sqrt(x));
	if(primelist.size() == 0){
		primeinit(sr+10);
	}
	else{
		ll p = *(primelist.rbegin());
		if(p*p < x){
			primeinit(sr+10);
		}
	}
	if(primeset.contains(x)){
		return true;
	}
	for(auto it = primelist.begin(); it != primelist.end(); it++){
		if(x % (*it) == 0){
			return false;
		}
	}
	return true;
}

//素因数分解
tuple<vector<ll>, um<ll, ll>> factorize(ll x){
	ll sr = static_cast<ll>(sqrt(x));
	if(primelist.size() == 0){
		primeinit(sr+10);
	}
	else{
		ll p = *(primelist.rbegin());
		if(p*p < x){
			primeinit(sr+10);
		}
	}
	um<ll, ll> dct;
	ll now = x;
	for(auto it = primelist.begin(); it != primelist.end(); it++){
		ll p = *it;
		if(x < p*p){
			break;
		}
		while(now % p == 0){
			if(!dct.contains(p)){
				dct.insert({p, 0});
			}
			dct[p] += 1;
			now /= p;
		}
	}
	if(now != 1){
		dct.insert({now, 1});
	}
	vector<ll> dctkey = keys(dct);
	return {dctkey, dct};
}

//約数数え上げ
ll countdivisor(ll x){
	vector<ll> k;
	um<ll, ll> f;
	tuple<vector<ll>, um<ll, ll>> t = factorize(x);
	k = get<0>(t);
	f = get<1>(t);
	ll cnt = 1;
	for(auto it = k.begin(); it != k.end(); it++){
		cnt *= f[*it] + 1;
	}
	return cnt;
}

//約数列挙
vector<ll> divisor(ll x){
	us<ll> s;
	for(ll i = 1; i <= x; i++){
		if(x < i*i){
			break;
		}
		if(x % i == 0){
			s.insert(i);
			s.insert(x / i);
		}
	}
	vector<ll> v;
	for(auto it = s.begin(); it != s.end(); it++){
		v.push_back(*it);
	}
	sort(v.begin(), v.end());
	return v;
}

//==========
//英字変換
//大文字->小文字変換
char uppertolower(char c){
	return static_cast<char>(toupper(c));
}

//小文字→大文字変換
char lowertoupper(char c){
	return static_cast<char>(tolower(c));
}

//大文字小文字相互変換
char upperlower(char c){
	char newc = uppertolower(c);
	if(c == newc){
		newc = lowertoupper(c);
	}
	return newc;
}

//文字列の大文字->小文字変換
string uppertolowerstr(string s){
	string a = "";
	for(ll i = 0; i < s.size(); i++){
		char& c = s[i];
		a.push_back(uppertolower(c));
	}
	return a;
}

//文字列の小文字->大文字変換
string lowertoupperstr(string s){
	string a = "";
	for(ll i = 0; i < s.size(); i++){
		char& c = s[i];
		a.push_back(lowertoupper(c));
	}
	return a;
}

//文字列の大小相互変換
string upperlowerstr(string s){
	string a = "";
	for(ll i = 0; i < s.size(); i++){
		char& c = s[i];
		a.push_back(upperlower(c));
	}
	return a;
}

//二分探索
//渡すvectorはソート済みにすること
//x以下の要素の個数
template <typename T>
ll xorless(vector<T> v, T x){
	int ans = distance(v.begin(), upper_bound(v.begin(), v.end(), x));
	return static_cast<ll>(ans);
}

//xより小さい要素の個数
template <typename T>
ll lessthanx(vector<T> v, T x){
	int ans = distance(v.begin(), lower_bound(v.begin(), v.end(), x));
	return static_cast<ll>(ans);
}

//x以上の要素の個数
template <typename T>
ll xormore(vector<T> v, T x){
	int ans = v.size() - distance(v.begin(), lower_bound(v.begin(), v.end(), x));
	return static_cast<ll>(ans);
}

//xより大きい要素の個数
template <typename T>
ll morethanx(vector<T> v, T x){
	int ans = v.size() - distance(v.begin(), upper_bound(v.begin(), v.end(), x));
	return static_cast<ll>(ans);
}

//==========
//繰り返し2乗法
um<ll, ll> powdct;
//powdctの初期化
void initpow(){
	powdct.clear();
	powdct.insert({0, 1});
	return;
}

ll repeatpow(ll x, ll y, ll m){//m = 1ならmd1, m = 2ならmd2, それ以外ならmでmod
	ll md = m;
	if(m == 1){
		md = md1;
	}
	else if(m == 2){
		md = md2;
	}
	
	if(powdct.contains(y)){
		return powdct[y];
	}
	ll a = 1;
	if(y % 2 == 1){
		a = x;
	}
	ll r = repeatpow(x, y/2, m);
	a = (((r*r) % md)*a) % md;
	powdct.insert({y, a});
	return a;
}

ll powit(ll x, ll y, ll m){
	initpow();
	if(x == 0){
		return 0;
	}
	return repeatpow(x, y, m);
}

//==========
//グラフツール(WIP)
//グラフ初期化
template <typename T>
vector<vector<ll>> defgraph(vector<T> vlist){
	vector<vector<ll>> graph;
	for(ll i = 0; i < vlist.size(); i++){
		vector<ll> vct;
		graph.push_back(vct);
	}
	return graph;
}

//elist生成(vlistはソート済みにすること)
template <typename T>
vector<tuple<ll, ll>> genelist(vector<T> vlist, vector<tuple<T, T>> rawe){
	vector<tuple<ll, ll>> elist;
	for(ll i = 0; i < rawe.size(); i++){
		T& u = get<0>(rawe[i]);
		T& v = get<1>(rawe[i]);
		auto uit = lower_bound(vlist.begin(), vlist.end(), u);
		auto vit = lower_bound(vlist.begin(), vlist.end(), v);
		ll uidx = static_cast<ll>(distance(vlist.begin(), uit));
		ll vidx = static_cast<ll>(distance(vlist.begin(), vit));
		elist.push_back({uidx, vidx});
	}
	return elist;
}

//無向グラフ生成
template <typename T>
vector<vector<ll>> undirgraph(vector<T> vlist, vector<tuple<T, T>> rawe){
	vector<vector<ll>> graph = defgraph<T>(vlist);
	vector<tuple<ll, ll>> elist = genelist<T>(vlist, rawe);
	for(ll i = 0; i < elist.size(); i++){
		ll& u = get<0>(elist[i]);
		ll& v = get<1>(elist[i]);
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	return graph;
}

//有向グラフ生成
template <typename T>
vector<vector<ll>> dirgraph(vector<T> vlist, vector<tuple<T, T>> rawe){
	vector<vector<ll>> graph = defgraph<T>(vlist);
	vector<tuple<ll, ll>> elist = genelist<T>(vlist, rawe);
	for(ll i = 0; i < elist.size(); i++){
		ll& u = get<0>(elist[i]);
		ll& v = get<1>(elist[i]);
		graph[u].push_back(v);
	}
	return graph;
}

//重み無し最短経路
template <typename T>
ll shortest(vector<T> vlist,\
			vector<vector<ll>> graph,\
			T st,\
			T gl){
	bool rule1 = find(vlist.begin(), vlist.end(), st) == vlist.end();
	bool rule2 = find(vlist.begin(), vlist.end(), gl) == vlist.end();
	if(rule1 || rule2){
		return -1;
	}
	auto stitr = lower_bound(vlist.begin(), vlist.end(), st);
	auto glitr = lower_bound(vlist.begin(), vlist.end(), gl);
	ll stidx = static_cast<ll>(distance(vlist.begin(), stitr));
	ll glidx = static_cast<ll>(distance(vlist.begin(), glitr));
	us<ll> yet;
	for(ll i = 0; i < vlist.size(); i++){
		yet.insert(i);
	}
	yet.erase(stidx);
	deque<tuple<ll, ll>> q;
	q.push_back({stidx, 0});
	while(q.size() != 0){
		tuple<ll, ll>& now = q.front();
		ll& v = get<0>(now);
		ll& s = get<1>(now);
		q.pop_front();
		if(v == glidx){
			return s;
		}
		for(ll i = 0; i < graph[v].size(); i++){
			ll nxtv = graph[v][i];
			if(yet.contains(nxtv)){
				yet.erase(nxtv);
				q.push_back({nxtv, s+1});
			}
		}
	}
	return -1;
}

//wdictの生成
template <typename T1, typename T2>
um<ll, T2> genwdict(vector<T1> vlist,\
					vector<tuple<T1, T1, T2>> raww){
	um<ll, T2> wdict;
	for(ll i = 0; i < raww.size(); i++){
		T1& u = get<0>(raww[i]);
		T1& v = get<1>(raww[i]);
		T2& w = get<2>(raww[i]);
		auto uit = lower_bound(vlist.begin(), vlist.end(), u);
		auto vit = lower_bound(vlist.begin(), vlist.end(), v);
		ll uidx = static_cast<ll>(distance(vlist.begin(), uit));
		ll vidx = static_cast<ll>(distance(vlist.begin(), vit));
		ll widx = uidx * vlist.size() + vidx;
		wdict.insert({widx, w});
	}
	return wdict;
}

//重み付きグラフ初期化
template <typename T1, typename T2>
vector<um<ll, T2>> defgraphw(vector<T1> vlist){
	vector<um<ll, T2>> graph;
	for(ll i = 0; i < vlist.size(); i++){
		um<ll, T2> dct;
		graph.push_back(dct);
	}
	return graph;
}

//重み付き無向グラフ生成
template <typename T1, typename T2>
vector<um<ll, T2>> undirgraphw(vector<T1> vlist,\
								vector<tuple<T1, T1>> rawe,\
								vector<tuple<T1, T1, T2>> raww){
	vector<um<ll, T2>> graph = defgraphw<T1, T2>(vlist);
	vector<tuple<ll, ll>> elist = genelist<T1>(vlist, rawe);
	um<ll, T2> wdict = genwdict<T1, T2>(vlist, raww);
	for(ll i = 0; i < elist.size(); i++){
		ll& u = get<0>(elist[i]);
		ll& v = get<1>(elist[i]);
		ll wref = u * vlist.size() + v;
		T2 w = wdict[wref];
		graph[u].insert({v, w});
		graph[v].insert({u, w});
	}
	return graph;
}

/* //ダイクストラ(WIP)
template <typename T1, typename T2>
um<ll, T2> dijkstra(vector<T1> vlist,\
				vector<tuple<ll, ll>> elist,\
				vector<um<ll, T2>> graph,\
				T1 st){
	um<ll, T2> cur;
	for(ll i = 0; i < vlist.size(); i++){
		cur.insert({i, static_cast<T2>(infll)});
	}
	
} */

//==========
//問題要約
// N 頂点 M 辺の単純無向グラフが与えられる
// 頂点には 1 から N までの番号が、辺には 1 から M までの番号が振られている
// 辺 i(where 1<=i<=M)は頂点 U_i と頂点 V_i を結んでいる
// 各頂点には地雷が 0 個または 1 個埋まっている
// 頂点 k(where 1<=k<=N)に隣接する頂点に埋まっている地雷の個数の総和は A_k 個である
// これに矛盾しない地雷の埋め方が存在するかを判定し、存在するなら埋め方を 1 つ例示せよ
//
// 1 <= N <= 16
// 1 <= M <= N(N-1) // 2
// 0 <= A_i <= N-1
// 1 <= U_i, V_i <= N
// 入力はすべて整数
// グラフは単純無向グラフ
//
//==========
//コードはここから書く

int main(){
	ll N, M;
	cin >> N >> M;
	vector<ll> vlist;
	for(ll i = 1; i <= N; i++){
		vlist.push_back(i);
	}
	vector<ll> A = intlist(N);
	vector<tuple<ll, ll>> rawe;
	for(ll i = 0; i < M; i++){
		ll U, V;
		cin >> U >> V;
		rawe.push_back({U, V});
	}
	vector<vector<ll>> graph = undirgraph<ll>(vlist, rawe);
	ll mx = powit(2, N, 1);
	bool flag = true;
	for(ll i = 0; i < mx; i++){
		vector<ll> mineexists;
		ll now = i;
		for(ll j = 0; j < N; j++){
			mineexists.push_back(now % 2);
			now /= 2;
		}
		vector<ll> minecount;
		for(ll j = 0; j < N; j++){
			minecount.push_back(0);
		}
		for(ll j = 0; j < N; j++){
			for(ll k = 0; k < graph[j].size(); k++){
				minecount[j] += mineexists[graph[j][k]];
			}
		}
		bool subflag = true;
		for(ll j = 0; j < N; j++){
			if(minecount[j] != A[j]){
				subflag = false;
			}
		}
		if(subflag){
			flag = false;
			cout << "Yes" << endl;
			printwithspace<ll>(mineexists);
			break;
		}
	}
	if(flag){
		cout << "No" << endl;
	}
	return 0;
}
yukicoder

結果

ソースコード
