SRM323 D2H UnrepeatableWords

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.

文字列がk-unrepeatableであるとは，全ての部分文字列がその文字列の中に$k$個未満のことである．全探索で通らないと思ったけど通るらしい．多分$A$から始めていって条件を満たさないときに，戻るのがそんなに戻らなくて大丈夫なのかな(適当)．
条件を満たすのをチェックするのは部分文字列が$k$個未満であればいいので，文字列の区間$[i, j]$を$k$個に分割して，先頭から確かめていく．

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

#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;

string ans = "";
int a[55];
int k, n, allowed;

int f(int sz) {
  rep(i, sz) {
      REP(j, i + 1, sz) {
          if((j - i + 1) % k == 0) {
              int len = (j - i + 1) / k;
              bool flag = true;

              REP(u, i, j - len + 1) {
                  if(a[u] != a[u + len]) {
                      flag = false;
                      break;
                  }
              }
              if(flag) return true;
          }
      }
  }
  return false;
}

bool flag;
void dfs(int sz) {
  if(flag) return;

  if(sz == n) {
      rep(i, n) {
          ans += char('A' + a[i]);
      }
      flag = true;
      return;
  }

  rep(i, allowed) {
      a[sz] = i;
      if(f(sz + 1)) continue;
      dfs(sz + 1);
  }
}

class UnrepeatableWords {
  public:
  string getWord(int _k, int _n, int _allowed) {
      k = _k;
      n = _n;
      allowed = _allowed;

      ans = "";
      flag = false;
      memset(a, 0, sizeof(a));

      dfs(0);
      return ans;
  }
};
Nov 18th, 2016
srm, topcoder, 全探索