Atcoder ARC #002 D. ボードゲーム
D: ボードゲーム - AtCoder Regular Contest 002 | AtCoder
２時間ほどかかったが自力で通したので、個人的にはARCのD（F）にしてはぬるめの考察問題だったと思う。
ボード上の２種類のコマ'o'と'x'の状態が与えられる。'o'は右に、'x'は左に向かって１歩ずつ進める。進行方向に異なるコマがあれば、それを踏み潰せる。'o'からスタートし、理想的に動いたとき、向かっている方向の端っこに先についた方が勝ちであるとき、どちらが勝つかを判定する問題。
まずサンプルケースを見ると気づくことだが、進行方向に相手のコマがないコマが存在すれば、それらの端までの距離を比較するだけで答えが出る。そうでない場合は、すべてのコマが左に'o'のみ、右に'x'のみというペアに分けられ、これらは独立に考えて良い。少し考察すると、自分のターンで動かせるところが、「o'スペース'x'」の部分だけになったときは負ける、ということがわかる。よって、できる限りこの状況に到るまでの自分にとっての余裕のようなものを最大化し、相手にとっての余裕のようなものを最小化するような動きをとればよい。さらに考察すると、動かすべきコマは、向かい合うコマのそれぞれの後ろのコマの個数の和が最も大きいものであることがわかる。なぜならば、中央のコマを動かすことで自分にとっての余裕はその後ろのコマの数だけ進むスペースを作ることができ、さらに相手が進む距離を１少なくできるので、相手にとって増やせたであろう余裕度の増加を阻止できるからである。この和を余裕度とよぶことにし、各ペアについて、余裕度がどれくらい生まれるかをカウントし、最後に比較すると答えがわかる。O(HW)。余裕度の計算はすでに解いていたC: ウサギ跳び - AtCoder Regular Contest 041 | AtCoderと似た発想だったので、すぐに実装できた。
#include "bits/stdc++.h" using namespace std; #define OUT(x) cout << #x << " = " << x << endl #define rep(i, n) for (int (i) = 0; (i) < (int)(n); (i)++) #define rer(i, l, r) for (int (i) = (int)(l); (i) <= (int)(r); (i)++) #define reu(i, l, r) for (int (i) = (int)(l); (i) < (int)(r); (i)++) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() template<typename T> void pv(T a, T b) { for (T i = a; i != b; i ++) cout << *i << " "; cout << endl; } template<typename T, typename U> inline void amin(T &x, U y) { if (y < x) x = y; } template<typename T, typename U> inline void amax(T &x, U y) { if (x < y) x = y; } int in() { int x; scanf("%d", &x); return x; } long long lin() { long long x; scanf("%lld", &x); return x; } static const long long INFL = 0x3f3f3f3f3f3f3f3fLL; #define int long long signed main() { int H, W; cin >> H >> W; vector<string> c(H); rep(i, H) cin >> c[i]; int od = INFL, xd = INFL; rep(i, H) { rep(j, W) { if (c[i][j] == 'x') { //最初に'x'がある場合は向かい合うコマがないことを意味する amin(xd, j); break; } if (c[i][j] == 'o') break; } reverse(all(c[i])); //reverseして同様に'o'も考える rep(j, W) { if(c[i][j] == 'o') { amin(od, j); break; } if (c[i][j] == 'x') break; } reverse(all(c[i])); //元に戻す } if (od != INFL || xd != INFL) { //どちらかが向き合ってないコマをもっていれば、答えが出る if (od <= xd) cout << 'o' << endl; else cout << 'x' << endl; return 0; } vector<pair<int, pair<vector<int>, vector<int>>>> P; //各ペアを格納する。<コマの総数から各コマの先頭の数(=2)を引いた数, <'o'のある座標, 'x'のある座標>>で一つのペアにする vector<int> opoint; vector<int> xpoint; rep(i, H) { rep(j, W) { if (c[i][j] == '.') continue; if (c[i][j] == 'o') { if (!xpoint.empty()) { reverse(all(opoint)); //'o'については、中央からみて左にindexが増加するようにしておくとわかりやすい P.push_back(make_pair(opoint.size() + xpoint.size() - 2, make_pair(opoint, xpoint))); opoint.clear(); xpoint.clear(); } opoint.push_back(j); } else { xpoint.push_back(j); } } } reverse(all(opoint)); if (!xpoint.empty()) P.push_back(make_pair(opoint.size() + xpoint.size() - 2, make_pair(opoint, xpoint))); sort(rall(P)); //余裕度（？）で降順にソートして大きいものからコマを進める bool oturn = true; //最初'o'からはじめる int ocnt = 0, xcnt = 0; //余裕度 for (auto i : P) { int l = i.second.first.front(); //'o'の先頭のコマ int r = i.second.second.front(); //'x'の先頭のコマ int d = r - l; //先頭のコマ同士の間にあるマスの数＋１ d --; //mid - 1に'o'がきて、mid + 1に'x'がくるようにmid（スペースになるマスの位置）をつくる if (d & 1) { //奇数個のマスがあるときは、ターンは変わらない int mid = (l + r) / 2; reu(j, 1, i.second.first.size()) ocnt += (mid - 1) - i.second.first[j] - j; reu(j, 1, i.second.second.size()) xcnt += i.second.second[j] - (mid + 1) - j; } else { //偶数個のときはターンが必ず変わる上に、どちらのターンから始まるかによって、先頭のコマの到達位置も変わるので注意 if (oturn) { int mid = (l + r + 1) / 2; reu(j, 1, i.second.first.size()) ocnt += (mid - 1) - i.second.first[j] - j; reu(j, 1, i.second.second.size()) xcnt += i.second.second[j] - (mid + 1) - j; } else { int mid = (l + r) / 2; reu(j, 1, i.second.first.size()) ocnt += (mid - 1) - i.second.first[j] - j; reu(j, 1, i.second.second.size()) xcnt += i.second.second[j] - (mid + 1) - j; } oturn ^= 1; } } if (oturn) { //余裕度を使って動かし始めるときにどちらのターンかで最終的な答えを出す cout << (ocnt > xcnt ? 'o' : 'x') << endl; } else { cout << (ocnt < xcnt ? 'x' : 'o') << endl; } return 0; }
