C++で制約条件付きの行列から最終的な値を効率的に求める方法

この記事では、1・2・3のいずれかの値で構成される数列をもとに、隣接要素の差の絶対値を繰り返し計算して最終的に残る値を求めるC++プログラムを紹介します。単純なシミュレーションではなく、二項係数の偶奇(パリティ)を利用した効率的な解法を解説します。

問題概要

1、2、または3のいずれかの値を持つN個の要素からなる数列Aがあるとします。これをもとに、次のように二次元配列Xを定義します。

• X[1][j] = A[j](ただし j は 1 以上 N 以下)
• X[i][j] = |X[i-1][j] − X[i-1][j+1]|(ただし i は 2 以上 N 以下、j は 1 以上 N+1−i 以下)

このとき、最終的に残る値 X[N][1] を求めることがゴールです。

具体例

たとえば入力が A = [1, 2, 3, 1] の場合、出力は 1 になります。計算の流れは以下の通りです。

X[1][1]〜X[1][4]: 1, 2, 3, 1
X[2][1], X[2][2], X[2][3]: |1−2| = 1, |2−3| = 1, |3−1| = 2
X[3][1], X[3][2]: |1−1| = 0, |1−2| = 1
X[4][1] = |0−1| = 1
したがって、答えは 1

解法のアプローチ

各段階で「隣接する2つの値の差の絶対値」を取る操作を繰り返すため、素直にシミュレーションするとO(N²)の計算量が必要になります。ここで注目すべきは値の偶奇(パリティ)です。差の絶対値 |a − b| の偶奇は a + b の偶奇と一致するため、二項係数の性質を利用すれば、最終的な値の偶奇を高速に判定できます。

具体的には、calc() 関数が二項係数 C(N−1, i) が奇数かどうかを、ビットシフトを用いてO(log N)で判定します(これはLucasの定理の考え方に基づいています)。最終結果に影響を与えるのは奇数となる位置に対応する要素だけであり、それらをXORで集計することで答えを導けます。

アルゴリズムの手順

1. calc(N, M) の定義: N、M、N−M のそれぞれを右シフトしながらカウンタに加減算を行い、最終的にカウンタが0なら1(該当する二項係数が奇数)、そうでなければ0を返します。
2. メイン処理では、まず隣接要素同士の差の絶対値を配列 arr に格納します。
3. 各差の値が0でない場合、その値が1かどうかでフラグ(hh、pd、ck)を分けて管理し、calc(n−1, i) の結果をXORで累積します。
4. 最後に pd XOR ck が非ゼロなら "1"、そうでなければ "0" を返します。

C++実装例

理解を深めるために、実際の実装を見てみましょう。

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

int calc(int N, int M) {
    int cnt = 0;
    for (int k = N; k; k >>= 1)
        cnt += k >> 1;
    for (int k = M; k; k >>= 1)
        cnt -= k >> 1;
    for (int k = N - M; k; k >>= 1)
        cnt -= k >> 1;
    return !cnt;
}

string solve(vector<int> A) {
    int n = A.size();
    vector<int> arr(n + 1);
    for (int i = 1; i < n; i++) {
        arr[i - 1] = abs(A[i] - A[i - 1]);
    }
    --n;
    bool hh = 1, pd = 0, ck = 0;
    for (int i = 0; i < n; i++)
        if (arr[i]) {
            if (arr[i] == 1)
                hh = 0, pd ^= calc(n - 1, i);
            else
                ck ^= calc(n - 1, i);
        }
    ck &= hh;
    if (pd ^ ck)
        return "1" + hh;
    return "0";
}

int main(){
    vector<int> A = { 1, 2, 3, 1 };
    cout << solve(A) << endl;
}

入力

{ 1, 2, 3, 1 }

出力

1

まとめ

本プログラムでは、「差の絶対値を繰り返し計算する」という一見単純な問題を、偶奇(パリティ)に着目した二項係数の判定へ帰着させることで、全段階のシミュレーションよりも大幅に効率よく最終値を求めています。数列の要素が1〜3に制限されている点こそが、この巧妙な手法を適用できる重要なポイントです。