Page List

Search on the blog

2010年11月27日土曜日

空間認知能力

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

問題はこちら。

簡単に訳するとこんな感じ。
立方体をn*n*n個の小さな立方体に分ける。そのあと、適当に小さな立方体を抜き取る。
そして、この立方体の写真を三方向(x軸、y軸、z軸方向)から取る。
3枚の写真を見て、抜き取られた可能性のある小さな立方体の最小個数を求めよ。

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

まー、話を戻して、友達の回答を見て自分なりに書いたコードはこんな感じ。
  1. int removeCubes(vector<string> A, vector<string> B, vector<string> C) {  
  2.    // A x-y  
  3.    // B x-z  
  4.    // C y-z  
  5.   
  6.    int sz = (int)A.size();  
  7.   
  8.    memset(cube, 1, sizeof(cube));  
  9.    REP(i, sz) {  
  10.        REP(j, sz) {  
  11.            if (A[i][j] == 'N') REP(k, sz) cube[i][j][k] = 0;  
  12.            if (B[i][j] == 'N') REP(k, sz) cube[i][k][j] = 0;  
  13.            if (C[i][j] == 'N') REP(k, sz) cube[k][i][j] = 0;  
  14.        }  
  15.    }  
  16.   
  17.    // valid-check  
  18.    REP(i, sz) {  
  19.        REP(j, sz) {  
  20.            if (A[i][j] == 'Y') {  
  21.                int t = 0;  
  22.                REP(k, sz)  
  23.                    t += cube[i][j][k];  
  24.                if (!t) return -1;  
  25.            }  
  26.            if (B[i][j] == 'Y') {  
  27.                int t = 0;  
  28.                REP(k, sz)  
  29.                    t += cube[i][k][j];  
  30.                if (!t) return -1;  
  31.            }  
  32.            if (C[i][j] == 'Y') {  
  33.                int t = 0;  
  34.                REP(k, sz)  
  35.                    t += cube[k][i][j];  
  36.                if (!t) return -1;  
  37.            }  
  38.        }  
  39.    }  
  40.   
  41.    int ret = 0;  
  42.    REP(i, sz)REP(j,sz)REP(k,sz)  
  43.        if (!cube[i][j][k])  
  44.            ++ret;  
  45.   
  46.    return ret;  
  47. }  

なるほど!そういうことか!
ちょっと気になったのが、valid-checkのところ。なんか短くできそうな・・。
Editorialに赤い人のコードが載っていたので、それを参考に書いてみた。
こんな感じ。

  1. int removeCubes(vector<string> A, vector<string> B, vector<string> C) {  
  2.     int sz = (int)A.size();  
  3.     bool a[sz][sz], b[sz][sz], c[sz][sz];  
  4.   
  5.     memset(a, 0, sizeof(a));  
  6.     memset(b, 0, sizeof(b));  
  7.     memset(c, 0, sizeof(c));  
  8.   
  9.     int ret = sz*sz*sz;  
  10.     REP(i,sz)REP(j,sz)REP(k,sz)  
  11.         if (A[i][j] == 'Y' && B[i][k] == 'Y' && C[j][k] == 'Y') {  
  12.             --ret;  
  13.             a[i][j] = 1;  
  14.             b[i][k] = 1;  
  15.             c[j][k] = 1;  
  16.         }  
  17.   
  18.   
  19.     REP(i,sz)REP(j,sz) {  
  20.         if (A[i][j] == 'Y' && !a[i][j]) return -1;  
  21.         if (B[i][j] == 'Y' && !b[i][j]) return -1;  
  22.         if (C[i][j] == 'Y' && !c[i][j]) return -1;  
  23.     }  
  24.   
  25.     return ret;  
  26.   
  27. }  
ほう、逆の発想をすることで、判定のところがシンプルに書けるわけか。。結構このコード理解するのに時間かかりました(笑)

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


0 件のコメント:

コメントを投稿