JOI '10 春合宿２：2 - DNA の合成 (DNA synthesizer)
問題
https://www.ioi-jp.org/camp/2010/2010-sp-tasks/2010-sp-day2_21.pdf
解法
dp(i) := S の i 文字目までを構成するのに素 DNA 鎖が最小で何本必要か
と DP を定義する．このとき，S の i 文字目から文字列が一致する素 DNA 鎖の最大の長さを maxL とすると，
dp(i) = min( dp(i + 1), dp(i + 2), ... , dp(i + maxL - 1) ) + 1（i + maxL が S の長さよりも小さいとき）
dp(i) = 1（i + maxL が S の長さと一致するとき）
と漸化式が立つ．各素 DNA 鎖の長さは高々 20 なので，各 DP の遷移に文字列走査がボトルネックとなり O(logN) かかるので全体で O(|S|logN)．
解答
実装において，ある文字列 T が存在するかどうかを std::map<std::string, bool> で管理し，判定していたため TLE を出してしまっていた．std::map ではなく std::unordered_set や std::set を使うことで高速化できる．ある値が存在するかどうかだけを知りたい場合は，積極的に set 系を使っていこうと思った．
