mini notes

競技プログラミングの解法メモを残していきます。

CODE FESTIVAL 2015 あさぷろ Middle B - ヘイホー君と削除

問題:B - ヘイホー君と削除

解答:Submission #11251025 - CODE FESTIVAL 2015 あさぷろ Middle

解法:文字列sをある場所を区切って文字列aとbに分割する。aで平方の前半、bで平方の後半を作るとする。このとき作れる平方文字の最大長はaとbのLCS(最長部分文字列)の長さの2倍になる。よって区切り方をすべて試し、そのたびにlcsを計算すればよい。