AGC012 C Tautonym Puzzle
問題
概要
aa
はa
を2回、bubobubo
はbubo
を2回繰り返している。このように長さ1以上の文字列を2回繰り返しているものは良い文字列と定義する。入力 が与えられるので、良い文字列である部分列の個数がである長さ200以下の文字列の1例を答えよ。ただし、文字の種類は最大種類しか使えない。
解法
まず例えば1, 2, 3, 4, 5, 1, 2, 3, 4, 5
という文字列に良い部分文字列がいくつあるかを数えてみる。半分に分割すると、1, 2, 3, 4, 5から1個以上選ぶ方法存在し、それは通りであることがわかる(は空文字列の場合)。
ここに1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 6, 5
のように6
を追加すると良い部分文字列がいくつ増えるかを考える。6
を含む選び方の数だけ増えるが、6
と5
を同時に選ぶことは出来ず、1, 2, 3, 4から0個以上選ぶ方法()通りだけ増える。
別の場合として、1, 2, 3, 4, 5, 6, 1, 2, 3, 6, 4, 5
のように6
を追加すると、良い部分文字列は1, 2, 3から0個以上選ぶ方法(通り)だけ増える。
このように、新しい文字種のペアを挿入する場所によって、増加する文字列の数を個増加させることができる。しかもこの挿入は独立なので、から個まで増加する文字列を1刻みで調節できる。
の場合を例にすると、下のように文字を追加する。
より、生成される文字列の長さは文字以下、文字の種類は以下となる。よって制約を満たす文字列を作ることができる。
ソースコード
こういう構築系は配点がそこそこ高くても思いつき次第でACを狙える時があるので、レート上昇が滞っている今は解ける問題を時間中に貪欲に探していく戦略が大事かも。