Search on the blog

2010年11月28日日曜日

空間認知能力

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

問題はこちら。

簡単に訳するとこんな感じ。
立方体を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;

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

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


0 件のコメント:

コメントを投稿