kurarrr's memooo

主に競プロ備忘録

蟻本練習問題(反転)

競プロ

反転

問題訳
20個のビット列が与えられる。1つを反転させると両隣のビットも反転される。
全てを0にするのに必要な反転の最小回数は？

解法
最初のビットを反転するかを決めると、全部決まるので2通り

メモ
配列を初期化するのと最初の反転をカウントするのを忘れていた。

コード

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>
#include<stack>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;
 
typedef long long ll;
typedef pair<int,int> P;
const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N=100005;

int a[22],c[22];

int main(){
  rep(i,20) cin >> a[i] ;
  rep(i,20) c[i]=a[i];
  int ans=INF;
  rep(j,2){
    int cnt=0;
    rep(i,20) a[i]=c[i];
    if(j){
      a[0]^=1; a[1]^=1; cnt++;
    }
    rep(i,19){
      if(a[i]==1){
        a[i]^=1; a[i+1]^=1; a[i+2]^=1;
        cnt++;
      }
    }
    if(a[19]==0) ans=min(ans,cnt);
  }
  cout << ans << endl;
  return 0;
}

問題訳
5x6のマスがあり、1マスを反転させると隣接4マスも反転するようなパズルがある。
パズルの答えを示せ。(最小回数でなくとも良い)

解法
1行目を決めるとパタパタ決まる。

メモ
またも配列の初期化ミスってしんどいことに…

コード

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;
 
typedef long long ll;
typedef pair<int,int> P;
const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N=1002,MAX_K=102;

int a[5][7],c[5][7],ans[5][7];
int dx[5]={0,-1,0,1,0};
int dy[5]={0,0,1,0,-1};

void rev(int i,int j){
  rep(k,5){
    if((i+dy[k]>=0 &&i+dy[k]<5)&&(j+dx[k]>=0 && j+dx[k]<6)){
      c[i+dy[k]][j+dx[k]]^=1;
    }
  }
}

void calc(){
  rep(i,5) rep(j,6) scanf("%d",&a[i][j]);
  bool ok=false;
  rep(i,1<<6){
    rep(j,5) rep(k,6) c[j][k]=a[j][k];
    rep(j,5) rep(k,6) ans[j][k]=0;
    rep(j,6){
      ans[0][j]=(i>>j)&1;
      if(ans[0][j]){
        rev(0,j);
      }
    }
    REP(j,1,5){
      rep(k,6){
        if(c[j-1][k]){
          rev(j,k);
          ans[j][k]=1;
        }
      }
    }
    ok=true;
    rep(k,6){
      if(c[4][k]) ok=false;
    }
    if(DEBUG){
      cout << "cnt" << i << endl;
      rep(k,5){
      rep(j,5) cout << ans[k][j] << " " ;
        cout << ans[k][5] << endl;
      }
      cout << "--------" << endl;
      rep(k,5){
        rep(j,5) cout << c[k][j] << " " ;
        cout << c[k][5] << endl;
      }
      cout  << endl;
    }
    if(ok) break;
  }
  if(ok){
    rep(i,5){
      rep(j,5) cout << ans[i][j] << " " ;
      cout << ans[i][5] << endl;
    }
  }
}

int main(){
  int n;
  cin >> n ;
  rep(i,n){
    cout << "PUZZLE #" << i+1 << endl;
    calc();
  }
  return 0;
}