保存されている過去のバージョンの一覧

2015年12月09日17時21分36秒

CODE THANKS FESTIVAL 2015 H問題 - 穴あきケーキ

Source

CODE THANKS FESTIVAL 2015
問題文

問題概要

長方形のケーキが $R$ 行 $C$ 列のマスに分割されている．
縦も横も $3$ マス以上の長方形の領域を $1$ つ選び，その周ではなく内部の $1$ マスを取り除いたような穴あきケーキを作りたい．
各マス $(i,j)$ のカロリー量 $S_{i,j}$ が与えられる．
総カロリー量が $K$ となるような穴あきケーキの作り方のパターン数を求める問題．

解法

前計算に $O(RCs)$ 時間（$s = \max(S_{ij})$）を使って，二次元累積和を用いて，各長方形の領域に $1$ から $9$ のカロリーのマスが何個あるかを $O(1)$ で求められるようにしておく．
穴ケーキの長方形の左端と右端を全探索し，上端と下端は尺取法にて探索する．
尺取法においては，上端を決めると，穴を開ける前の長方形の領域のカロリーの合計が $K+1$ から $K+9$ までとなるような下端を探せば良い．
下端を $1$ マス下に移動させると，最低でもカロリーが $3$ 増えるので，そのような下端の数は最大でも $3$ 個しかない．
後は，余分なカロリー量と同じカロリーのマスが何個あるかを求め，それを足していけば良い．
カロリーの総量を求めるには，考えている範囲において，各行の総カロリーを求めておいたり，もしくはこれも二次元累積和を用いても良い．
時間計算量は $O(RCs+RC^2)$ 程度．

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

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

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
#define ll long long
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);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;}
template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}

int X, Y, K;
int S[360][360];

int sum[360];
int cnt[10][360][360];
char buf[360];

inline int get_sum(int x1, int x2, int y1, int y2, int mp[][360]){
  return mp[x2+1][y2+1] - mp[x1][y2+1] - mp[x2+1][y1] + mp[x1][y1];
}

int main(){
  int i, j, k, cur, tar;
  int x1, x2;
  ll res = 0;

  reader(&X,&Y,&K);
  rep(i,X){
    reader(buf);
    rep(j,Y) S[i][j] = buf[j]-'0';
  }

  REP(k,1,10) rep(i,X) rep(j,Y){
    cnt[k][i+1][j+1] = cnt[k][i+1][j] + cnt[k][i][j+1] - cnt[k][i][j];
    if(S[i][j]==k) cnt[k][i+1][j+1]++;
  }

  rep(x1,X-2){
    rep(i,Y) sum[i] = S[x1][i]+S[x1+1][i];
    REP(x2,x1+2,X){
      rep(i,Y) sum[i] += S[x2][i];
      
      j = 0; cur = sum[0];
      rep(i,Y){
        while(j < Y && (j<i+2 || cur<=K)) cur += sum[++j];
        if(j >= Y) break;

        tar = cur - K - sum[j];
        REP(k,j,Y){
          tar += sum[k];
          if(tar>=10) break;
          res += get_sum(x1+1,x2-1,i+1,k-1,cnt[tar]);
        }
        cur -= sum[i];
      }
    }
  }
  writerLn(res);

  return 0;
}

Current time: 2024年04月16日20時44分42秒
Last modified: 2015年12月09日17時21分36秒 (by laycrs)
Tags: Competitive_Programming AtCoder code-thanks-festival-2015-open
トップページに戻る

Logged in as: unknown user (not login)

ログイン：