POJ 2011 - Primary X-Subfactor Series

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

概要

ある数 n に対して，n の約数であり部分列でもある1以上の整数を subfactor という．

2, 13, 801, 882, 1324 はどれも 8013824 の部分列であるが，以下は部分列ではない．

• 214 (順番は入れ替えられない)
• 8334 (元の数字より出現を増やしてはいけない)
• 8013824 (少なくとも1つの数字を消さなければならない)
• 01 (leading zero は許されていない)

n に対する x-subfactor series は n[1], ..., n[k] という整数の減少数列で，

• n[1] = n
• k >= 1
• for all 1 <= i < k, n[i+1] は n[i] のある subfactor に出現する数字を消して leading zero も消した数

を満たすものであり，x-subfactor は x-subfactor series の x 番目の数である．

例えば n = 2004 のとき，以下の2つの異なる x-subfactor series をもつ．

• 2004 → (subfactor として 2 を採用する) → 4
• 2004 → (subfactor として 4 を採用する) → 200 → (subfactor として 2 を採用する) → 0
• 2004 → (subfactor として 4 を採用する) → 200 → (subfactor として 20 を採用する) → 0

primary x-subfactor series は x-subfactor series の中で最も長いものである．もし複数存在する場合，2番目の数が最も小さいものを選び，もしそれも複数存在する場合は3番目の数が最も小さいものを…と選ぶことにする．

与えられた数の primary x-subfactor series を答える．

解法

メモ化しつつ，再帰的に primary x-subfactor series を計算する．

 1 #include <iostream>
 2 #include <vector>
 3 #include <map>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 map<int,pair<int,int> > cache;
 8 
 9 pair<int,int> solve(int start)
10 {
11   if (cache.count(start)) {
12     return cache[start];
13   }
14 
15   vector<int> v;
16   for (int i = start; i > 0; i /= 10) {
17     v.push_back(i % 10);
18   }
19   const int N = v.size();
20 
21   pair<int,int> ans = make_pair(0, -1);
22   for (int s = 1; s < (1<<N)-1; s++) {
23     int n = 0;
24     for (int i = 0; i < N; i++) {
25       if (s & (1<<i)) {
26         if (n == 0 && v[N-1-i] == 0) {
27           // leading zero
28           goto NEXT;
29         } else {
30           n = 10*n + v[N-1-i];
31         }
32       }
33     }
34     if (n > 1 && start % n == 0) {
35       int t = 0;
36       for (int i = 0; i < N; i++) {
37         if ((s & (1<<i)) == 0) {
38           t = 10*t + v[N-1-i];
39         }
40       }
41       const pair<int,int> r = solve(t);
42       if (ans.first < r.first+1 || (ans.first == r.first+1 && ans.second > t)) {
43         ans.first = r.first+1;
44         ans.second = t;
45         ans.second = t;
46       }
47     }
48 NEXT:
49     ;
50   }
51   cache[start] = ans;
52   return ans;
53 }
54 
55 int main()
56 {
57   int n;
58   while (cin >> n && n != 0) {
59     pair<int,int> ans = solve(n);
60     cout << n;
61     while (ans.second != -1) {
62       cout << ' ' << ans.second;
63       ans = cache[ans.second];
64     }
65     cout << endl;
66   }
67   return 0;
68 }