SRM 660 Div1 Easy - Coversta

問題

TopCoder Statistics - Problem Statement

問題概要

行列のグリッドが与えられる．各グリッドの中には0~9のいずれかの数字が書かれている．そして，stationをに設置すると， ()内に書かれている数字の合計をポイントとして得ることが出来る．

今，stationを2つ設置しようと考える．仮に両方のstationが同じグリッドをカバーした時の点数は1回分としてしか数えない(つまり2つのstationがカバーするグリッドの和集合が得られるポイントになる)．そのときに得られる得点の最大値を答えよ．

• 
• 
• 

アイデア

2つのstationの領域が被ってしまう時にどうすればいいかとかいうことを考えると効率的な方法が思いつけなかった．Editorialを見ながら．

1つ目のstationを固定して考えよう．すると，そのstationによってカバーされるグリッドの個数はたかだか個になる．そして，1つ目の設置されたstationに対応するある座標に対して，2つ目のstationを設置した時にその2つ目のstationがをカバーしてしまう2つ目のstationの設置方法はたかだか個存在する．つまり，1つ目のstationによってカバーされるたかだか個のグリッドを，2つ目のstationの設置によってカバーしてしまう可能性というのは組み合わせを考えればたかだか箇所になる．

つまり，まず1つ目のstationの位置を全探索する．その中で，被る可能性のあるたかだか箇所を調べ，2つ目のstationを設置することによって得られるポイントを逐次更新していく(正確には，被っている部分を引いていく)．

それが全ての座標に対して終われば，その1つ目のstation固定に関しての2つ目のstationによって得られる得点が確定するので，2つ目のstationの位置を全探索しながら得られる得点の最大値を更新していく．

実装(C++)

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

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second

typedef vector<int> vi;
typedef vector<vi> vvi;

class Coversta {
    public:
    int X,Y;
    inline bool in(int x, int y)
    {
        return(0<=x&&x<X && 0<=y&&y<Y);
    }

    int place(vector<string> a, vector<int> x, vector<int> y) {
        X=a.size();
        Y=a[0].size();

        int z=x.size();

        //1つ目のstation設置によって得られるpoint
        vvi sum1(X,vi(Y,0));
        rep(i,X)rep(j,Y)rep(k,z)
        {
            int nx=i+x[k], ny=j+y[k];
            if(in(nx,ny)) sum1[i][j]+=(a[nx][ny]-'0');
        }

        int ret=0;
        //1つ目のstationの位置を固定
        rep(i,X)rep(j,Y)
        {
            //2つ目のstation設置によって得られるpoint
            vvi sum2=sum1;

            //1つ目のstationのp個目のグリッドと
            //2つ目のstationのq個目のグリッドが
            //重なっていると仮定した時
            rep(p,z)
            {
                int nx=i+x[p], ny=j+y[p];
                if(in(nx,ny))
                {
                    rep(q,z)
                    {
                        int nnx=nx-x[q], nny=ny-y[q];
                        if(in(nnx,nny)) sum2[nnx][nny]-=(a[nx][ny]-'0');
                    }
                }
            }

            //1つ目のstationの固定に対してベストな位置を選択
            rep(k,X)rep(l,Y) ret=max(ret,sum1[i][j]+sum2[k][l]);
        }

        return ret;
    }
};