GCJ 2011 Round2 Spinning Blade復習

問題概要

R*Cの単位ブロックからなる長方形の鉄板がある。この鉄板から1辺がkの正方形を切り出す。さらに、4隅のブロックを切り落として、ブレードを作る。この鉄板は厚さが不均一なため、重心とブレードの中点が一致しないことがある。各ブロックの重さが与えられるので、重心とブレードの中点が一致するような最大のブレードのサイズを求める。

方針

正方形の左上のブロックを選ぶ。これを(x, y)とする。

　(x+k, y+k)が(r, c)を超えない間、kをインクリメント。

　　(x, y), (x+k, y+k)のブレードの重心および中点を計算する。一致すれば、答えに反映する。

これで、smallは通る。全体の処理は、O(N^5)。

largeを通すには、計算量を減らす必要がある。(x, y), (x+k, y+k)のブレードの重心計算は、(x, y), (x+k-1, y+k-1)のブレードの重心情報を利用すれば、O(N)で出来る。これは良くやる動的計画。中点は、((x+x+k)/2, (y+y+k)/2)なので、O(1)。これで全体の計算量はO(N^4)に落ちる。結構きわどいが、これでも通る。

Editorial解は、O(N^3)だった。ACrushとかrngさんとかもO(N^3)でやっていた。この方法は、非常に興味深い。

処理の概要は以下のとおり。

1. (0, 0), (x, y), x in {0,1,..,R-1}, y in {0,1,...C-1}のブレードの重心を予め計算しておく。このとき、(0,0),(x, y)の重心は、(0,0),(x-1,y-1)と、(0,0), (x-1,y)と、 (0,0),(x, y-1)の情報を利用すれば、O(1)で出来る。よって、1.の処理はO(N^2)
2. (x, y)(x+k, y+k)のブレードの重心は、(x, y) = (0, 0)の場合は、1.をそのまま使える。そうでない場合は、(0,0), (x+k, y+k)と、(0,0),(x+k, y-1)と、(0, 0),(x-1,y+k)と、(0,0),(x-1,y-1)の情報を使ってO(1)で求めることができる。よって2.の処理は、(x,y,k)のループのみとなり、O(N^3)

コードに落とすときの工夫だが、2.の場合分け（x=0とかy=0とか）をごちゃごちゃしなくていいように、上行と左列にdummyのバッファを入れておくとよい。

以下ソース。

int mass[512][512];
LL rec_m[512][512];
LL rec_gx[512][512];
LL rec_gy[512][512];

void gcjMain() {
    int t;

    cin >> t;
    REP(ii, t) {
        int r, c, d;

        cin >> r >> c >> d;
        vector<string> mtx(r);
        REP(i, r)
            cin >> mtx[i];

        REP(i, r) REP(j, c)
            mass[i][j] = mtx[i][j] - '0';

        memset(rec_m, 0, sizeof(rec_m));
        memset(rec_m, 0, sizeof(rec_gx));
        memset(rec_m, 0, sizeof(rec_gy));

        REP(i, r) REP(j, c) {
            rec_m[i+1][j+1] = rec_m[i][j+1] + rec_m[i+1][j] - rec_m[i][j] + mass[i][j];
            rec_gx[i+1][j+1] = rec_gx[i][j+1] + rec_gx[i+1][j] - rec_gx[i][j] + i * mass[i][j];
            rec_gy[i+1][j+1] = rec_gy[i][j+1] + rec_gy[i+1][j] - rec_gy[i][j] + j * mass[i][j];
        }

        int ret = -1;
        REP(i, r) REP(j, c) {
            for (int k = 2; i + k < r && j + k < c; k++) {
                LL ms;
                LL gx;
                LL gy;

                ms = rec_m[i+1+k][j+1+k] + rec_m[i][j] - rec_m[i+1+k][j] - rec_m[i][j+1+k];
                gx = rec_gx[i+1+k][j+1+k] + rec_gx[i][j] - rec_gx[i+1+k][j] - rec_gx[i][j+1+k];
                gy = rec_gy[i+1+k][j+1+k] + rec_gy[i][j] - rec_gy[i+1+k][j] - rec_gy[i][j+1+k];

                ms -= mass[i][j] + mass[i][j+k] + mass[i+k][j] + mass[i+k][j+k];
                gx -= i*mass[i][j] + i*mass[i][j+k] + (i+k)*mass[i+k][j] + (i+k)*mass[i+k][j+k];
                gy -= j*mass[i][j] + (j+k)*mass[i][j+k] + j*mass[i+k][j] + (j+k)*mass[i+k][j+k];

                if (ms * (i + i + k) == 2 * gx && ms * (j + j + k) == 2 * gy)
                    ret = max(ret, k+1);
            }
        }

        if (ret == -1)
            printf("Case #%d: IMPOSSIBLE\n", ii+1);
        else
            printf("Case #%d: %d\n", ii+1, ret);
    }
}