はまやんはまやんはまやん

hamayanhamayan's blog

CubesOnATable [TopCoderOpen 2018 Wildcard Round Easy]

150個の1×1×1の箱がある。
10×10の平面の上にこの箱を置いていく。
(0,0)から(9,9)まで100マスの上に順次置いていく。
箱を中途半端な位置に置くことや空中に浮くように置くことはできない。
平面を除いた周りから見える箱の面積がsurfaceになるように箱を置く方法を示せ。

解法

高さに上限は無いので、ある箱の上に箱を置くことで自由に+4することはできる(平面の上に置くと+5なので注意)
そのため、surface%4の0,1,2,3がそれぞれ作ることができれば、あとはその上に箱を置くことで目的のsurfaceを実現できる。
 
surface%4=1で作れる最小は5である。
これは1つ普通に置くと5になる。
surface=1は作れない。
 
surface%4=2で作れる最小は10である。
これは1つ置いて、隣接しないようにもう1つ置くと、5+5=10となる。
surface=2,6は作れない。
 
surface%4=3で作れる最小は11である。
これはL字で3つ置くと作れる。
surface=3,7は作れない。
 
surface%4=0で作れる最小は8である。
これは隣り合って2つ置くと作れる。
surface=4は作れない。
 
作れないsurfaceは判定して返して、作れる最小を作ったあとは、surfaceが0になるまで上に乗せていけばいい。

struct CubesOnATable {
    vector <int> placeCubes(int surface) {
        if (surface < 5) return {};
        if (surface == 6 or surface == 7) return {};

        vector<int> res;
        if (surface % 4 == 1) {
            res.push_back(0);
            res.push_back(0);
            res.push_back(0);
            surface -= 5;
        }
        else if (surface % 4 == 2) {
            res.push_back(0);
            res.push_back(0);
            res.push_back(0);
            res.push_back(2);
            res.push_back(2);
            res.push_back(0);
            surface -= 10;
        } else if (surface % 4 == 3) {
            res.push_back(0);
            res.push_back(0);
            res.push_back(0);
            res.push_back(1);
            res.push_back(0);
            res.push_back(0);
            res.push_back(0);
            res.push_back(1);
            res.push_back(0);
            surface -= 11;
        } else if (surface % 4 == 0) {
            res.push_back(0);
            res.push_back(0);
            res.push_back(0);
            res.push_back(1);
            res.push_back(0);
            res.push_back(0);
            surface -= 8;
        }

        rep(i, 0, surface / 4) {
            res.push_back(0);
            res.push_back(0);
            res.push_back(i + 1);
        }

        return res;
    }
};