B – 123 Triangle 解説 (AtCoder Grand Contest 043)
問題概要
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;
}