結果

問題 No.74 貯金箱の退屈
コンテスト
ユーザー koyumeishi
提出日時 2014-11-24 23:31:54
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 3,102 bytes
コンパイル時間 1,191 ms
コンパイル使用メモリ 87,144 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2025-01-02 21:17:19
合計ジャッジ時間 2,051 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

void print(const vector<vector<int> > &v){
	int n = v.size();
	int m = v[0].size();
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			cerr << v[i][j] << (j==(n-1)? " | " : " ");
		}
		cerr << endl ;
	}
	cerr << endl;
	
}

//A[n*n]*b[n*1] = x[n*1]
//A^(-1)[n*n]*x[n*1] = b[n*1]
bool gaussian_elimination(vector<vector<int> > &A, vector<vector<int> > &x){
	bool valid = true;
	int rank=0;
	int n = A.size();
	vector< vector<int> > R = A;
	for(int i=0; i<n; i++){
		R[i].insert(R[i].end(), x[i].begin(), x[i].end());
	}
	int m = R[0].size();

	//print(R);

	//foward
	//row
	for(int i=0; i<n; i++){

		//print(R);
		
		//pivot
		int pivot_row = i;
		int pivot_val = abs(R[i][i]);
		//choose pivot row
		for(int j=i+1; j<n; j++){
			if(pivot_val < abs(R[j][i])){
				pivot_row = j;
				pivot_val = abs(R[j][i]);
			}
		}
		if(pivot_row != i){
			swap(R[i], R[pivot_row]);
		}

		if(pivot_val == 0){
			
			continue;
		}

		rank++;

		{
			int divisor = 1/R[i][i];
			//A[i][j] == 0, such that (0 <= j < i)
			for(int j=i; j<m; j++){
				R[i][j] *= divisor;
				R[i][j] += 2;
				R[i][j] %= 2;
			}
		}
		
		for(int j=i+1; j<n; j++){
			int divisor = R[j][i];	// R[j][i]/R[i][i], but R[i][i] is 1.0
			for(int k=i; k<m; k++){
				R[j][k] -= R[i][k] * divisor;
				R[j][k] += 2;
				R[j][k] %= 2;
			}
		}
	}

	//print(R);

	//backward
	//row
	for(int i=n-1; i>=0; i--){
		for(int j=i-1; j>=0; j--){
			int c = R[j][i];
			for(int k=i; k<m; k++){
				R[j][k] -= R[i][k] * c;
				R[j][k] += 2;
				R[j][k] %= 2;
			}
		}
	}

	for(int i=0; i<n; i++){
		if(R[i][n] == 0) continue;
		bool row_valid = false;
		for(int j=i; j<m; j++){
			if(abs(R[i][j]) > 0 && j<n){
				row_valid = true;
				break;
			}
		}
		if(row_valid == false && R[i][n] != 0){
			valid = false;
			break;
		}
	}

	//print(R);
	//cerr << "rank is " << rank << endl;
	//cerr << (valid?"valid":"invalid, no solutions") << endl;

	return valid;
}



int main(){
	int N;
	cin >> N;
	vector<int> D(N);
	for(int i=0; i<N; i++){
		cin >> D[i];
		D[i] %= N;
	}

	//W[i][0] := i番目のコインをひっくり返さねばならないとき1、それ以外は0
	vector< vector<int> > W(N, vector<int>(1));
	for(int i=0; i<N; i++){
		cin >> W[i][0];
		//今の状態が表(入力:1)なら裏返す必要はないので0、裏(入力:0)なら裏返す必要があるので1
		W[i][0] = !W[i][0];
	}

	//C[i][j] := j枚目のコインでi番目のコインがひっくり返る場合1、それ以外は0
	vector< vector<int> > C(N, vector<int>(N, 0));
	for(int i=0; i<N; i++){
		C[ (i+D[i])%N ][i] |= 1;
		C[ (i-D[i]+N)%N ][i] |= 1;
	}

	//ガウスの消去法でCx = Wを解いて解が存在するなら"Yes"、そうでなければ"No"
	cout << (gaussian_elimination(C,W)?"Yes":"No") << endl;
	return 0;
}
0