Processing math: 2%

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++ での実装例

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#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;
}
#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; }
#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;
}