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

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

AtCoder AGC 002 E - Candy Piles (1400 点)

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

問題へのリンク

問題概要

キャンディの山が  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 以上) は後手勝ち
  • 長方形の場合は、縦と横の長さの和が奇数なら先手勝ちで偶数なら後手勝ち

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

f:id:drken1215:20190406012134p:plain

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

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

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

さらに

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

f:id:drken1215:20190406012920p:plain

ここで着目したいのは「結局は斜め 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;
    }
}   

解説を見て

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