Problem38 パンデジタル倍数

問題

192 に 1, 2, 3 を掛けてみよう.

192 × 1 = 192
192 × 2 = 384
192 × 3 = 576

積を連結することで1から9の パンデジタル数 192384576 が得られる.
192384576 を 192 と (1,2,3) の連結積と呼ぶ.

同じようにして, 9 を 1,2,3,4,5 と掛け連結することでパンデジタル数 918273645が得られる.
これは 9 と (1,2,3,4,5) との連結積である.

整数と (1,2,...,n) (n > 1) との連結積として得られる9桁のパンデジタル数の中で
最大のものはいくつか?

ソース

#include <vector>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <valarray>
#include <Windows.h>

std::vector<int> RenketuSekiVect;

void CheckRenketuSeki(int pTarget);
bool IsPandigital(int pTarget);

void main()
{
    //5桁の数に1を掛けると5桁以上の数になる。
    //5桁の数に2を掛けると5桁以上の数になる。
    //これらを連結すると10桁以上なので、4桁の最大値である9999までをチェック
    for (int I = 1; I <= 9999; I++) {
        CheckRenketuSeki(I);
    }

    printf("Answer=%d\n",*std::max_element(RenketuSekiVect.begin(),RenketuSekiVect.end()));
}

void CheckRenketuSeki(int pTarget)
{
    std::string wkStr;
    for (int I = 1; I <= 9; I++) {
        char wkCharArr[100];wsprintf(wkCharArr,"%d",pTarget * I);
        wkStr += wkCharArr;
        if (wkStr.length() == 9){
            int wkInt = atoi(wkStr.c_str());
            if (IsPandigital(wkInt)){
                RenketuSekiVect.push_back(wkInt);
                return;
            }
        }
        if (wkStr.length() > 9) return;
    }
}

bool IsPandigital(int pTarget)
{
    std::valarray<bool> CheckNumArr(false,10);
    do {
        int wk = pTarget % 10;
        if (wk == 0) return false;
        if (CheckNumArr[wk]) return false;
        CheckNumArr[wk] = true;
    } while ((pTarget /= 10) > 0);

    for(int I=1;I<=(int)CheckNumArr.size()-1;I++){
        if (CheckNumArr[I]==false) return false;
    }
    return true;
}

実行結果

Answer=932718654

解説

*std::max_element(RenketuSekiVect.begin(),RenketuSekiVect.end())
で最大値を求めてます。
(最大値の要素を指すイテレータの指す値を求めれば、それが最大値のため)