2020-03-22

AtCoder AGC 043 B - 123 Triangle (青色, 700 点)

AtCoder AtCoder700点 AGC-B パリティ不変量二項係数個別の要素の動きに注目する場合分け絶対値やminを扱う問題倍数判定や九去法数列経路数に帰着係数を考える数学的帰納法に基づく考察 0と1と2の問題青色diff ピラミッド操作後の結果を求める問題操作:隣接要素の和や差をとる

答えが 0, 1, 2 の三通りしかないとなれば、mod で絞るのをやりたくなる！受験数学では定番のテクニックだ！！！

問題へのリンク

問題概要

長さ $N$ の、1, 2, 3 のみからなる数列が与えられる。この数列に対して、

隣接する要素の差を書き出す

という操作を、数列の長さが 1 になるまで繰り返す。最後に残る値を答えよ。

制約

$2 \le N \le 10^{6}$

考えたこと

ひとまず、1 回は操作してしまう。そうすると数列が 0, 1, 2 のみになる。そこから後はずっと 0, 1, 2 しか登場しない世界となる。まともにシミュレーションしたら $O(N^{2})$ かかってしまう。何かしたら省略できるからくりがあるはず。こういうので今まで経験したのは

パリティで絞れる
何かしら単調性があって二分探索できる

といったあたり。ザッと手元で実験した感じだと、なんか構造がある気がしない。というわけで、mod で絞るのを決行することに！

そして今回、絶対値制約が mod. 2 で考えろとささやいているようにも見える。なぜなら

$|a - b| \equiv a + b \pmod 2$

が成立するからだ。mod. 2 であれば「足し算」も「引き算」も一緒だというのが効いている。

$a - b \equiv a + b \pmod 2$
$b - a \equiv a + b \pmod 2$

がともに成立するので、絶対値があろうとなかろうと関係ないのだ。この特質は mod. 2 でしか成り立たない。さて、ここから言えることは一つ。「mod. 2 で考えれば、少なくとも答えの偶奇は必ず特定できるはず」ということだ。これで 0 or 2 か、1 かのどちらかには絞ることができる。まずはそれを考えることにした。

さて、mod. 2 で考えたとき、最終結果は $a_{0}, a_{1}, \dots, a_{N-1}$ の線形結合で表せるはずだ。つまり

$x_{0} a_{0} + x_{1} a_{1} + \dots + x_{N-1} a_{N-1}$

という形になるはずなのだ。なのであとは係数 $x_{i}$ を求めればいいはずだ。こういう風に「係数を考えればいい」という考察はめちゃくちゃ良く見る。

そしてその係数は良く考えると簡単だ。今回のシミュレーションの構造は、パスカルの三角形そのものなので、二項係数になる。つまり

$C(N-1, 0) a_{0} + \dots + C(N-1, N-1) a_{N-1}$

となる。よって二項係数の偶奇がわかれば OK。

二項係数の偶奇

二項係数の偶奇が、シェルピンスキーのガスケットとよばれる構造を持っていることはよく知られている。

mathtrain.jp

このことの考察を深めるとリュカの定理というのに行き着く。

mathtrain.jp

しかしそんなことしなくても、 $C(n, r)$ の偶奇を調べたかったら単純に

$n!$ が 2 で何回割れるかを求めて、そこから
$r!$ が 2 で何回割れるのかを引いて、
$(n-r)!$ が 2 で何回割れるのかを引いて、

残った値が 1 以上かどうかで判定することができる。

0 or 2 になったときは...

さて、以上から最終結果が偶数か奇数かはわかった。奇数なら答えは 1 で確定する。偶数の場合は 0 か 2 かを絞らなければならない。

ここで、「2 になるためにはどういう条件が必要か」を考察することにしよう。最終結果が 2 になるように、数列を遡っていくイメージで手を動かしていくと、

最後の結果を 2 とすると、0 と 2 しか作れない

ということがわかってくる。そしてもう一つ。

初期数列に 1 が存在しないならば、途中で 1 が生えてくることが絶対にない

ということも見えて来る。それはそうで、初期数列に 1 がないということは、最初からすべて偶数なのだから、差をとっても偶数しか生まれないのだ。したがって、

最終結果が偶数で、初期数列に 1 がある：答えは 0
最終結果が偶数で、初期数列に 1 がない：もう少し考える

という状態になった。

初期数列に 0 と 2 しかないとき...

良く考えるとこれはもう、全体を 2 で割ってしまってよい。そうすると、

初期数列は 0 と 1 しかない
その差分も 0 と 1 しかない

という状態に落ち着く。この最終結果が 0 ならば、元の問題の答えも 0 で、1 ならば、元の問題の答えは 2 だ。

そして、2 で割ったバージョンで最終結果が 0 か 1 かを求める問題は、結局先ほどと同じように偶奇を求めればよい。

まとめ

パリティが奇数なら、答えは 1
パリティが偶数で、1 が含まれるなら、答えは 0
パリティが偶数で、1 が含まれないとき、全体を 2 で割って
- その状態でパリティが偶数なら、答えは 0
- その状態でパリティが奇数なら、答えは 2

計算量は $O(N)$ 。

#include <bits/stdc++.h>
using namespace std;

const int MAX = 1100000;
vector<long long> cnt; // cnt[n] := n! が 2 で何回割れるか
void pre() {
    cnt.assign(MAX, 0);
    for (int i = 1; i < MAX; ++i) {
        int j = i;
        int add = 0;
        while (j % 2 == 0) ++add, j /= 2;
        cnt[i] = cnt[i-1] + add;
    }
}

int solve(const string &S) {
    pre();
    vector<int> a;
    for (int i = 0; i + 1 < S.size(); ++i) {
        int x = S[i] - '0';
        int y = S[i+1] - '0';
        a.push_back(abs(x - y));
    }
    long long parity = 0;
    for (int i = 0; i < a.size(); ++i) {
        long long ex = cnt[a.size()-1] - cnt[i] - cnt[a.size()-i-1];
        if (ex > 0) continue;
        parity += a[i];
    }

    if (parity & 1) return 1;
    else {
        bool exist_one = false;
        for (int i = 0; i < a.size(); ++i) if (a[i] == 1) exist_one = true;
        if (exist_one) return 0;
        else {
            parity = 0;
            for (int i = 0; i < a.size(); ++i) {
                long long ex = cnt[a.size()-1] - cnt[i] - cnt[a.size()-i-1];
                if (ex > 0) continue;
                parity += a[i] / 2;
            }
            if (parity & 1) return 2;
            else return 0;
        }
    }
}

int main() {
    int N;
    string S;
    cin >> N >> S;
    cout << solve(S) << endl;
}

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

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