WBC004 C - Blurred Numbers 解説

2021年3月18日に開かれたウインドベル(@Twi_Stamp)主催の競プロ有志コンテストWind Bel Contest 004 – Good Bye 2A Day 2の解説です。

問題文

文字列 が与えられます。 の各文字は、ローマ数字の記号 (I, V, X, L, C, D, M) または ? です。

? をローマ数字の記号に置き換えてできる文字列のうち、文字列全体を通してローマ数字として成り立つものは何通りあるでしょうか？

しかし、東京大学には「優３割規定」というルールがあります。「優３割規定」とは、『 点以上の成績がつく学生の人数は受講者全体の 以下でなければならない』というルールです。このルールに違反すると、怒られが発生します。

怒られるのは嫌なので、あなたは「優３割規定」に違反しないように成績をつけ直すことにしました。あなたは任意の学生の点数を 点に変えることができます。最低で何人の学生の点数を 点に変えれば「優３割規定」をみたすことができるか求めてください。

制約

• はローマ数字の記号 (I, V, X, L, C, D, M) と ? からなる
• 

解説

桁DPはしません。この問題、メチャクチャ見掛け倒しです。

作れるローマ数字は 以上 以下のたった 通りなので、ローマ数字のほうを全部生成して文字列 に一致するものがいくつあるか数えればよいです。

計算量は として です。

実装例

def int_to_roman(n):
    """
    1～3999のアラビア数字を入れるとそれに対応するローマ数字を返す関数
    """
    assert 1 <= n <= 3999

    res = ""

    # 1000の位
    d, n = divmod(n, 1000)
    res += ["", "M", "MM", "MMM"][d]

    # 100の位
    d, n = divmod(n, 100)
    res += ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"][d]

    # 10の位
    d, n = divmod(n, 10)
    res += ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"][d]

    # 1の位
    res += ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"][n]

    return res

def is_match(s, target):
    """
    与えられた文字列Sが目的のローマ数字を表せるか判定する関数
    """
    # 長さが違ったらダメ
    if len(s) != len(target):
        return False
        
    # 1文字ずつ見ていって食い違いがあったらダメ
    for sl, tl in zip(s, target):
        if sl != tl and sl != "?":
            return False
    return True

def solve():
    s = input()
    print(sum(is_match(s, int_to_roman(n)) for n in range(1, 4000)))
    
t = int(input())
for _ in range(t): solve()

ひとこと

最近、ABCのCにもこういう問題多いですよね。