ARC155 A - ST and TS Palindrome (400)
再帰的に考える
$ k \le nの場合
片方の条件から完全に$ S'が決まるのでもう一報でも条件を満たしているか確認するだけ
$ k \lt 2nの場合
2つの条件から$ S'の前半分と後ろ半分が定まる
重複する部分は矛盾が発生するなら駄目
実際に作った$ S'が条件を満たすかどうか確認してその結果が答え
$ k \le 4nの場合
2つの条件から前後それぞれ$ n文字が決まる
適当に何回か2つの条件の回文を作って道だったところを決定していく
最終的に回文であるかを判定
それ以上の場合
先頭にある$ rev(S)+Sと最後の$ S+rev(S)を任意の回数取り除くことで$ k \le 4nの場合にすることができるのでそれを解く
解説によると$ k \le 2nの場合だけで再帰的に解ける