Codejam2022 Round1A: Double or One Thing
問題
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)))
Author And Source
この問題について(Codejam2022 Round1A: Double or One Thing), 我々は、より多くの情報をここで見つけました https://zenn.dev/satojkovic/articles/1d0e972cd020b1著者帰属：元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Collection and Share based on the CC protocol