SRM618 Div1 Medium "LongWordsDiv1"
問題
TopCoder Statistics - Problem Statement
訳
キツネのシエルはn個のアルファベットを持っている。彼女は下記のような性質を全て持つ文字列が好きである。
1. 同じ文字が隣り合っていない。 2. xとyを(同じ文字もありうる)ある文字として、xyxyとなるような部分列を持たない。 部分列は元の文字列の連続したものでなくともよいことに注意して欲しい。 3. 上記1.と2.を満たす文字列の中で、最も長い文字列である。
例: シエルは'B'が2つ隣り合っているため、"ABBA"は好きではない。 シエルは部分列"TETE"を含んでいるため、"THETOPCODER"は好きではない。 シエルは部分列"AAAA"を含んでいるため、"ABACADA"は好きではない。(x=y='A') シエルはより長い"ABCBA"があるため、"ABCA"は好きではない。 もし、n=1で、シエルが持つアルファベットが'A'であれば、 彼女は"A"という文字列が好きである。 もし、n=2で、シエルが持つアルファベットが'A'と'B'であれば、 彼女は"ABA"と"BAB"という文字列が好きである。
整数nが与えられるので、シエルが好きな文字列の数を返せ。
制約
1 <= n <= 5000
考えたこと
まず、問題文より次のことが分かる
ある文字は3回までしか使えない。
"ABCA"という文字列を考える。ここで、'A'に挟まれた'B'と'C'は1回しか使っていないが、末尾に追加しようとしても、部分列に"ABAB"または"ACAC"を含んでしまうためこれ以上追加で使うことはできない。しかし、'A'の挟まれた中に追加し、"ABCBA"もしくは"ACBCA"とすることはできる。
なにが言いたいかというと、"ABCA"みたいに'A'で挟まれた部分で左右非対称となるのは、最も長い文字列をでなければならないという条件に反するため、シエルの好きな文字列にはなり得ない、といいたいのです・・(説明が上手くできぬ)
ある文字で挟まれた部分は、左右対称でなければならない
ある文字で挟まれた部分は、左右対称となる必要があるため、1文字だけは1回しか使えない。つまり、"ABCBA"や"ACBCA"や"ABCDCBA"は、それぞれ'C' 'B' 'D'を1回とする必要がある。ここでは'A'を2回使ったので1文字が1回しか使えなくなったが、'A'を3回使うと2文字が1回しか使えなくなる。例えば、"ABACA"は'B'と'C'が、"ABCBADA"は'C'と'D'が1回しか使えなくなっている。つまり、'A'を2回から3回使うと1回しか使えない文字が1文字増えるため、2回使おうが3回使おうが、文字列の最大の長さは変わらない。まとめると次のようなことがいえる
最大文字列の長さはn * 2 - 1である
これらの条件を利用すれば、DPで解けるようになる。
dp[i] := i文字でシエルの好きな文字列が何個作れるか。
dp[i+1] = (dp[i] + sum(dp[i]*dp[1] + dp[i - 1]*dp[2] + ... dp[1]*dp[i])) * (i + 1)
ソースコード
const int MOD = 1000000007; long long dp[5050]; class LongWordsDiv1 { public: int count(int n) { dp[1] = 1; for (int i = 2; i <= n; i++) { long long r = dp[i - 1]; for (int j = 1; j < i - 1; j++) { int k = i - 1 - j; r = (r + (dp[j] * dp[k] % MOD)) % MOD; } dp[i] = r; } long long res = dp[n]; for (int i = 1; i <= n; i++) { res = res * i % MOD; } return (int)res; } };