Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2151-2b2a3ab2
この記事にトラックバックする(FC2ブログユーザー)

Beta Round #93 DIV1 C問題/DIV2 E問題 - E-reader Display (この記事を編集する[管理者用])

Source

Codeforces Beta Round #93 DIV1 C問題 (1500pt)
Codeforces Beta Round #93 DIV2 E問題 (2500pt)
Problem description

問題概要

n*n (2000*2000以下) のマス目があって,最初は全てのマスが白色.
1回の操作でできることは,あるマス(x,y)を指定して,
 2つの両端を含む線分,(x,x) - (x,y),(x,y) - (y,y) の少なくてもどちらかに属するマスの白黒を反転させる.
ある図形が与えられるので,それを作るのに最小で何回の操作が必要かを求める問題.

解法

操作は,あるマスから対角線まで2本の線分を伸ばしてそこを反転させるもの.
ちょっと考えると,(同じマスを2回選ばないなら)作る方法は1通りしかないことがわかり,それは,greedyにマスを選べば良い.
つまり,一番左下,もしくは,一番右上の反転させなくてはいけないセルを選び反転させる,を繰り返すことになる.
ただし,1回の反転でO(n)かかる愚直なシミュレーションしていくと,O(n^3)になってしまうので,左下と右上の領域は別々に考えて,
現在の行,現在の列は何回反転したか,という情報だけもっておけば,O(n^2)でできる.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

char mp[2100][2100], tmp[2100][2100];
int go[2100];

int main(){
  int i,j,k,l,m,n,loop;
  int res;
  
  while(scanf("%d",&n)==1){
    rep(i,n) scanf("%s",mp[i]);
    res = 0;

    rep(i,n) rep(j,n) mp[i][j] -= '0';

    rep(loop,2){
/*      printf("loop %d\n",loop);
      rep(i,n){ rep(j,n)putchar(mp[i][j]+'0'); puts(""); }*/

      rep(i,n) go[i] = 0;
      for(i=n-1;i>=0;i--){
        k = 0;
        for(j=0; j<=i; j++){
          m = mp[i][j];
          m += k;
          m += go[j];
          
          if(j!=i){
            if(m%2){
              res++;
              k++;
              go[j]++;
            }
            mp[i][j] = 0;
          } else {
            mp[i][j] = m%2;
          }
        }
      }
      if(loop==0){
        rep(i,n) rep(j,n) tmp[i][j] = mp[i][j];
        rep(i,n) rep(j,n) mp[i][j] = tmp[j][i];
      }
    }

    rep(i,n) if(mp[i][i]) res++;

    printf("%d\n",res);
  }

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2151-2b2a3ab2
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。