🐷

Codejam2022 Round1A: Double or One Thing

2022/05/05に公開

Python

programming

algorithm

tech

問題

Uppercaseの英文字列が与えられる。文字のハイライトを行った時に得られる新しい文字列のうち、辞書順で最初に現れる文字列を求める。文字のハイライトは、たとえばHELLOWORLDで、H・L・O・Lをハイライトしたとすると、HHELLOWOORLLDのようにハイライトした文字が二回追加される処理。

アルゴリズム

ハイライトする文字を以下のように決めてみる。

隣り合う文字sとtで、s<tの場合にはsをハイライトする。tを右側にずらし、sで置き換えることで、辞書順で小さくすることができる。
s>tの場合には、sはハイライトしない。ハイライトしてしまうと、辞書順で大きくしてしまうことになるため。

これだとs=tの時に決めることができない。tの次のuを見て、s>uまたはs<uならば上のルールで決めることはできるが、s=t=uとなると同じように決められなくなる。

入力文字列を同じ文字列のブロックとして扱って、隣り合う異なる文字列sとtの比較をする。例えば、BOOKKEEPERであれば、[(B,1),(O,2),(K,2),(E,2),(P,1),(E,1),(R,1)]として、BとOを比較してB<OなのでBをハイライト、OとKを比較してO>Kなのでハイライトしないと決めることができる。また、EとPを比較してE<Pなのでハイライトするが、Eの長さ２を倍にした４文字とする（Eを一つだけ倍にしただけだと辞書順で大きくなるため）。

実装

入力文字列の前処理は、itertoolsのgroupbyを利用。

def counts(S):
    import itertools
    return [(label, len(list(group))) for label, group in itertools.groupby(S)]


T = int(input())
for t in range(1, T + 1):
    S = input()
    s_counts = counts(S)
    res = []
    for i in range(len(s_counts)):
        if i < len(s_counts) - 1 and s_counts[i][0] < s_counts[i+1][0]:
            res.extend([s_counts[i][0] for _ in range(s_counts[i][1] * 2)])
        else:
            res.extend([s_counts[i][0] for _ in range(s_counts[i][1])])
    print('Case #{}: {}'.format(t, ''.join(res)))

問題

アルゴリズム

実装

Discussion