POJ 3842 - An Industrial Spy

http://poj.org/problem?id=3842

概要

与えられた文字列の一部(全部でもいい)を好きな順に並べてできる数字のうち，素数はいくつあるか答える．

制約

• 文字列の長さ <= 7
• テストケースの数 <= 200

解法

10^7 未満のエラトステネスの篩を作っておいて，各文字列に関して全探索 + unique．

unique が必要無いようにうまく next_permutation 的なものを自分で実装すると高速に通るらしい．

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8   static const int N = 10000000;
 9   static bool sieve[N];
10   sieve[0] = sieve[1] = true;
11   for (int i = 2; i < N; i++) {
12     if (!sieve[i]) {
13       for (int j = i+i; j < N; j += i) {
14         sieve[j] = true;
15       }
16     }
17   }
18 
19   int C;
20   cin >> C;
21   while (C-- > 0) {
22     string s;
23     cin >> s;
24     const int M = s.size();
25     vector<int> v;
26     for (int u = 1; u < (1<<M); u++) {
27       string t;
28       for (int i = 0; i < M; i++) {
29         if (u & (1<<i)) {
30           t += s[i];
31         }
32       }
33       sort(t.begin(), t.end());
34       do {
35         int n = 0;
36         for (string::const_iterator it(t.begin()); it != t.end(); ++it) {
37           n = 10*n + *it-'0';
38         }
39         if (!sieve[n]) {
40           v.push_back(n);
41         }
42       } while (next_permutation(t.begin(), t.end()));
43     }
44     sort(v.begin(), v.end());
45     const vector<int>::iterator it = unique(v.begin(), v.end());
46     cout << distance(v.begin(), it) << endl;
47   }
48   return 0;
49 }