SRM319 D2H IncompleteBST

TopCoder Statistics - Problem Statement

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

完全二分木が与えられる．完全二分木のためノードは子にleftとrightを持つが，その持つ値に制限がある．

  • leftの部分木の全ての値はleftの値より小さいか等しくなければならない
  • rightの部分木の全ての値はrightの値より大きくなければならない

完全二分木の中に1つだけ要素が決まっていないノード?がある．そのノードの値として制約を満たすアルファベットを全て並べる．

?のノードの値を全て探索して制約を満たしているかどうか見てあげる．dfsでは，今見ているノードが持って良い値の範囲を$[minval$, $maxval]$として持っておく．leftに行く場合には，その部分木が今見ているノードの値より小さいか等しくなければいけないので$[minval$, $val]$として進む．rightに行く場合には，その部分木が今見ているノードの値より大きくなければいけないので$[val + 1$, $minval]$として進む．矛盾なく進むことが出来たらtrueを返すようにした．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <queue>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int cnt[1<<21];
bool flag[1<<21];

int vmax = -1;
bool dfs(int id, int val, int minval, int maxval) {
  if(val < minval || val > maxval) {
      return false;
  }

  int l = (id * 2);
  int r = (id * 2 + 1);

  bool f1 = false, f2 = false;

  if(cnt[l] != -1) {
      f1 = dfs(l, cnt[l], minval, val);
  } else {
      f1 = true;
  }

  if(cnt[r] != -1) {
      f2 = dfs(r, cnt[r], val + 1, maxval);
  } else {
      f2 = true;
  }

  return f1 && f2;
}


class IncompleteBST {
  public:
  string missingValues(vector <string> tree) {
      int n = tree.size();
      memset(cnt, -1, sizeof(cnt));
      memset(flag, 0, sizeof(flag));

      int x = -1;
      rep(i, n) {
          string s = tree[i].substr(2);
          stringstream ss(s);
          int id; ss >> id;

          vmax = max(vmax, id);

          if(tree[i][0] == '?') {
              flag[id] = true;
              x = id;
          } else {
              int val = (tree[i][0] - 'A');
              cnt[id] = val;
          }

      }

      string ans = "";
      rep(i, 26) {
          cnt[x] = i;
          if(dfs(1, cnt[1], 0, 25)) {
              ans += char('A'+i);
          }
      }

      return ans;
  }
};
Oct 27th, 2016
srm, topcoder, 木