B – 123 Triangle 解説 (AtCoder Grand Contest 043)

2020年3月23日AtCoder二項係数,Lucasの定理,偶奇性,パスカルの三角形,差の絶対値

問題へのリンク

問題概要

1,2,3 で構成された整数列 \(a_1 a_2 a_3 \cdots a_N\) が与えられ、\(x_{i,j}\) を以下のように再帰的に定義する。

  • \(x_{1,j} := a_j\)  \((1 \leq j \leq N)\)
  • \(x_{i,j} := | x_{i-1,j} – x_{i-1,j+1} |\)  \((2 \leq i \leq N\) かつ \(1 \leq j \leq N+1-i)\)

\(x_{N,1}\) を求めよ。

制約

  • \(2 \leq N \leq 10^6\)

考え方

問題設定から分かること

「奇数(特に 3)」や「差の絶対値(abs(x-y))」などが問題設定にある時は、「偶奇性」に注目すると良いことがあります。それを中心に考えてみましょう。

特に「差の絶対値」を考えるときは、

\(|x-y| \equiv x \oplus y \equiv x + y ~(mod ~ 2)\)

が成立することを頭に入れておくと良いです。

制約は \(2 \leq N \leq 10^6\) なので、単純に計算するのでは難しいです。ほぼ O(N) で解くことが必要でしょう。

実験して分かること

まず、いくつか実験してみると以下の事実が分かります

  • 実際に計算してみると三角形のようなものができる
  • 最初の差(\(x_{2,j}\)の部分)を計算すると、それ以降は「0, 1, 2」だけになる

最初に与えられた数を全て -1 しても、結果は変わりません。以後は、登場する数を「0, 1, 2」のみにして、考えやすくすることにします。( -1 するのは本質的ではないので、かわりに「1段計算したものを最初に与えられたとする」というようにしても良いです。)

また、もう少し考えてみると

  • はじめに 1 があったら答えが 2 になることはない

ということも分かります。これの証明は帰納的にできます。

偶奇性を考える

偶奇性で考えるというのは、言い換えれば「パリティを見る」・「mod 2 で考える」ということです。

登場する数字は「0, 1, 2」でしたが、偶奇性を考慮すると以下の事実が分かります。

  • 偶奇で考えると 0 と 2 を同一視することができる(0 と 1 しかない)
  • \(|x-y| \equiv x \oplus y \equiv x + y ~(mod ~ 2)\)  が成立する

これを頭に入れた状態で、再び実験をしてみると、

  • 上2つの数を、「差の絶対値 = XOR = 足し算」して下の数 1 つを作る

というようにして三角形を構成していることが分かり、特に足し算と考えると「(mod 2 で考えた)パスカルの三角形の一部」が見えてきます。

答えが 1 になる場合について考える

0 と 2 は同一視したままなので、「答えが 1 になる場合」と「答えが 0 か 2 になる場合」を先に考えてみましょう。

パスカルの三角形と見れば、はじめに登場する 1 が左から \(i\) 番目にあるとき、\(x_{N,1}\) に \(_{N-1}\mathrm{C}_{i}\) だけ影響することになります。

全ての 1 について \(x_{N,1}\) に寄与する数を調べれば、

  • \(x_{N,1}\) に 1 が寄与する数(\(_{N-1}\mathrm{C}_{i}\) の合計)が奇数なら答えも奇数で 1
  • \(x_{N,1}\) に 1 が寄与する数(\(_{N-1}\mathrm{C}_{i}\) の合計)が偶数なら答えも偶数で 0 か 2

ということになります。

最初に 1 が含まれるかどうかで場合分け

「はじめに 1 があったら答えが 2 になることはない」ということから、

  • 最初に 1 が含まれていれば
    • \(x_{N,1}\) に 1 が寄与する数が奇数なら答えも奇数で 1
    • \(x_{N,1}\) に 1 が寄与する数が偶数なら答えも偶数で 0
  • 最初に 1 が含まれていなければ答えは 0 か 2

ということがわかります。

最初が 0 と 2 だけから構成されている場合で実験してみると、

  • 2 と 1 を同一視しても変わらない(同様に \(x_{N,1}\) に 2 が寄与する数の偶奇で答えが決まる)

ということが分かります。つまり、最初に 1 が含まれている場合と同様にして答えを求めることが可能です。

解法

  • 最初に 1 が含まれている時
    • \(x_{N,1}\) に 1 が寄与する数(\(_{N-1}\mathrm{C}_{i}\) の合計)が奇数なら答えは 1
    • \(x_{N,1}\) に 1 が寄与する数(\(_{N-1}\mathrm{C}_{i}\) の合計)が偶数なら答えは 0
  • 最初に 1 が含まれている時
    • \(x_{N,1}\) に 2 が寄与する数(\(_{N-1}\mathrm{C}_{i}\) の合計)が奇数なら答えは 2
    • \(x_{N,1}\) に 2 が寄与する数(\(_{N-1}\mathrm{C}_{i}\) の合計)が偶数なら答えは 0

とすれば良いです。\(_{N-1}\mathrm{C}_{i}\) の値は mod 2 での値のみを見れば良いので、Lucas の定理や (N-1)&i == i で判定ができます。(参考:二項係数(nCk)の偶奇判定のアルゴリズム

C++ での実装例

#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
using namespace std;

int N;
string S;

int main() {
    cin >> N;
    cin >> S;
    vector<int> a(N);
    vector<int> cnt(3);
    for (int i = 0; i < N; i++) {
        a[i] = (int)(S[i] - '1');
        cnt[a[i]]++;
    }

    if (cnt[1] > 0) {  // 1 が存在する時
        bool is_odd = 0;
        for (int i = 0; i < N; i++) {
            if (a[i] == 1) {
                is_odd ^= (((N - 1) & i) == i);  // 1 が寄与する
            }
        }
        if (is_odd) {
            cout << 1 << endl;
        } else {
            cout << 0 << endl;
        }
    } else {  // 1 が存在しない時
        bool is_odd = 0;
        for (int i = 0; i < N; i++) {
            if (a[i] == 2) {
                is_odd ^= (((N - 1) & i) == i);
            }
        }
        if (is_odd) {
            cout << 2 << endl;
        } else {
            cout << 0 << endl;
        }
    }

    return 0;
}