- Quiz
- AC
- 他者の解法
こどふぉ #697 div3
— keroru (@keroru10) January 25, 2021
A 2でひたすら割る
B 2021*2020以上は大丈夫、以下は2020の数で全探索
C 各人から出る辺の数をカウント
D 尺取りでバグったので累積和を二分探索
E k番目の数をmとするとC(mの個数,k-mより大きい数の個数)
F AxorBを0にできるかどうかは、全行が一行目と同じか、その反転のどちらか
たしかにそうっぽいが天才感がある。もっと再現性のある方法はないか?ということで以下に続く
- 私の解法
- A[i][j] ^= B[i][j]として、Aを全て0にする問題にする
- 1行目のswapを「やる」「やらない」の両方試す
- 1行目のswapをやった後でも1行目にまだ1が残っているならば、その1は縦swapにより0にする必要がある。つまり1行目を決めてやると縦のswapをするかどうかが全て決まる
- あと残された操作は2行目以降の横swapのみ。これを使って全てを0にできればYES
- (蟻本でも「1行目を決めてやれば後は決まる」というのがありましたね)
code
// for codeforces void solve(){ ll N; cin>>N; VV A(N, VI(N)); VV B(N, VI(N)); rep(i,N){ string s;cin>>s; rep(j,N){ if(s[j]=='1')A[i][j]=1; } } rep(i,N){ string s;cin>>s; rep(j,N){ if(s[j]=='1')B[i][j]=1; } } rep(i,N){ rep(j,N){ A[i][j] ^= B[i][j]; } } auto A_original = A; // 1週目 1行目をswapしない場合 // 2週目 1行目をswapした場合 rep(_,2){ A = A_original; if(_==0){ // 1行目をswap rep(i,N){ A[0][i] ^= 1; } } // check // 1行目を見て、列のswapが必要な箇所は今1である部分 rep(x,N){ if(A[0][x]==1){ // その列は全てswapする rep(y,N){ A[y][x] ^= 1; } } } bool ok=true; FOR(y,1,N){ // 残りの行は0にできるか // 全部0か、全部1なら横swapにより可能 ll sum = SUM(A[y]); if(sum==0 or sum==N){ // safe }else{ ok=false; } } if(ok){ p_yes();return; } } p_no(); } int main(){ cin.tie(0); ios::sync_with_stdio(false); // input ll N;cin>>N; while(N--)solve(); return 0; }