Project Euler 問題38（パンデジタル倍数）を解いてみる

Project Euler で紹介されている問題38を解いてみました。パンデジタル数について解くため、ライブラリで順列を使える C++ を利用して解きました。

Project Euler 問題38（パンデジタル倍数）

パンデジタル数の定義

問題32の問題文でパンデジタルを以下と定義しています。

n桁の数で、1からnまでのすべての数字をちょうど1回ずつ使うものをパンディジタル（pandigital）と呼ぶことにする。たとえば、5桁の数 15234 は1から5のパンディジタルである。

パンデジタルな数をパンデジタル数と呼びます。パンデジタル数は、0 を含む場合もあるようです。Wikipedeia の「パンデジタル数」の定義では、0 を含めています。この問題では、Project Euler の流儀に従います。

考察

問題文で、n > 1 としています。n = 1 の場合を認めると、9桁の数と (1) の連結積となり、明らかに 987654321 が最大となります。

問題文にもある 9 と (1,2,3,4,5) の連結積であるパンデジタル数 918273645 は、最大値の候補になります。このため、連結積であるパンデジタル数の一番左の桁は 9 とします。

最初の整数を2桁とします。連結積であるパンデジタル数の一番左の桁を 9 とすると、以下となり、パンデジタル数が9桁となりません。? は、数字1桁を表します。

9? → 18? → 27? → 残り1桁

最初の整数を3桁とします。こちらも2桁の場合と同じく、パンデジタル数の一番左の桁を 9 とすると、以下となり、パンデジタル数が9桁となりません。

9?? → 18?? → 残り2桁

最初の整数を4桁とします。この場合は、あり得ます。

9???? → 18??? （ちょうど9桁になる）

9から始まる4桁の数とそれに2を掛けた5桁を連結した9桁のパンデジタル数で最大のものを探します。もし見つからなければ、918273645 が最大となります。

解答例

順列を使うと楽に解くことができます。C では標準ライブラリで順列のサポートがありません。標準ライブラリで順列のサポートがあるC++を使って解きます。問題32では、順列を生成する next_permutataion を do-while と組みにして、1から9までのすべての順列を生成して解きました。

今回は、最大値を求めるため、ひとつ前の順列を生成する prev_permutataion を使います（28行目）。もし、この条件を満たすパンデジタル数が見つからなければ、918273645 を出力します（11行目）。

以下は、C++ のプログラムです。

#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

int main(void)
{
	int n[8] = {8, 7, 6, 5, 4, 3, 2, 1};

	int answer = 918273645;

	do {
		int num1 = 9;
		for (int i = 0; i < 3; ++i) {
			num1 = num1 * 10 + n[i];
		}
		int num2 = 0;
		for (int i = 3; i < 8; ++i) {
			num2 = num2 * 10 + n[i];
		}
		if (num1 * 2 == num2) {
			if (num1 * 100000 + num2 > answer) {
				answer = num1 * 100000 + num2;
				break;
			}
		}
	} while (prev_permutation(n, n + 8));

	printf("Problem038: %d\n", answer);

	return 0;
}

このプログラムでは、条件を満たす数が見つかれば、ループを break します。break しなければ、解答以外に 927318546 と 926718534 が条件を満たすことが分かります。

最後に

連結積の定義から最大値となるのは、4桁+5桁の場合に絞り込めました。このため、プログラムはすっきりと書けました。

引き続き、Project Euler の問題を紹介していきます。