2011-2012 Waterloo Local Contest, 24 September, 2011 E : Harmonious Matrices
問題概要
ある二次元ボードが調和的であるとは自分を含む5近傍の和がmod 2で0となるときにいう。H*W(H,W<40)の調和的な行列を出力する問題。ただし自明解としてすべて0というのがあるので、非自明解が存在するならば必ず非自明解を出力する。
解法
mod 2での連立1次方程式を解けばよい。このままだとMAX_W^6でTLEするがビット演算を使って高速化すれば通る。埋め込みはファイルが大きくなりすぎるので適切な圧縮が必要。
acceptされたコード
#include <cstdio> #include <cstring> using namespace std; typedef unsigned long long bits; const int MAX_W = 40; const int dy[] = {1, -1, 0, 0, 0}, dx[] = {0, 0, -1, 1, 0}; int H, W; bool fixed[MAX_W*MAX_W]; int one[MAX_W*MAX_W]; bits mat[MAX_W*MAX_W][(MAX_W*MAX_W + 1)/64 + 1]; bits tmp[(MAX_W*MAX_W + 1)/64 + 1]; void init(){ scanf("%d%d", &H, &W); } void solve(){ //build matrix memset(mat, 0, sizeof(mat)); for(int i=0; i<H; i++){ for(int j=0; j<W; j++){ for(int k=0; k<5; k++){ int ny = i + dy[k], nx = j + dx[k]; if(0<=ny && ny<H && 0<=nx && nx<W){ int a = ny*W+nx; mat[i*W+j][a>>6] |= (1LL<<(a&63)); } } } } //calc memset(fixed, false, sizeof(fixed)); memset(one, 0, sizeof(one)); const int S = H * W; const int L = (S + 1) / 64 + 1; for(int i=0; i<S; i++){ int pivot = -1; for(int j=0; j<S; j++)if(!fixed[j] && ((mat[j][i>>6]>>(i&63))&1) ){ pivot = j; } if(pivot == -1){ for(int j=0; j<S; j++){ if((mat[j][i>>6]>>(i&63))&1){ mat[j][i>>6] &= ~(1LL<<(i&63)); mat[j][S>>6] ^= 1LL<<(S&63); } } one[i] = 1; continue; } fixed[i] = true; memcpy(tmp, mat[pivot], sizeof(tmp)); memcpy(mat[pivot], mat[i], sizeof(tmp)); memcpy(mat[i], tmp, sizeof(tmp)); for(int j=0; j<S; j++)if(i!=j && ((mat[j][i>>6]>>(i&63))&1)){ for(int k=i>>6; k<L; k++){ mat[j][k] ^= mat[i][k]; } } } for(int i=0; i<H; i++){ for(int j=0; j<W; j++){ printf("%d%c", (int)(one[i*W+j] | ((mat[i*W+j][(S>>6)]>>(S&63))&1)), j==W-1?'\n':' '); } } } int main(){ int T; scanf("%d", &T); for(int i=0; i<T; i++){ init(); solve(); } return 0; }