2019-04-06

AtCoder AGC 002 E - Candy Piles (赤色, 1400 点)

AtCoder AtCoder1400点 AGC-E ゲーム逆形ゲームパリティ場合分け条件の言い換え操作変数変換して扱いやすい同型な問題を見出す実験ほとんどのところで値が一定値に決まる対称戦略可視化テク:二次元平面上に可視化する赤色diff ジグザグ

やった！自力で解けたー！！！
メチャクチャ楽しい問題だった。

問題へのリンク

問題概要

キャンディの山が $N$ 個あって、それぞれ $a_1, a_2, \dots, a_N$ 個のキャンディが積まれている。先手と後手が交互に

キャンディが 1 個以上あるすべての山について、1 個ずつキャンディを取る
最も多くのキャンディが積まれている山について、その山のすべてのキャンディを取る

最後にキャンディを取った方が負けである (逆形)。双方最善を尽くしたときに先手と後手のどちらが勝つか？

制約

$1 \le N \le 10^{5}$
$1 \le a_i \le 10^{9}$

考えたこと

まずは実験をして

(偶数) は先手勝ち
(奇数) は後手勝ち
(1, 1 以上) は先手勝ち
(2, 2 以上) は後手勝ち
長方形の場合は、縦と横の長さの和が奇数なら先手勝ちで偶数なら後手勝ち

とか、そんなことを考えたりしていた。やがて思ったことは、それぞれの操作は下図のように「ヤング図形の縦・横を削る操作」に過ぎないということ。

これをさらに、グリッド上の点の移動とみなせば、左下のマスから出発して、

列のを削るのは、横に 1 マス移動
行のを削るのは、縦に 1 マス移動

とみなせる。そして移動できなくなったら負け (いつの間にか、逆形ではなくなった) ということになる。

さらに

なんかすごく考えやすくなった気がするのでこの調子で行く。最終的には下図の赤マスのどこかで終わることになる。それぞれのマスまで何手で行けるかは決まっているので、そのパリティが大問題になる。

ここで着目したいのは「結局は斜め 45 度方向にジグザグに進むような流れになるのでは」ということ。もし先手にとって斜め 45 度方向にいい感じのマスがあったら、後手はそれを阻止したいが先手がそれを引き戻すことで斜め 45 度方向に概ね進む。先手と後手を入れ替えても同様のことが言える。そうすると斜め 45 度方向付近がどうなっているかを丁寧に考えれば解けそうである。

詰め

以下のことが言えた:

後手は、好きであれば必ず $(x, x)$ なマスに行くことができる
先手は、好きであれば必ず $(x, x+1), (x+1, x)$ なマスに行くことができる

これを利用して詰める。

赤マスが 1 箇所しかない場合

そのパリティのみで決まる (偶数なら後手勝ち、奇数なら先手勝ち)

赤マスのうちどれかについて x 座標と y 座標が等しいとき

後手がそこに行って、先手は動けなくなるので、後手勝ち

x 座標が最小の赤マスが x > y のとき

先手と後手がどうしようとそのマスで終わるので、そのマスのパリティで決まる

x 座標が最大の赤マスが x < y のとき

同様にそのマスのパリティで決まる

その他

赤マスを x 座標が小さい順にリストアップしていったとき、 $(x_{i}, y_{i}), (x_{i+1}, y_{i+1})$ であって

$x_{i}$ < $y_{i}$
$x_{i+1}$ > $y_{i+1}$

であるようなものが存在するはずである。 $(x_{i}, y_{i+1})$ (= $(a, b)$ とおく) に着目する。

a > b のとき

先手と後手がどうやっても、 $(x_{i}, y_{i})$ で終わるので、そのマスのパリティで決まる

a < b のとき

同様に $(x_{i+1}, y_{i+1})$ のパリティで決まる

a = b のとき

最後に残ったパターンで、このときは先手がやや有利である。先手側に主導権があって $(x_{i}, y_{i})$ と $(x_{i+1}, y_{i+1})$ のどちらで終わりたいかを選べる。どちらかが奇数なら先手勝ち、どちらも偶数なら後手勝ち

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using pll = pair<long long,long long>;

bool isodd(const pll &p) { return (p.first + p.second) & 1; }
bool solve(vector<long long> &a) {
    int N = (int)a.size();
    sort(a.begin(), a.end(), greater<long long>());

    long long x = 0, y = a[0];
    vector<pll> ps;
    for (int i = 0; i < N; ++i) {
        if (a[i] != y) ps.push_back(pll(i-1, y)), y = a[i];
    }
    ps.push_back(pll(N-1, a[N-1]));
    if (ps.size() == 1) return isodd(ps[0]);
    for (auto p : ps) if (p.first == p.second) return false;
    
    for (int i = 0; i + 1 < ps.size(); ++i) {
        if (ps[i].first < ps[i].second && ps[i+1].first > ps[i+1].second) {
            if (ps[i].first < ps[i+1].second) return isodd(ps[i+1]);
            else if (ps[i].first > ps[i+1].second) return isodd(ps[i]);
            else return isodd(ps[i]) || isodd(ps[i+1]);
        }
    }
    if (ps[0].first > ps[0].second) return isodd(ps[0]);
    else return isodd(ps.back());
}

int main() {
    int N;
    while (cin >> N) {
        vector<long long> a(N);
        for (int i = 0; i < N; ++i) cin >> a[i], --a[i];

        if (solve(a)) cout << "First" << endl;
        else cout << "Second" << endl;
    }
}

解説を見て

僕は上記のような場合分けを頑張ったけど、もう少し統一的にできる模様。。。

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます