STL にも next_permutation があった
Scheme の permutations-for-each が役に立つ - EAGLE 雑記 と書いたけど、実は STL にも permutation が得られる関数があった。
それで Problem 43 を再び解いてみたところ、一瞬で解けた。
Gauche が遅いのか C++ が速いのか俺の書き方が悪いのか。
#include <iostream> #include <algorithm> int main(void) { unsigned d[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; unsigned len = 10; unsigned long long sum = 0; do { if ((d[1]*100 + d[2]*10 + d[3]) % 2 == 0 && (d[2]*100 + d[3]*10 + d[4]) % 3 == 0 && (d[3]*100 + d[4]*10 + d[5]) % 5 == 0 && (d[4]*100 + d[5]*10 + d[6]) % 7 == 0 && (d[5]*100 + d[6]*10 + d[7]) % 11 == 0 && (d[6]*100 + d[7]*10 + d[8]) % 13 == 0 && (d[7]*100 + d[8]*10 + d[9]) % 17 == 0) { unsigned long long p = 1; for (unsigned i = 0; i < len; i++) { sum += d[len-i-1]*p; p *= 10; } } } while (std::next_permutation(d, d+len)); std::cout << sum << std::endl; return 0; }