POJ 3187 - Backward Digit Sums

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

概要

1 .. N の N 個の数字を並べて，パスカルの三角形のように隣接する数値を足していくと最後は1つの数値になる． N とその数値だけが与えられたとき，一番最初の N 個の数字の並び方を答える．

制約

• 1 <= N <= 10

解法

next_permutation で全探索． シミュレーション的に実際に足していくと遅いので，最初の並びが a[0] .. a[N-1] だったときに，最後の値は Σ(a[i] * c[N-1][i]) であることを利用して計算する(c は combination)．

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int comb[11][11];
 7 
 8 int sum(const vector<int>& a)
 9 {
10   const int N = a.size();
11   int s = 0;
12   for (int i = 0; i < N; i++) {
13     s += a[i] * comb[N-1][i];
14   }
15   return s;
16 }
17 
18 int main()
19 {
20   for (int i = 0; i <= 10; i++) {
21     comb[i][0] = 1;
22     comb[i][i] = 1;
23   }
24   for (int n = 1; n <= 10; n++) {
25     for (int k = 1; k < n; k++) {
26       comb[n][k] = comb[n-1][k] + comb[n-1][k-1];
27     }
28   }
29 
30   int N, S;
31   cin >> N >> S;
32   vector<int> a(N);
33   for (int i = 0; i < N; i++) {
34     a[i] = i+1;
35   }
36 
37   do {
38     if (sum(a) == S) {
39       for (int i = 0; i < N; i++) {
40         if (i != 0) {
41           cout << ' ';
42         }
43         cout << a[i];
44       }
45       cout << endl;
46       break;
47     }
48   } while (next_permutation(a.begin(), a.end()));
49   return 0;
50 }