BOJ 1339 - Word Math

Problem: BOJ 1339 — Word Math · 한국어 · 日本語

Treat every letter as a digit shared by all occurrences of that letter. In a word, a letter in the ones place contributes its digit once, a letter in the tens place contributes ten times its digit, and so on. For example, ABC contributes 100 * value[A] + 10 * value[B] + value[C]. Summing these positional weights over every occurrence in every word turns the total into sum(weight[letter] * digit[letter]).

The best assignment pairs the largest weight with the largest available digit. To see why, suppose weights w1 > w2 were assigned digits d1 < d2. Swapping those digits changes the sum by (w1 * d2 + w2 * d1) - (w1 * d1 + w2 * d2) = (w1 - w2) * (d2 - d1) > 0. Such an inverted pair cannot be optimal, so sorting weights descending and assigning 9, 8, ... maximizes the sum. Equal weights may be ordered by letter to make the result deterministic; swapping equal-weight letters does not change the total.

If T is the total number of characters and A is the number of distinct letters, computing weights takes O(T) time and sorting them takes O(A log A), for O(T + A log A) time overall. The weights and answer use long long.

C++17

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    long long weight[26] = {};
    for (int i = 0; i < n; ++i) {
        string word;
        cin >> word;

        long long place = 1;
        for (int j = static_cast<int>(word.size()) - 1; j >= 0; --j) {
            weight[word[j] - 'A'] += place;
            place *= 10;
        }
    }

    vector<pair<long long, int>> letters;
    for (int letter = 0; letter < 26; ++letter) {
        if (weight[letter] > 0) {
            letters.emplace_back(weight[letter], letter);
        }
    }

    sort(letters.begin(), letters.end(), [](const auto& a, const auto& b) {
        if (a.first != b.first) {
            return a.first > b.first;
        }
        return a.second < b.second;
    });

    long long answer = 0;
    int digit = 9;
    for (const auto& [letter_weight, letter] : letters) {
        answer += letter_weight * digit--;
    }

    cout << answer << '\n';
}