問題
直方体の豆腐が複数用意される。各豆腐の中には1つ以上のハバネロが埋め込まれており、二人のプレイヤーがハバネロを避けながら豆腐をいずれかの面に平行な平面で切断していく。豆腐の個数、サイズ、ハバネロの位置を与えるので、どちらのプレイヤーも最善を尽くしたとき勝つ方を求めよ。
解法
ある面に平行な切断の操作は他の面に平行な成分に対して影響を及ぼさないため、豆腐1個につき6個の山があるNimゲームに帰着できる。各豆腐に対してハバネロをすべて含む最小の直方体を求め、その周囲にある豆腐の厚みについてそれぞれxorを取っていけば答えが求まる。
反省
1時間考えてもわからなかったので他人の提出やブログ等を読んだ。最終的には1時間6分でAC。
全てのハバネロを含む最小の直方体を求め、それら周囲にある豆腐の厚みを考えるところまでは行っていたが、Nimというものを今まで書いたことがなかったのでそれに帰着させようと思えなかった。アドホックな考察として「2以上の厚みは全て同じとして扱える」と勘違いし、厚みが「0,1,または2以上」の三パターンで分けられると思ってそれらの数をカウントして、1である個数が奇数であるか、2以上である個数が奇数であるかを判定すれば良いとして提出したが、かなり多くのケースがWAとなり完全に行き詰ってしまった。
Nimの答えを知ったあとで実験してみると、たとえば豆腐が一つとして、ハバネロの周囲6面の厚みが「0,0,0,0,2,3」のようなときに間違うことがわかった。当然だが2以上は全て同じなどということはなく、それぞれの数を別に考えなければならない。
Nimというかgrundy numberについての理解が浅いため解けなかったという典型の問題だと感じる。Nimって取れるコインの枚数に制約があると思っていたが、そうではないらしい。この問題はまさにNimなんだな。grundy数を習得したかったを読んで多少わかったような、しかしまだ応用はできなさそうな、という感じ。
コード
#include"bits/stdc++.h" using namespace std; using ll = long long; int main() { ll N; cin >> N; vector<ll> X(N), Y(N), Z(N); vector<vector<ll>> x(N), y(N), z(N); for (ll i = 0; i < N; i++) { cin >> X[i] >> Y[i] >> Z[i]; ll M; cin >> M; x[i].resize(M); y[i].resize(M); z[i].resize(M); for (ll j = 0; j < M; j++) { cin >> x[i][j] >> y[i][j] >> z[i][j]; } } //各豆腐についてハバネロを囲う最小の立方体を求める //そして、その周りの豆腐の厚みがどれだけあるか ll grundy = 0; for (ll i = 0; i < N; i++) { vector<vector<ll>> habanero(3, vector<ll>(2)); for (ll j = 0; j < 3; j++) { habanero[j][0] = INT_MAX; habanero[j][1] = INT_MIN; } for (ll j = 0; j < x[i].size(); j++) { habanero[0][0] = min(habanero[0][0], x[i][j]); habanero[0][1] = max(habanero[0][1], x[i][j]); habanero[1][0] = min(habanero[1][0], y[i][j]); habanero[1][1] = max(habanero[1][1], y[i][j]); habanero[2][0] = min(habanero[2][0], z[i][j]); habanero[2][1] = max(habanero[2][1], z[i][j]); } grundy ^= habanero[0][0]; grundy ^= X[i] - 1 - habanero[0][1]; grundy ^= habanero[1][0]; grundy ^= Y[i] - 1 - habanero[1][1]; grundy ^= habanero[2][0]; grundy ^= Z[i] - 1 - habanero[2][1]; } cout << (grundy ? "WIN" : "LOSE") << endl; }
