POJ 3139 - Balancing the Scale

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

概要

16個の相異なる整数 \(a_1 \cdots a_16\) が与えられる。 これをそれぞれ1回ずつ使って

を満たすような式はいくつあるか答える。

制約

解法

2つの式は同じなので、いわゆる半分全列挙のイメージで、8つの整数の使い方のビットパターン s に対して \(4 x_1 + 3 x_2 + 2 x_3 + x_4 = x_5 + 2 x_6 + 3 x_7 + 4 x_8\) を満たすようなものが x[s] 通りある、ということがわかれば、 すべてのビットパターン (高々 \(2 ^ {16}\) 通りしかない) について x[s] * x[s の反転] の総和をとれば答えになる。

しかし、8つの整数の使い方は単純に列挙すると \(16 \cdot 15 \cdots 9 = 518918400\) 通りもあるので厳しい。 そこで式の両辺が対称的であり、制約から各辺の和が高々 10240 しかないことから、

v[val] = 16個の整数から4つ選んで並べたときの和が val になるようなビットパターンの配列

というのを計算し、各 v[val] から2つ選んだもののうち、ビットパターンが重なっていないものが求める8つの整数の選び方である、というように求める。 この方法の計算量はよくわかってない。 10240 のループの中に二重ループがあるけどそんなに回らない、つまりそんなに総和は被らないんじゃないかと思う。

 1 #include <iostream>
 2 #include <vector>
 3 #include <map>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 int main()
 8 {
 9   int n;
10   for (int Ti = 1; cin >> n && n != 0; Ti++) {
11     int a[16];
12     a[0] = n;
13     int ix[16];
14     ix[0] = 0;
15     for (int i = 1; i < 16; i++) {
16       cin >> a[i];
17       ix[i] = i;
18     }
19 
20     vector<vector<unsigned> > v(10240);
21     do {
22       int val = 0;
23       unsigned s = 0;
24       for (int i = 0; i < 4; i++) {
25         val += (i+1) * a[ix[i]];
26         s |= 1<<(ix[i]);
27       }
28       v[val].push_back(s);
29       reverse(ix+4, ix+16);
30     } while (next_permutation(ix, ix+16));
31 
32     static const int M = 1<<16;
33     vector<long long> x(M);
34     for (int i = 0; i < 10240; i++) {
35       const vector<unsigned>& w = v[i];
36       const int N = w.size();
37       for (int j = 0; j < N; j++) {
38         for (int k = j+1; k < N; k++) {
39           if ((w[j] & w[k]) == 0) {
40             ++x[w[j] | w[k]];
41           }
42         }
43       }
44     }
45 
46     long long ans = 0LL;
47     for (int i = 0; i < M; i++) {
48       ans += x[i] * x[i ^ (M-1)];
49     }
50     cout << "Case " << Ti << ": " << ans/2 << endl;
51   }
52   return 0;
53 }
poj/3139.cc