絶滅

どうでもいい

Project Euler - Problem 491

Double pandigital number divisible by 11

Problem 491 (日本語訳)

0から9の数字をちょうど2回使った(先行ゼロのない)正整数をダブルパンデジタル数と呼ぼう. 例えば, 40561817703823564929 はそのような数の一つである.

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 の倍数.



方針としては,

  1. ans = 0 とする.
  2. 集合 A = { 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9 } を要素数の等しい 2 つのグループ LR に分ける全ての組合せを列挙する.
  3. sum(L) - sum(R) ≡ 0 ( mod 11 ) であるような組合せに対して,
  4. L の no leading zero である順列 perm_lR の順列 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 くらい.