Codeforces Round #243 DIV1 B問題/DIV2 D問題 - Sereja and Table

Source

Codeforces Round #243 DIV1 B問題 (1000pt)
Codeforces Round #243 DIV2 D問題 (2000pt)
Problem description

問題概要

$N$ 行 $M$ 列の盤面が与えられる.
各セルには $0$ か $1$ かのどちらかが書かれている.
上下左右に繋がっているとして,$0$ のみから成る連結成分,$1$ のみから成る連結成分が全て(中の詰まった)長方形になるようにしたい.
$K$ 回以下だけセルの要素を変更して良い.
そのようにできるなら,そのようにするための,セルの変更の最小回数を求める,できないならばそれを指摘する問題.

解法

$0$ と $1$ の $2$ 種類しかないので,全ての連結成分が長方形になるということは,(幅や高さは各行,各列で違うのも許して)市松模様のようになるしかない.
つまり,ある行のパターンを決めてしまったら,その他の行は,決めたパターンと全く同じか,それと $0$ と $1$ を全て反転したものでなくてはいけなくて,そうであれば良い.
そこで,ある $1$ 行のパターンを決めてしまったら,その他の行は,$2$ 通りのうち,変更回数の小さい方に合わせれば良いことになる.
(上のことは,行を列に読み替えても同じ)
行数 $N$ が $K$ 以下か,$K$ より大きいかで場合分けする.(または,$K$ の最大値 $10$ より大きいかどうかで場合分け)
行数が $K$ 以下である場合は,各列の要素は $K$ 以下ということなので,列のパターンとして考えられるのは $2^K$ 以下しかないので,全て試せば良い.
行数が $K$ より大きい場合は,最高で $K$ セルまでしか変更できないので,少なくても $1$ 行は変更されない.
よって,全ての(あるいは$K+1$個の)行を取ってきて,それを行の基本パターンとして試せば良い.

C++のスパゲッティなコード

#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<string>
#include<utility>
#include<iostream>
#include<cmath>
#include<ctime>
#include<cassert>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define READER_BUF_SIZE 1048576
#define WRITER_BUF_SIZE 1048576
int reader_pt=READER_BUF_SIZE,reader_last;char reader_buf[READER_BUF_SIZE];
int writer_pt=0;char writer_buf[WRITER_BUF_SIZE];
#define mygc(c) {if(reader_pt==READER_BUF_SIZE)reader_pt=0,reader_last=fread(reader_buf,sizeof(char),READER_BUF_SIZE,stdin);(c)=reader_buf[reader_pt++];}
#define mypc(c) {if(writer_pt==WRITER_BUF_SIZE)writer_pt=0,fwrite(writer_buf,sizeof(char),WRITER_BUF_SIZE,stdout);writer_buf[writer_pt++]=(c);}
#define myed {fwrite(writer_buf,sizeof(char),writer_pt,stdout);writer_pt=0;}

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}
void reader(int *x, int *y, int *z){reader(x);reader(y);reader(z);}
void writer(int x, char c){int i,sz=0,m=0;char buf[10];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}

int pt[120], mp[120][120];

int solve(int x, int y){
  int i, j, add, tmp;
  tmp = 0;
  rep(j,y){
    add = 0;
    rep(i,x) if(pt[i] != mp[i][j]) add++;
    tmp += min(add, x-add);
  }
  return tmp;
}

int main(){
  int i, j;
  int x, y, k;
  int mp2[120][120], mask;
  int res, tmp, add;

  res = 1000000;

  reader(&x,&y,&k);
  rep(i,x) rep(j,y) reader(mp[i]+j);

  if(x <= k){
    rep(mask, 1<<x){
      rep(i,x) if(mask & 1<<i) pt[i] = 1; else pt[i] = 0;
      res = min(res, solve(x,y));
    }
  } else {
    rep(i,x) rep(j,y) mp2[i][j] = mp[i][j];
    swap(x,y);
    rep(i,x) rep(j,y) mp[i][j] = mp2[j][i];

    rep(mask, k+1){
      rep(i,x) pt[i] = mp[i][mask];
      res = min(res, solve(x,y));
    }
  }

  if(res > k) res = -1;

  writer(res, '\n');
  myed;

  return 0;
}

Current time: 2017年11月18日04時21分06秒
Last modified: 2014年05月03日17時20分48秒 (by laycrs)
Tags: Competitive_Programming Codeforces CF243 CF_Div1_B CF_Div2_D
トップページに戻る

Logged in as: unknown user (not login)

ログイン: