Что спрашивают

В строке из I, V, X, L, C, D, M нужно найти самый длинный фрагмент, являющийся канонической римской записью числа от 1 до 3999. При равной длине выбирается меньшее числовое значение. Выводится десятичное число.

Нельзя просто складывать и вычитать значения всей строки: сначала нужно убедиться, что выбранный фрагмент составлен по разрешённым формам тысяч, сотен, десятков и единиц.

Приём решения

Каноническая запись состоит из четырёх последовательных блоков. Каждый блок может быть пустым, но вся запись — нет. Для тысяч разрешено до трёх M. Для остальных разрядов есть две вычитательные пары либо старшая цифра разряда с несколькими младшими.

РазрядРегулярное выражение
ТысячиM{0,3}
СотниCM|CD|D?C{0,3}
ДесяткиXC|XL|L?X{0,3}
ЕдиницыIX|IV|V?I{0,3}

Соединим блоки в одну регулярную форму. Проверять её нужно с каждого начала, включая начала внутри уже найденного фрагмента. Для этого используем опережающую проверку (?=(...)): совпадение не поглощает символы, а найденная запись доступна в первой группе.

  1. Получите наиболее длинный допустимый префикс с каждого начала: блоки выражения выбирают свои максимальные допустимые формы.
  2. Пропускайте пустые совпадения, возможные из-за пустых блоков.
  3. Переведите найденную запись в десятичное значение, вычитая символ перед более крупным и складывая остальные.
  4. Сравните пару (-длина, значение) с лучшей: отрицательная длина обеспечивает максимум, значение — минимум при равенстве.

Проверка канонической формы идёт до вычисления значения. Например, формальная вычитательная трактовка IL не делает её разрешённой записью 49; канонический вариант — XLIX.

Длина разрешённой записи ограничена пятнадцатью символами: до трёх тысяч и до четырёх знаков в каждом оставшемся разряде. Поэтому работа с каждым началом ограничена постоянной величиной, итоговое время — O(n), дополнительная память — O(1). Все 3999 записей перечислять для каждого входа не требуется.

Разбор на примере

Ввод

XVIIILXIII

Вывод

18
Разбор примера по шагам
НачалоДлиннейшая запись отсюдаДлинаЗначение
0XVIII518
1VIII48
5LXIII563

В строке есть две записи длины пять: XVIII и LXIII. Они означают 18 и 63, поэтому выбирается 18. Вся строка канонической записью не является: после блока единиц XVIII нельзя приписать новый десяток. Более короткая VIII не выигрывает, хотя её значение ещё меньше.

Код на Python и C++

decimal применяется только к уже проверенным записям. Первая координата пары отрицательна: длинные фрагменты при сравнении min идут раньше коротких.

В C++ тот же шаблон через std::regex тоже работает: совпадения короткие. Но на строке в миллион символов он в несколько раз медленнее, поэтому в коде на C++ шаблон записан функцией roman_length. Она с каждой позиции проходит тысячи, сотни, десятки и единицы в том же порядке, что и шаблон. Пара (-длина, значение) — pair<int, int>.

import re
import sys

VALUES = {'I': 1, 'V': 5, 'X': 10, 'L': 50,
          'C': 100, 'D': 500, 'M': 1000}
PATTERN = (r'M{0,3}(?:CM|CD|D?C{0,3})'
           r'(?:XC|XL|L?X{0,3})(?:IX|IV|V?I{0,3})')
OVERLAP = re.compile(r'(?=(' + PATTERN + r'))')


def decimal(word):
    total = 0
    for i, ch in enumerate(word):
        value = VALUES[ch]
        if i + 1 < len(word) and value < VALUES[word[i + 1]]:
            total -= value
        else:
            total += value
    return total


def solve(s):
    best = (0, 0)
    for match in OVERLAP.finditer(s):
        word = match.group(1)
        if word:
            best = min(best, (-len(word), decimal(word)))
    return best[1]

if __name__ == '__main__':
    print(solve(sys.stdin.readline().rstrip('\r\n')))
#include <iostream>
#include <map>
#include <string>
#include <utility>
using namespace std;

map<char, int> VALUES = {{'I', 1}, {'V', 5}, {'X', 10}, {'L', 50},
                         {'C', 100}, {'D', 500}, {'M', 1000}};

// Длина разряда с позиции i: две буквы вычитания (CM, CD) или
// старшая буква разряда и до трёх младших (D?C{0,3}). Так же для десятков и единиц.
int digit_length(const string& s, int i, char one, char five, char ten) {
    int n = s.size();
    if (i + 1 < n && s[i] == one && (s[i + 1] == ten || s[i + 1] == five))
        return 2;
    int length = 0;
    if (i < n && s[i] == five)
        length = 1;
    for (int k = 0; k < 3 && i + length < n && s[i + length] == one; k++)
        length += 1;
    return length;
}

// То же, что шаблон M{0,3}(?:CM|CD|D?C{0,3})(?:XC|XL|L?X{0,3})(?:IX|IV|V?I{0,3}) с позиции start.
int roman_length(const string& s, int start) {
    int i = start, n = s.size();
    for (int k = 0; k < 3 && i < n && s[i] == 'M'; k++)
        i += 1;
    i += digit_length(s, i, 'C', 'D', 'M');
    i += digit_length(s, i, 'X', 'L', 'C');
    i += digit_length(s, i, 'I', 'V', 'X');
    return i - start;
}

int decimal(const string& word) {
    int total = 0;
    for (size_t i = 0; i < word.size(); i++) {
        int value = VALUES[word[i]];
        if (i + 1 < word.size() && value < VALUES[word[i + 1]])
            total -= value;
        else
            total += value;
    }
    return total;
}

int solve(const string& s) {
    pair<int, int> best = {0, 0};
    for (int start = 0; start < (int)s.size(); start++) {
        int length = roman_length(s, start);
        if (length > 0)
            best = min(best, {-length, decimal(s.substr(start, length))});
    }
    return best.second;
}

int main() {
    string s;
    getline(cin, s);
    if (!s.empty() && s.back() == '\r')
        s.pop_back();
    cout << solve(s) << endl;
}

Типичные ошибки

  • Посчитать значение всей строки без проверки формы

    Правило вычитания само по себе не проверяет каноничность. Сначала найдите фрагмент, соответствующий формам разрядов.

  • Искать только непересекающиеся совпадения

    Правильная запись может начинаться внутри предыдущего совпадения и оказаться длиннее. Нужно просмотреть все начала.

  • Сначала минимизировать значение

    Главный критерий — длина. Меньшее число выбирается лишь среди записей одинаковой максимальной длины.

  • Выбрать большее значение при равенстве

    Второй элемент пары сравнивается по возрастанию. Отрицательна только длина, но не десятичное значение.