Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Round #219 DIV1 B問題/DIV2 D問題 - Counting Rectangles is Fun (この記事を編集する[管理者用])

Source

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

問題概要

$N \times M$ のサイズのグリッドが与えられる.それぞれのセルには $0$ か $1$ が書かれている.
$Q$ 個のクエリが与えられる.
各クエリでは,長方形領域が与えられるので
 その長方形領域に含まれる長方形領域の中で,セルが全部 $0$ となるようなものの数
を求める.
$1 \leq N, M \leq 40$
$1 \leq Q \leq 3 \times 10^5$

解法

クエリの数を考えると最悪ケースでほぼすべてのパターンのクエリが来うるので,最初に全部の長方形領域に対して答えを計算しておく.
まず,ある場所より左上にある $0$ の数とか,そういうのは,縦に横に累積和を取ったり,包除原理を用いたりで $O(\mbox{セルの数})$ 計算できる.
全部 $0$ となるような長方形のうち,左上の場所 $(r_1, c_1)$ を決めつける.
右下の座標としてvalidがどうかを判定する.それは,左上に $1$ がある場所の数が $0$ 個であれば良い.
次に,ある座標 $(r_2, c_2)$ より左上に右下とvalidな座標の数を同様の方法により数える.
後は,その数を,左上 $(r,c)$,$(r \leq r_1,\ c \leq c_1)$,右下 $(r_2,c_2)$ に対応するクエリの答えに足していく.
$O(N^3 M^3)$.
他にもいろいろな方法があるらしい.

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)

#define ll long long
#define READER_BUF_SIZE 65536
#define myIsDigit(x) ('0'<=(x) && (x)<='9')
#define myIsSpace(x) ((x)==' ' || (x)=='\t' || (x)=='\n' || (x)=='\r')

int reader_pt = READER_BUF_SIZE;
char reader_buf[READER_BUF_SIZE];

int reader_nonneg_int(){
  int r;

  for(;;){
    if(reader_pt==READER_BUF_SIZE) reader_pt = 0, fread(reader_buf, READER_BUF_SIZE, sizeof(char), stdin);
    if(myIsDigit(reader_buf[reader_pt])) break;
    reader_pt++;
  }
  r = reader_buf[reader_pt++] - '0';
  for(;;){
    if(reader_pt==READER_BUF_SIZE) reader_pt = 0, fread(reader_buf, READER_BUF_SIZE, sizeof(char), stdin);
    if(!myIsDigit(reader_buf[reader_pt])) break;
    r = r*10 + (reader_buf[reader_pt++]-'0');
  }
  reader_pt++;

  return r;
}

int reader_string(char res[]){
  int len = 0;
  for(;;){
    if(reader_pt==READER_BUF_SIZE) reader_pt = 0, fread(reader_buf, READER_BUF_SIZE, sizeof(char), stdin);
    if(!myIsSpace(reader_buf[reader_pt])) break;
    reader_pt++;
  }
  for(;;){
    if(reader_pt==READER_BUF_SIZE) reader_pt = 0, fread(reader_buf, READER_BUF_SIZE, sizeof(char), stdin);
    if(myIsSpace(reader_buf[reader_pt])){
      reader_pt++;
      break;
    }
    res[len++] = reader_buf[reader_pt++];
  }
  res[len] = '\0';
  return len;
}


int main(){
  int i,j,k,l,m,n;
  int x, y, q;
  char mp[50][50];
  int sum[50][50];
  static int res[41][41][41][41];
  int x1, y1, x2, y2;

  x = reader_nonneg_int();
  y = reader_nonneg_int();
  q = reader_nonneg_int();
  rep(i,x) reader_string(mp[i]);

  rep(x1,x) rep(y1,y) rep(x2,x) rep(y2,y) res[x1][y1][x2][y2] = 0;

  rep(x1,x) rep(y1,y){
    REP(i,x1,x) REP(j,y1,y) sum[i][j] = 0;
    REP(i,x1,x){
      REP(j,y1,y){
        if(mp[i][j]=='1') break;
        if(i>x1 && sum[i-1][j]==0) break;
        sum[i][j] = 1;
      }
    }
    REP(i,x1,x) REP(j,y1+1,y) sum[i][j] += sum[i][j-1];
    REP(j,y1,y) REP(i,x1+1,x) sum[i][j] += sum[i-1][j];

    rep(i,x1+1) rep(j,y1+1) REP(x2,x1,x) REP(y2,y1,y) res[i][j][x2][y2] += sum[x2][y2];
  }

  while(q--){
    x1 = reader_nonneg_int() - 1;
    y1 = reader_nonneg_int() - 1;
    x2 = reader_nonneg_int() - 1;
    y2 = reader_nonneg_int() - 1;
    printf("%d\n",res[x1][y1][x2][y2]);
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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