hotpepsiの練習帳

SRM 698

00:01

https://competitiveprogramming.info/topcoder/srm/round/16802/div/1

Div1 Easy (250) RepeatString

問題

• 文字列が二つの文字列の繰り返しになっているとき、平方文字列と呼ぶ
• 1ターンで、1文字挿入、1文字変更、1文字削除、のいずれかの操作を行う
• 文字列sを平方文字列にするための最小ターン数を求める

方針

• 左側と右側にわけてDP (左側の長さを全て試す)
• Failed System Test
• 編集距離のライブラリを貼ればいいらしい
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_698/RepeatString.cpp

結果

x-- +1 50pt 280th/431 rating 1582 -> 1533 (-49)

DP力が少し足りなかった。

https://togetter.com/li/1025727