床 [パソコン甲子園2019 予選 F]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0409

解説

https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0409/judge/3897204/C++14

シミュレーションをする。 つまり、タイルを敷き詰めをしていく訳だが、実際マス目を塗っていく必要は無い。
答えに必要なのは、ある1つのタイルの色だけであるためである。
例えば、問題文にある図の4番目の状態を考えると、既に塗られている領域に答えるべきタイルがない場合は、この塗られている領域に何が塗られているかというのは特に意味がない。
意味を持つのは、次に下に色2を塗るということである。
なので、状態として、現在塗られている領域の左下座標(sx, sy)と右上座標(tx, ty)、次に上下左右のどちらに塗るかという情報、そして、次に塗る色の情報である。

これだけわかっていれば、塗るべき座標が計算でき、塗るべき座標に答えるべき座標が含まれていれば、そのときに塗る色を答えればいい。
そうでないなら、塗るべき領域と塗られている領域を合体して、座標を計算し直し、塗るべき方向を回転させ、色を次に進めればいい。
これを繰り返していこう。

言うが易しで、実装は大変になるだろう。
うまく書く方法もあるだろうが、自分は丁寧に場合分けして実装していった。
x=0,y=0の場合は既に塗られているので、最初に答えておこう。
PCKでは実装を要求する問題も出てくる。

下の実装では、101010回ループとしている。
無限ループがちょっと嫌でこうしているだけで、無限ループと思ってくれればいい。

enum { UP = 0, RIGHT, DOWN, LEFT };
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
int x, y;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> x >> y;

    if (x == 0 and y == 0) {
        cout << 1 << endl;
        return;
    }

    int sx = 0, sy = 0, tx = 0, ty = 0;
    int dir = LEFT;
    int col = 2;

    rep(_, 0, 101010) {
        int sx2 = sx, tx2 = tx, sy2 = sy, ty2 = ty;

        if (dir == DOWN) {
            ty2 = sy - 1;
            sy2 = ty2 - (tx - sx + 1) + 1;
        } else if (dir == LEFT) {
            sx2 = tx + 1;
            tx2 = sx2 + (ty - sy + 1) - 1;
        } else if (dir == UP) {
            sy2 = ty + 1;
            ty2 = sy2 + (tx - sx + 1) - 1;
        } else if (dir == RIGHT) {
            tx2 = sx - 1;
            sx2 = tx2 - (ty - sy + 1) + 1;
        }

        if (sx2 <= x and x <= tx2 and sy2 <= y and y <= ty2) {
            cout << col << endl;
            return;
        }

        col++;
        if(3 < col) col = 1;

        dir = (dir + 1) % 4;

        chmin(sx, sx2);
        chmin(sy, sy2);
        chmax(tx, tx2);
        chmax(ty, ty2);

        //printf("%d %d %d %d\n", sx, tx, sy, ty);
    }
}