空間認知能力

今日練習した問題で面白いのがあったので紹介。

問題はこちら。

http://www.topcoder.com/stat?c=problem_statement&pm=9954&rd=13506

簡単に訳するとこんな感じ。

立方体をn*n*n個の小さな立方体に分ける。そのあと、適当に小さな立方体を抜き取る。

そして、この立方体の写真を三方向（x軸、y軸、z軸方向）から取る。

3枚の写真を見て、抜き取られた可能性のある小さな立方体の最小個数を求めよ。

最近買ったルーブックキューブと睨めっこ・・・。

結局解けなかった。。この問題は、テクニックというより、生まれ持った才能による部分が大きい気がする・・・・。そういえば、高校のとき「東大に行きたければ、数学は空間系の問題に強くならないとダメだ。」って先生が言ってたのを思い出した。

まー、話を戻して、友達の回答を見て自分なりに書いたコードはこんな感じ。

int removeCubes(vector<string> A, vector<string> B, vector<string> C) {
   // A x-y
   // B x-z
   // C y-z

   int sz = (int)A.size();

   memset(cube, 1, sizeof(cube));
   REP(i, sz) {
       REP(j, sz) {
           if (A[i][j] == 'N') REP(k, sz) cube[i][j][k] = 0;
           if (B[i][j] == 'N') REP(k, sz) cube[i][k][j] = 0;
           if (C[i][j] == 'N') REP(k, sz) cube[k][i][j] = 0;
       }
   }

   // valid-check
   REP(i, sz) {
       REP(j, sz) {
           if (A[i][j] == 'Y') {
               int t = 0;
               REP(k, sz)
                   t += cube[i][j][k];
               if (!t) return -1;
           }
           if (B[i][j] == 'Y') {
               int t = 0;
               REP(k, sz)
                   t += cube[i][k][j];
               if (!t) return -1;
           }
           if (C[i][j] == 'Y') {
               int t = 0;
               REP(k, sz)
                   t += cube[k][i][j];
               if (!t) return -1;
           }
       }
   }

   int ret = 0;
   REP(i, sz)REP(j,sz)REP(k,sz)
       if (!cube[i][j][k])
           ++ret;

   return ret;
}

なるほど！そういうことか！

ちょっと気になったのが、valid-checkのところ。なんか短くできそうな・・。

Editorialに赤い人のコードが載っていたので、それを参考に書いてみた。

こんな感じ。

int removeCubes(vector<string> A, vector<string> B, vector<string> C) {
    int sz = (int)A.size();
    bool a[sz][sz], b[sz][sz], c[sz][sz];

    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    memset(c, 0, sizeof(c));

    int ret = sz*sz*sz;
    REP(i,sz)REP(j,sz)REP(k,sz)
        if (A[i][j] == 'Y' && B[i][k] == 'Y' && C[j][k] == 'Y') {
            --ret;
            a[i][j] = 1;
            b[i][k] = 1;
            c[j][k] = 1;
        }


    REP(i,sz)REP(j,sz) {
        if (A[i][j] == 'Y' && !a[i][j]) return -1;
        if (B[i][j] == 'Y' && !b[i][j]) return -1;
        if (C[i][j] == 'Y' && !c[i][j]) return -1;
    }

    return ret;

}

ほう、逆の発想をすることで、判定のところがシンプルに書けるわけか。。結構このコード理解するのに時間かかりました（笑）

ちょっと、この才能の差を埋めるにはかなり時間がかかりそうだな～～～。。。