Project Euler - Problem 491
Double pandigital number divisible by 11
0から9の数字をちょうど2回使った(先行ゼロのない)正整数をダブルパンデジタル数と呼ぼう. 例えば, 40561817703823564929 はそのような数の一つである.
11で割り切れるダブルパンデジタル数はいくつあるか?
(日本語訳より)
11で割り切れるダブルパンデジタル数はいくつあるか?
(日本語訳より)
Unsolved の中で最も difficulty が低かった問題.
11 の倍数の判定方法は 1 つおきに桁数字を取った和の差が 11 の倍数かどうかを調べればいい.例えば
N = 40561817703823564929
4 + 5 + 1 + 1 + 7 + 3 + 2 + 5 + 4 + 2 = 34
0 + 6 + 8 + 7 + 0 + 8 + 3 + 6 + 9 + 9 = 56
34 - 56 = -22 ≡ 0 ( mod 11 )
なので N は 11 の倍数.
方針としては,
- ans = 0 とする.
- 集合 A = { 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9 } を要素数の等しい 2 つのグループ L と R に分ける全ての組合せを列挙する.
- sum(L) - sum(R) ≡ 0 ( mod 11 ) であるような組合せに対して,
- L の no leading zero である順列 perm_l と R の順列 perm_r の積 perm_l * perm_r を ans に加算する.
色付けしたように,L は N の先頭から 1 つおきに数字を取った集合,R はその残りの集合に対応する.
これをプログラムに落とし込めばいい.
組合せの列挙に関しては,配列
a[20] = { 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9 }
を用意して next_combination 関数 *1 を使う.
next_combination(a, a + 10, a + 20) が false になるまでループを回せば全ての組合せが得られる.
区間 l = [a, a + 10) には配列 a から 10 要素選ぶ組合せが辞書式昇順に格納され,区間 r = [a + 10, a + 20) にはその残りが辞書式昇順に格納される.
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <climits> #include <cmath> #include <string> #include <vector> #include <algorithm> #include <queue> #include <map> #include <functional> #include <set> #include <numeric> #include <stack> #include <utility> #include <time.h> #include <iterator> //#include "util.h" using namespace std; typedef unsigned uint; typedef long long lint; typedef unsigned long long ulint; //呪文 template <typename _KTy, typename _Ty> ostream& operator << (ostream& ostr, const pair<_KTy, _Ty>& m) { cout << "{" << m.first << ", " << m.second << "}"; return ostr; } template <typename _KTy, typename _Ty> ostream& operator << (ostream& ostr, const map<_KTy, _Ty>& m) { if (m.empty()) { cout << "{ }"; return ostr; } cout << "{" << *m.begin(); for (auto itr = ++m.begin(); itr != m.end(); itr++) { cout << ", " << *itr; } cout << "}"; return ostr; } template <typename _Ty> ostream& operator << (ostream& ostr, const vector<_Ty>& v) { if (v.empty()) { cout << "{ }"; return ostr; } cout << "{" << v.front(); for (auto itr = ++v.begin(); itr != v.end(); itr++) { cout << ", " << *itr; } cout << "}"; return ostr; } template <typename _Ty> ostream& operator << (ostream& ostr, const set<_Ty>& s) { if (s.empty()) { cout << "{ }"; return ostr; } cout << "{" << *(s.begin()); for (auto itr = ++s.begin(); itr != s.end(); itr++) { cout << ", " << *itr; } cout << "}"; return ostr; } //template <typename T> void print(T* v, int N) { if (N == 0) cout << "{ }"; cout << "{" << v[0]; for (int p = 1; p < N; p++) cout << ", " << v[p]; cout << "}"; } #define PI 3.14159265358979323846 #define EPS 1e-8 #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define all(x) (x).begin(), (x).end() // next_combination : http://yak-ex.blogspot.jp/2014/05/c-nextcombination.html namespace { // possible implementation introduced at http://en.cppreference.com/w/cpp/algorithm/rotate with slight modification to handle parted ranges template<typename FI> void parted_rotate(FI first1, FI last1, FI first2, FI last2) { if (first1 == last1 || first2 == last2) return; FI next = first2; while (first1 != next) { std::iter_swap(first1++, next++); if (first1 == last1) first1 = first2; if (next == last2) { next = first2; } else if (first1 == first2) { first2 = next; } } } template<typename BI> bool next_combination_imp(BI first1, BI last1, BI first2, BI last2) { if (first1 == last1 || first2 == last2) return false; auto target = last1; --target; auto last_elem = last2; --last_elem; // find right-most incrementable element: target while (target != first1 && !(*target < *last_elem)) --target; if (target == first1 && !(*target < *last_elem)) { parted_rotate(first1, last1, first2, last2); return false; } // find the next value to be incremented: *next auto next = first2; while (!(*target < *next)) ++next; std::iter_swap(target++, next++); parted_rotate(target, last1, next, last2); return true; } // INVARIANT: is_sorted(first, mid) && is_sorted(mid, last) template<typename BI> inline bool next_combination(BI first, BI mid, BI last) { return next_combination_imp(first, mid, mid, last); } // INVARIANT: is_sorted(first, mid) && is_sorted(mid, last) template<typename BI> inline bool prev_combination(BI first, BI mid, BI last) { return next_combination_imp(mid, last, first, mid); } } lint factorial(lint n) { if (n == 0) return 1; lint ret = 1; for (lint i = 1; i <= n; i++) ret *= i; return ret; } int main() { clock_t start, end; start = clock(); lint a[20] = { 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9 }; lint ans = 0; do { // [a, a + 10) と [a + 10, a + 20) を互い違いに並べて double pandigital number を生成する // このとき生成した double pandigital number が 11 の倍数となる条件は // sum( [a, a + 10) ) - sum( [a + 10, a + 20) ) が 11 の倍数となること lint sum_left = accumulate<lint*, lint>(a, a + 10, 0); lint sum_right = accumulate<lint*, lint>(a + 10, a + 20, 0); if (abs(sum_left - sum_right) % 11 != 0) continue; // 左側 10 個の数字の数 lint nl[10] = {}; // 右側 10 個の数字の数 lint nr[10] = {}; for (lint i = 0; i < 10; i++) { nl[a[i]]++; nr[a[i + 10]]++; } // 左側 (no leading zero) の順列 lint perm_left = 0; // 0 以外の数字を先頭に持ってきて,残りの数字を並べる for (lint i = 1; i < 10; i++) { // 数字 i がある if (nl[i] > 0) { // i を先頭にもってくる (並べるべき要素から除外する) nl[i]--; // 9! = 先頭以外を並べる総数 lint fac9 = factorial(9); // 同じものを含む場合は割っていく for (lint j = 0; j < 10; j++) { fac9 /= factorial(nl[j]); } perm_left += fac9; // i を元に戻す nl[i]++; } } // 右側の順列 lint perm_right = factorial(10); // 同じものを含む場合は割っていく for (lint j = 0; j < 10; j++) { perm_right /= factorial(nr[j]); } ans += perm_left * perm_right; } while (next_combination(a, a + 10, a + 20)); cout << ans << endl; end = clock(); printf("%f sec.\n", double(end - start) / CLOCKS_PER_SEC); return 0; }
2 msec くらい.