POJ 1496 - Word Index

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

概要

小文字のアルファベットのみを使ってできる strict lexicographic order な文字列を辞書順に番号を付けていく．

• a -> 1
• ...
• z -> 26
• ab -> 27
• ...
• az -> 51
• bc -> 52
• ...
• vwxyz -> 83681

である．

与えられた文字列に対して，その番号を答える． ただし，不正な文字列 (strict lexicographic order でない文字列)であった場合は 0 を出力する．

制約

• 答えの番号は 83681 を越えない

解法

文字列 s の番号は，s の長さを L とすると

Σ(C(26, i+1) - C(26-(s[i]-'a'+1), L-i))

で計算できる．ここで C(n,k) は組み合わせの数．

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int comb[27][27];
 5 
 6 int encode(const string& s)
 7 {
 8   const int len = s.size();
 9   int r = 0;
10   for (int i = 0; i < len; i++) {
11     if (s[i-1] < s[i]) {
12       r = r + comb[26][i+1] - comb[26-(s[i]-'a'+1)][len-i];
13     } else {
14       return 0;
15     }
16   }
17   return r;
18 }
19 
20 int main()
21 {
22   for (int i = 0; i <= 26; i++) {
23     comb[i][0] = 1;
24     comb[i][i] = 1;
25   }
26   for (int n = 1; n <= 26; n++) {
27     for (int k = 1; k < n; k++) {
28       comb[n][k] = comb[n-1][k] + comb[n-1][k-1];
29     }
30   }
31 
32   string s;
33   while (cin >> s) {
34     cout << encode(s) << endl;
35   }
36 
37   return 0;
38 }