Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Beta Round #15 D問題 - Map (この記事を編集する[管理者用])

Source

Codeforces Beta Round #15 D問題
Problem description
Beta Round #15の自分の参加記録

問題概要

1000*1000の場所の高さが与えられる.
a*bのビルを建てたい.
建てるときは建てる場所のうち,標高が最も低い場所にあわせて,余分な部分を削る.
次のような操作を繰り返す.
 建てれる場所が残っているなら,削る体積が最小で建てれる場所のうち,最も左上に建てる
結果をシミュレーションする問題.

解法

まず,すべてのマス目に対して,そのマスを左上端にして建てるときに削る体積を求める.
それは,そのマスを左上とするa*bの長方形の部分の和と最小値を求めておけば良い.
和はDPでO(1000^2)で求まるが,最小値はいい方法がわからなかったので愚直に(でも1次元分は覚えておいて)やってO(1000*a)でやってぎりぎり間に合った.
後は,削る体積の値でソートしておいて,立地条件の良い場所から,実際に建てていく.
建てたら,それとオーバーラップするような場所には建てれないフラグを立てて,フラグが建っているなら無視する.

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

このコードは実際に本番でサブミットしたコードです.見にくいと思われます.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

void intIntSort(ll d[],int m[],int s){
  ll i=-1,j=s,k,t;
  if(s<=1)return;k=(d[0]+d[s-1])/2;
  for(;;){while(d[++i]<k);while(d[--j]>k);if(i>=j)break;
    t=d[i];d[i]=d[j];d[j]=t;
    t=m[i];m[i]=m[j];m[j]=t;
  }
  intIntSort(d,m,i);intIntSort(d+j+1,m+j+1,s-j-1);
}

void intSort(int d[],int s){int i=-1,j=s,k,t;if(s<=1)return;k=(d[0]+d[s-1])/2;for(;;){while(d[++i]<k);while(d[--j]>k);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;}intSort(d,i);intSort(d+j+1,s-j-1);}

int in[1100][1100];
ll sum[1100][1100], tmp[1100][1100], mn[1100][1100];

ll d[1000100]; int ind[1000100];

int res1[1000100],res2[1000100]; ll resd[1000100]; int res_size;

int main(){
  int i,j,k,l,m,n;
  int x,y,sx,sy,xy;
  int a,b;
  ll t;

  scanf("%d%d%d%d",&x,&y,&sx,&sy);
  rep(i,x) rep(j,y) scanf("%d",in[i]+j);

  rep(i,x){
    t=0;
    rep(j,sy) t += in[i][j];
    tmp[i][0]=t;
    REP(j,sy,y){
      t += in[i][j] - in[i][j-sy];
      tmp[i][j-sy+1] = t;
    }
  }

  rep(j,y-sy+1){
    t=0;
    rep(i,sx) t += tmp[i][j];
    sum[0][j]=t;
    REP(i,sx,x){
      t += tmp[i][j] - tmp[i-sx][j];
      sum[i-sx+1][j] = t;
    }
  }

  rep(i,x){
    rep(j,y-sy+1){
      t = in[i][j];
      REP(k,1,sy) if(t > in[i][j+k]) t = in[i][j+k];
      tmp[i][j]=t;
    }
  }

  rep(j,y-sy+1){
    rep(i,x-sx+1){
      t=tmp[i][j];
      REP(k,1,sx) if(t > tmp[i+k][j]) t = tmp[i+k][j];
      mn[i][j]=t;
    }
  }
  x = x-sx+1; y = y-sy+1; xy = x*y;
  rep(i,x) rep(j,y) d[i*y+j] = sum[i][j]-mn[i][j]*sx*sy;

  rep(i,xy) ind[i]=i;
  intIntSort(d,ind,xy);
  for(a=0;a<xy;){
    b=a+1; while(b<xy && d[a]==d[b]) b++;
    intSort(ind+a,b-a);
    a=b;
  }

  rep(i,x) rep(j,y) d[i*y+j] = sum[i][j]-mn[i][j]*sx*sy;

  res_size=0;
  rep(l,xy){
    k=ind[l]; if(d[k]<0) continue;
    i=k/y; j=k%y;
    res1[res_size]=i; res2[res_size]=j; resd[res_size++]=d[k];

    REP(a,i-sx+1,i+sx) if(0<=a&&a<x) REP(b,j-sy+1,j+sy) if(0<=b&&b<y) d[a*y+b]=-1;
  }

  printf("%d\n",res_size);
  rep(i,res_size) printf("%d %d %lld\n",res1[i]+1,res2[i]+1,resd[i]);
  
  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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