ZeroJudge 解題筆記：c077. 00417 - Word Index

作者：王一哲
日期：2026年2月17日


ZeroJudge 題目連結：c077. 00417 - Word Index

解題想法

這題給的條件比較寬鬆，先建表列出所有答案再查表也能通過。但如果能夠找出規律，用數學解會快很多。

Python 程式碼

建表，使用時間約為 31 ms，記憶體約為 15.6 MB，通過測試。

import sys

cnt = 0  # 編號
table = dict()  # 表格，內容為{字串: 編號}
# a ~ z 的編號
for i in range(26):
    cnt += 1
    s = chr(i+ord('a'))
    table[s] = cnt
# ab ~ yz 的編號
for i in range(26):
    s = chr(i+ord('a'))
    for j in range(i+1, 26):
        t = s + chr(j+ord('a'))
        cnt += 1
        table[t] = cnt
# abc ~ xyz 的編號
for i in range(26):
    s = chr(i+ord('a'))
    for j in range(i+1, 26):
        t = s + chr(j+ord('a'))
        for k in range(j+1, 26):
            u = t + chr(k+ord('a'))
            cnt += 1
            table[u] = cnt
# abcd ~ wxyz 的編號
for i in range(26):
    s = chr(i+ord('a'))
    for j in range(i+1, 26):
        t = s + chr(j+ord('a'))
        for k in range(j+1, 26):
            u = t + chr(k+ord('a'))
            for x in range(k+1, 26):
                v = u + chr(x+ord('a'))
                cnt += 1
                table[v] = cnt
# abcde ~ vwxyz 的編號
for i in range(26):
    s = chr(i+ord('a'))
    for j in range(i+1, 26):
        t = s + chr(j+ord('a'))
        for k in range(j+1, 26):
            u = t + chr(k+ord('a'))
            for x in range(k+1, 26):
                v = u + chr(x+ord('a'))
                for y in range(x+1, 26):
                    w = v + chr(y+ord('a'))
                    cnt += 1
                    table[w] = cnt
# 讀取測資並查表輸出答案，如果 key 不在 table 之中則輸出 0
for line in sys.stdin:
    print(table.get(line.rstrip(), 0))

數學解，使用時間約為 7 ms，記憶體約為 3 MB，通過測試。

import sys

def comb(n, m):  # C n 取 m
    if m < 0 or m > n: return 0  # 不合法的算式，回傳 0
    m = min(m, n-m)  # 取 m, n-m 較小者
    ans = 1  # 組合數
    for i in range(1, m+1):
        ans = ans*(n-i+1)//i
    return ans

def calculate_code(s):  # 輸入字串，回傳編號
    n, code = len(s), 0  # 字串長度，編號
    # 檢查字符串是否合法，後面的字元大於前面的字元
    for i in range(n-1):
        if s[i+1] <= s[i]:  # 不合法，回傳 0
            return 0
    # 計算長度為 1 ~ n-1 的組合數
    for i in range(1, n):
        code += comb(26, i)
    # 計算長度 n 的排名
    for i in range(n):  # 掃過 s[0] ~ s[n-i]
        start = ord('a') if i == 0 else ord(s[i-1]) + 1  # i = 0 從 a 開始，否則從 s[i-1] 下一個開始
        end = ord(s[i])  # 到 s[i] 的編號為止
        for c in range(start, end):
            code += comb(26 - (c-ord('a')+1), n-i-1)
    # 最後要再加 1
    return code + 1

for line in sys.stdin:
    print(calculate_code(line.rstrip()))

C++ 程式碼

建表，使用時間約為 15 ms，記憶體約為 6.7 MB，通過測試。

#include <iostream>
#include <string>
#include <map>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int cnt = 0;  // 編號
    map<string, int> table;  // 表格，內容為{字串, 編號}
    /* a ~ z 的編號 */
    for(int i=0; i<26; i++) {
        string s (1, char(i+'a'));
        cnt++;
        table[s] = cnt;
    }
    /* ab ~ yz 的編號 */
    for(int i=0; i<26; i++) {
        string s (1, char(i+'a'));
        for(int j=i+1; j<26; j++) {
            string t = s + char(j+'a');
            cnt++;
            table[t] = cnt;
        }
    }
    /* abc ~ xyz 的編號 */
    for(int i=0; i<26; i++) {
        string s (1, char(i+'a'));
        for(int j=i+1; j<26; j++) {
            string t = s + char(j+'a');
            for(int k=j+1; k<26; k++) {
                string u = t + char(k+'a');
                cnt++;
                table[u] = cnt;
            }
        }
    }
    /* abcd ~ wxyz 的編號 */
    for(int i=0; i<26; i++) {
        string s (1, char(i+'a'));
        for(int j=i+1; j<26; j++) {
            string t = s + char(j+'a');
            for(int k=j+1; k<26; k++) {
                string u = t + char(k+'a');
                for(int x=k+1; x<26; x++) {
                    string v = u + char(x+'a');
                    cnt++;
                    table[v] = cnt;
                }
            }
        }
    }
    /* abcde ~ vwxyz 的編號 */
    for(int i=0; i<26; i++) {
        string s (1, char(i+'a'));
        for(int j=i+1; j<26; j++) {
            string t = s + char(j+'a');
            for(int k=j+1; k<26; k++) {
                string u = t + char(k+'a');
                for(int x=k+1; x<26; x++) {
                    string v = u + char(x+'a');
                    for(int y=x+1; y<26; y++) {
                        string w = v + char(y+'a');
                        cnt++;
                        table[w] = cnt;
                    }
                }
            }
        }
    }
    /* 讀取測資並查表輸出答案，如果 key 不在 table 之中則輸出 0 */
    string line;
    while(cin >> line) cout << table[line] << "\n";
    return 0;
}

數學解，使用時間約為 1 ms，記憶體約為 312 kB，通過測試。

#include <iostream>
#include <string>
using namespace std;

int comb(int n, int m) {  // C n 取 m
    if (m < 0 || m > n) return 0;  // 不合法的算式，回傳 0
    if (n-m < m) m = n-m;  // 取 m, n-m 較小者
    int ans = 1;  // 組合數
    for(int i=1; i<=m; i++) ans = ans*(n-i+1)/i;
    return ans;
}

int calculate_code(string s) {  // 輸入字串，回傳編號
    int n = (int)s.size(), code = 0;  // 字串長度，編號
    // 檢查字符串是否合法，後面的字元大於前面的字元
    for(int i=0; i<n-1; i++) {
        if (s[i+1] <= s[i]) return 0;  // 不合法，回傳 0
    }
    // 計算長度為 1 ~ n-1 的組合數
    for(int i=1; i<n; i++) code += comb(26, i);
    // 計算長度 n 的排名
    for(int i=0; i<n; i++) {  // 掃過 s[0] ~ s[n-i]
        int start = (i == 0 ? 'a' : s[i-1]+1);  // i = 0 從 a 開始，否則從 s[i-1] 下一個開始
        int end = s[i];  // 到 s[i] 的編號為止
        for(int j=start; j<end; j++) code += comb(26 - (j-'a'+1), n-i-1);
    }
    // 最後要再加 1
    return code + 1;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string s;
    while(cin >> s) cout << calculate_code(s) << "\n";
    return 0;
}