C++で要素を並べ替えて回文を作れる部分配列の個数を求める方法

問題概要

整数要素からなる配列が与えられ、その配列から切り出せる部分配列のうち、要素を並べ替えることで回文（パリンドローム）を構成できるものの個数を求めるのが課題です。回文とは、先頭から読んでも末尾から読んでも同じ順序になる並びのことを指します。

ここで重要なのは、ある並びが回文にできる条件が「奇数回出現する要素の種類が高々1つ」であるという点です。この性質を利用すると、各要素の出現回数の偶奇をビットフラグとして管理し、XORで更新することで効率よく判定できます。

入力例1

入力 − int arr[] = { 3, 3, 1, 4, 2, 1, 5 }

出力 − 要素を並べ替えて回文を形成できる部分配列の個数 − 9

説明 − 条件を満たす部分配列は、{3}, {3}, {1}, {4}, {2}, {1}, {5}, {1, 2, 1} および {1, 3, 1} の9つです。したがって、合計個数は9となります。

入力例2

入力 − int arr[] = { 2, 5, 5, 2, 1 }

出力 − 要素を並べ替えて回文を形成できる部分配列の個数 − 8

説明 − 条件を満たす部分配列は、{2}, {5}, {5}, {2}, {1}, {5, 2, 5}, {2, 5, 2}, {2, 5, 5, 2} の8つです。したがって、合計個数は8となります。

プログラムで用いるアプローチ

• 整数要素の配列を入力として受け取り、配列のサイズを計算したうえで、後続の処理を行う関数にデータを渡します。

• 回文となる部分配列の個数を格納するための一時変数 count を宣言します。

• 0 から配列のサイズまでの FOR ループを開始します。

• ループの内側では long long 型の変数を宣言し、1LL << arr[j] の値を設定します。そのうえで、temp を temp ^ val として更新していきます。

• true または false を返すチェック関数を呼び出し、その結果を boolean 型の変数に格納します。

• temp が 0LL である、または ch が true である場合は、count を 1 増やします。

• count を返します。

• 結果を出力します。

コード例

#include <bits/stdc++.h>
using namespace std;
bool check(long long temp){
    return !(temp & (temp - 1LL));
}
int palindromes_rearrange(int arr[], int size){
    int count = 0;
    for (int i = 0; i < size; i++){
        long long temp = 0LL;
        for (int j = i; j < size; j++){
            long long val = 1LL << arr[j];
            temp = temp ^ val;
            bool ch = check(temp);
            if (temp == 0LL || ch){
                count++;
            }
        }
    }
    return count;
}
int main(){
    int arr[] = { 3, 3, 1, 4, 2, 1, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"Count of sub-arrays whose elements can be re-arranged to form palindromes are:\n"<<palindromes_rearrange(arr, size);
    return 0;
}

ポイント解説

関数 check() では「temp & (temp - 1)」が 0 になるかどうかを調べています。これは、ビットが1本だけ立っている（＝2のべき乗である）場合に真となる定番のビット演算テクニックです。temp が 0、つまりすべての要素が偶数回出現している場合、または奇数回出現する要素が1種類だけの場合に、その部分配列は回文へ並べ替え可能と判断できます。

出力

上記のコードを実行すると、次のような出力が得られます −

Count of sub-arrays whose elements can be re-arranged to form palindromes are: 9