問題はこちら。
簡単に訳するとこんな感じ。
立方体を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;
- }
ちょっと、この才能の差を埋めるにはかなり時間がかかりそうだな~~~。。。