Learning Algorithms

アルゴリズムの勉強メモ

Atcoder Regular Contest 013 C. 笑いをとれるかな?

Atcoder Regular Contest 013 C. 笑いをとれるかな?

C: 笑いをとれるかな? - AtCoder Regular Contest 013 | AtCoder

感想

友人が問題文の内容がおもしろいと言っていたのでやったみた。確かにおもしろかった。

解法

各座標軸を基準にみて端点同士の点より内側にある部分は決して食べることができない。よってこれは大きなハバネロが一つ埋め込まれているものとして考えてよく、それぞれの座標のハバネロの位置の最小値と最大値がわかれば、あとはその外側の幅の部分を食べていけることになる。

この幅が高々$\ 6 * N\ $個あって、それらを山とみれば、単純な$\ Nim\ $になっているので、$\ XOR\ $をとると答えがわかる。

実装
#include "bits/stdc++.h"
using namespace std;

static const int INF = 0x3f3f3f3f;

int main() {
        int n;
        scanf("%d", &n);
        int ans = 0;
        for (int i = 0; i < n; i ++) {
                int X, Y, Z;
                int m;
                scanf("%d%d%d%d", &X, &Y, &Z, &m);
                int min_x = INF, max_x = 0, min_y = INF, max_y = 0, min_z = INF, max_z = 0;
                for (int i = 0; i < m; i ++) {
                        int x, y, z;
                        scanf("%d%d%d", &x, &y, &z);
                        min_x = min(min_x, x);
                        max_x = max(max_x, x);
                        min_y = min(min_y, y);
                        max_y = max(max_y, y);
                        min_z = min(min_z, z);
                        max_z = max(max_z, z);
                }
                max_x = X - max_x - 1;
                max_y = Y - max_y - 1;
                max_z = Z - max_z - 1;
                int res = 0;
                res = min_x ^ max_x ^ min_y ^ max_y ^ min_z ^ max_z;
                ans ^= res;
        }
        puts(ans ? "WIN" : "LOSE");
        return 0;
}