Project Euler - Problem 170

みなさんがＳＥＸしている間にプロジェクトオイラーをやりました

Find the largest 0 to 9 pandigital that can be formed by concatenating products

6を1273と9854に掛けると,

6 × 1273 = 7638
6 × 9854 = 59124 となる.

これらの積をつなげることで, 1から9を網羅するパンデジタル数, 763859124を得る. 763859124を"6と(1273,9854)の連結された積"と呼ぶことにする. 元の数をつなげた 612739854も1から9を網羅する数であることに注意.

同じことが0から9を網羅する数にたいしてもできる.

元の数をつなげた数も0から9を網羅する数となるような, ある整数と二つ以上の整数の連結された積が0から9を網羅する数の最大値を求めよ.

(日本語訳より)

適当に考えて立った方針が 2 つ

順方向 : pandigital 数 612739854 から (6, (1273, 9854)) のような組を生成 → 積が pandigital か確認
逆方向 : pandigital 数 763859124 を (7638, 59124) 等に分解 → 公約数で割って (6, (1273, 9854)) のような組を生成し pandigital か確認

人々の解説を見るに 2 番目の方法が多かったが (最大値を求める問題なので 9876543210 から prev_permutation で回したりしている　かしこい)，自分はかしこくないので前者で 10! の総当りを (適度に枝刈りしつつ) やった．

具体的には配列

v = { 1, 0, 2, 3, 4, 5, 6, 7, 8, 9 }

からスタートして next_permutation を回す．

各々に対して先頭から d (1 ≦ d ≦ 8) 桁とってきて base とする．
これは (6, (1273, 9854)) などの 6 の部分に該当する． *1
たとえば v = { 1, 0, 2, 3, 4, 5, 6, 7, 8, 9 } で d = 4 なら base = 1023．

残った部分は v = { 1, 0, 2, 3, 4, 5, 6, 7, 8, 9 } となるが，ここからゴチャッと再帰を書いて 2 つ以上の組に分けて，適当に掛けて連結して一番でかいの見つけてきて終わり．(適当)

汚いコードでも食らってください．

#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()


lint ans = 0;

int vtoi(lint* v, int begin, int end) {
    int ret = 0;
    for (int i = begin; i < end; i++) {
        ret *= 10;
        ret += v[i];
    }
    return ret;
}

// -1 : error, 0 : ok, 1 : pandigital
int pandigital(string& cp) {
    if (cp.empty()) return 0;
    if (cp[0] == '0' || cp.size() > 10) return -1;

    bool d[10] = {};
    for (int i = 0; i < cp.size(); i++) {
        int index = int(cp[i] - '0');
        if (d[index]) return -1;
        d[index] = true;
    }

    return (cp.size() == 10 ? 1 : 0);
}

// cp: concatenating product
// width: 次の rec では width 以上とる
void rec(string& cp, lint* v, lint base, int pos, int width) {
    if (pos != 10 && v[pos] == 0) return;
    int pd = pandigital(cp);
    if (pd == -1) return;
    if (pd == 1 && pos == 10) {
        ans = max(ans, stoll(cp));
        return;
    }

    // 残りの半分以下をとってくる
    for (int i = width; i <= (10 - pos) / 2; i++) {
        int x = vtoi(v, pos, pos + i);
        int sz = cp.size();
        string sstr = to_string(x * base);
        if (cp[0] < sstr[0]) {
            cp = sstr + cp;
            rec(cp, v, base, pos + i, i);
            cp.erase(0, sstr.size());
        }
        else if (sstr[0] < cp[0]) {
            cp += sstr;
            rec(cp, v, base, pos + i, i);
            cp.erase(sz);
        }
    }

    // 全部とってくる
    if(!cp.empty()) {
        int x = vtoi(v, pos, 10);
        int sz = cp.size();
        string sstr = to_string(x * base);
        if (cp[0] < sstr[0]) {
            cp = sstr + cp;
            rec(cp, v, base, 10, -1);
            cp.erase(0, sstr.size());
        }
        else if (sstr[0] < cp[0]) {
            cp += sstr;
            rec(cp, v, base, 10, -1);
            cp.erase(sz);
        }
    }
}

void solve(lint* v) {
    lint base = 0;
    // base に何桁使うか
    for (int digits = 0; digits < 8; digits++) {
        base *= 10;
        base += v[digits];

        string cp;
        rec(cp, v, base, digits + 1, 1);
    }
}

int main() {

    clock_t start, end;
    start = clock();

    lint v[] = { 1, 0, 2, 3, 4, 5, 6, 7, 8, 9 };
    
    do {
        solve(v);
    } while (next_permutation(v, v + 10));

    cout << ans << endl;

    end = clock();
    printf("%f sec.\n", double(end - start) / CLOCKS_PER_SEC);
    return 0;
}

だいたい 13 秒くらい．*2

*1:ここはちゃんと考察すると d = 2 らしい

*2:VC++ のビルドを Debug から Release モードにしたら 10 倍くらい速くなって，今までヤバい縛りプレイをしていたことが分かった．

絶滅

どうでもいい

Project Euler - Problem 170

Find the largest 0 to 9 pandigital that can be formed by concatenating products