hotpepsiの練習帳

SRM 649

15:02

Div1 Easy (250) Decipherability

問題

• 文字列sが与えられる
• K文字削除する
• 削除した場所が一意かどうかを判定する

方針

• 全ての文字がユニークな場合は常に一意
• 全て削除する場合は一意
• 一意でないのは、同じ文字が含まれていて、削除後に残った文字がどちらなのかわからない場合
• すなわちs[i]とs[i+j]が同じ文字のとき、jがK以下のとき(K-1文字以下がはさまっているとき)は一意でない
• 全てのiについて調べる
• Passed System Test

結果

o-- -1 204.60 -25 = 179.60pts 293rd/555 rating 1424 -> 1443 (+19)

写経が不十分で失敗した。

最長共通部分列を求めても解けるらしい。

http://togetter.com/li/781384