POJ 1487 - Single-Player Games

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

概要

いくつかのラベル付きの部分木が与えられる。 部分木の葉ノードには、整数かラベルが付けられている。 整数はその葉ノードのスコアを表し、ラベルはその位置にそのラベルを持つ部分木が続くことを表している。

各部分木のルートから葉ノードに向かって遷移する。 どの子ノードにも等確率で遷移するとする。 このとき、得られるスコアの期待値を答える。 ただし、その部分木のルートから各葉ノードへ最終的に遷移する確率の合計が 1 にならない場合は「undefined」と答える。

制約

解法

前半は構文解析。S 式なので大したことはない。

後半は期待値に関する連立方程式を解く。 undefined となるのは任意の値をとれる変数、つまりガウスの消去法を行った後に対角成分が 0 になっているところの変数と、その変数に依存している変数である。

  1 #include <cstdio>
  2 #include <iostream>
  3 #include <sstream>
  4 #include <vector>
  5 #include <queue>
  6 #include <cmath>
  7 using namespace std;
  8 static const double EPS = 1e-6;
  9 
 10 bool is_zero(double x) { return fabs(x) < EPS; }
 11 
 12 bool gaussian_elimination(vector<vector<double> >& a, vector<double>& b)
 13 {
 14   const int N = a.size();
 15   const int M = a[0].size();
 16   const int K = min(N, M);
 17   vector<int> sigma(N);
 18   for (int i = 0; i < N; i++) {
 19     sigma[i] = i;
 20   }
 21 
 22   for (int i = 0; i < K; i++) {
 23     int p;
 24     for (p = i; is_zero(a[i][i]) && p < N; p++);
 25     if (p == N) {
 26       continue;
 27     }
 28     swap(a[i], a[p]);
 29     swap(b[i], b[p]);
 30     swap(sigma[i], sigma[p]);
 31     if (is_zero(a[i][i])) {
 32       continue;
 33     }
 34     const double r = 1.0/a[i][i];
 35     for (int k = i; k < M; k++) {
 36       a[i][k] *= r;
 37     }
 38     b[i] *= r;
 39     for (int j = 0; j < N; j++) {
 40       if (j == i) {
 41         continue;
 42       }
 43       const double t = a[j][i];
 44       for (int k = i; k < M; k++) {
 45         a[j][k] -= t * a[i][k];
 46       }
 47       b[j] -= t * b[i];
 48     }
 49   }
 50 
 51   const vector<vector<double> > t1(a);
 52   const vector<double> t2(b);
 53   for (int i = 0; i < N; i++) {
 54     a[sigma[i]] = t1[i];
 55     b[sigma[i]] = t2[i];
 56   }
 57   return true;
 58 }
 59 typedef string::const_iterator Iterator;
 60 
 61 void skip_white(Iterator& it, const Iterator& last)
 62 {
 63   while (it != last && *it == ' ') {
 64     ++it;
 65   }
 66 }
 67 
 68 int number(Iterator& it, const Iterator& last)
 69 {
 70   int n = 0;
 71   while (it != last && '0' <= *it && *it <= '9') {
 72     n = 10*n + (*it-'0');
 73     ++it;
 74   }
 75   return n;
 76 }
 77 
 78 pair<vector<double>, double> parse(Iterator& it, const Iterator& last)
 79 {
 80   skip_white(it, last);
 81   if (it == last) {
 82     while (true);
 83   }
 84   if (*it == '(') {
 85     ++it;
 86     skip_white(it, last);
 87     vector<pair<vector<double>, double> > rs;
 88     while (*it != ')') {
 89       const pair<vector<double>, double> r = parse(it, last);
 90       rs.push_back(r);
 91       skip_white(it, last);
 92     }
 93     ++it;
 94     skip_white(it, last);
 95 
 96     const double N = rs.size();
 97     vector<double> v(26, 0);
 98     double c = 0;
 99     for (vector<pair<vector<double>, double> >::const_iterator jt = rs.begin(); jt != rs.end(); ++jt) {
100       for (int i = 0; i < 26; i++) {
101         v[i] += jt->first[i] / N;
102       }
103       c += jt->second / N;
104     }
105     return make_pair(v, c);
106   } else if ('0' <= *it && *it <= '9') {
107     int c = number(it, last);
108     skip_white(it, last);
109     return make_pair(vector<double>(26, 0), c);
110   } else if (*it == '-') {
111     ++it;
112     int c = number(it, last);
113     skip_white(it, last);
114     return make_pair(vector<double>(26, 0), -c);
115   } else if ('a' <= *it && *it <= 'z') {
116     vector<double> v(26, 0);
117     v[*it-'a'] = 1;
118     ++it;
119     skip_white(it, last);
120     return make_pair(v, 0);
121   } else {
122     while (true);
123   }
124 }
125 
126 int main()
127 {
128   int N;
129   for (int Ti = 1; cin >> N && N != 0; Ti++) {
130     cin.ignore();
131     vector<vector<double> > m;
132     vector<double> x;
133     for (int i = 0; i < N; i++) {
134       string s;
135       getline(cin, s);
136       Iterator it = s.begin(), last = s.end();
137       int var = *it-'a';
138       ++it;
139       skip_white(it, last);
140       if (*it != '=') {
141         while (true);
142       }
143       ++it;
144       skip_white(it, last);
145       pair<vector<double>, double> r = parse(it, last);
146       r.first[var] -= 1.0;
147       r.second = -r.second;
148       m.push_back(r.first);
149       x.push_back(r.second);
150     }
151 
152     printf("Game %d\n", Ti);
153     if (gaussian_elimination(m, x)) {
154       queue<int> q;
155       vector<int> undef(N, false);
156       for (int i = 0; i < N; i++) {
157         if (is_zero(m[i][i])) {
158           undef[i] = true;
159           q.push(i);
160         }
161       }
162       while (!q.empty()) {
163         const int n = q.front();
164         q.pop();
165         for (int i = 0; i < N; i++) {
166           if (!is_zero(m[i][n]) && !undef[i]) {
167             undef[i] = true;
168             q.push(i);
169           }
170         }
171       }
172 
173       for (int i = 0; i < N; i++) {
174         printf("Expected score for %c ", i+'a');
175         if (undef[i]) {
176           puts("undefined");
177         } else {
178           if (is_zero(x[i])) {
179             x[i] = 0;
180           }
181           printf("= %.3f\n", x[i]);
182         }
183       }
184     } else {
185       while (true);
186     }
187     puts("");
188   }
189   return 0;
190 }
poj/1487.cc