Codeforces 277C (170C) Game
問題
nxmの方眼紙がある。
方眼紙には1x1刻みで縦線と横線が引かれている。
(ふちに線はひかれていないものとする)
この用紙を使って二人が次のようなゲームをする。
- 二人が交互に手番をもつ。
- 手番のプレイヤーは、格子点と格子点を結ぶ、水平または垂直な線分を引く。
- 線分は、必ず長さ0以上のまだ線の引かれていない部分を含まなければならない。
- 線分のひけなくなった人の負け。
最初からひかれている線分が与えられるとき、
(この線分は、重複があったりする)お互いが最善を尽くすとして、
どちらが勝つか出力せよ。
先手が勝つ場合は、先手の最初の手として適当なものをどれか一つ出力せよ。
制約条件
n, m≦10^9
k≦10^5
方針
縦の線、横の線がそれぞれ一つの山に対応するようなNimをやっていることに相当する。
山の石の数は、線のうち、消えていない部分の長さである。
なので、Nimの必勝法通り、各山のxorを取り、それが0なら後手勝ちで、そうでないなら先手勝ちである。
先手勝ちのとき、xorを0にするような手を打てばよい。
消えてない部分の長さは、累積和などを使って上手く求めてやる。
ソースコード
int w, h, k; map<int, vector<pi> > tate, yoko; map<int, int> tatelen, yokolen; int calc(int &sz, int len, vector<pi> &v){ sort(all(v)); map<int, int> m; m[0] = m[len] = 0; rep(i, v.size()) m[v[i].first]++, m[v[i].second]--; int s = 0, p = 0; sz = 0; each(i, m){ if(s == 0) sz += i->first - p; s += i->second; p = i->first; } return sz; } int calc2(int sz, int len, vector<pi> &v){ map<int, int> m; m[0] = m[len] = 0; rep(i, v.size()) m[v[i].first]++, m[v[i].second]--; int s = 0, p = 0, sum = 0; each(i, m){ if(s == 0){ int t = i->first - p; if(sum <= sz && sz <= sum + t) return p + sz - sum; sum += t; } s += i->second; p = i->first; } assert(0); } int main(){ cin >> w >> h >> k; rep(i, k){ int x, y, X, Y; cin >> x >> y >> X >> Y; if(x > X) swap(x, X); if(y > Y) swap(y, Y); if(x == X) tate[x].pb(mp(y, Y)); else yoko[y].pb(mp(x, X)); } int sum = 0; each(i, tate) sum ^= calc(tatelen[i->first], h, i->second); each(i, yoko) sum ^= calc(yokolen[i->first], w, i->second); if((w - 1 - tate.size()) % 2) sum ^= h; if((h - 1 - yoko.size()) % 2) sum ^= w; if(sum == 0){ cout << "SECOND" << endl; return 0; } cout << "FIRST" << endl; each(i, tatelen){ int l = i->second; if((sum ^ l) <= l){ int ans = calc2(tatelen[i->first] - (sum ^ l), h, tate[i->first]); cout << i->first << " " << 0 << " " << i->first << " " << ans << endl; return 0; } } each(i, yokolen){ int l = i->second; if((sum ^ l) <= l){ int ans = calc2(yokolen[i->first] - (sum ^ l), w, yoko[i->first]); cout << 0 << " " << i->first << " " << ans << " " << i->first << endl; return 0; } } if(tate.size() < w - 1 && (sum ^ h) <= h){ for(int i = 1 ; i < w; i++) if(!tate.count(i)){ cout << i << " " << 0 << " " << i << " " << h - (sum ^ h) << endl; return 0; } } for(int i = 1 ; i < h; i++) if(!yoko.count(i)){ cout << 0 << " " << i << " " << w - (sum ^ w) << " " << i << endl; return 0; } return 0; }