予選A-C 天下一文字集合 解説
部分点1
与えられた「*」に対して、ありうるもの(他のパターンで出てきてるもの)を全通り試せば間に合います。
部分点2
動的計画法(DP)を使用することで間に合います。
つまり、n個のパターンで、集合Xの要素数考える場合は以下のように考えます
- まず、n個のパターンが、1つの文字列に一致するかを調べます。
- 1つの文字列に一致しなかった場合、n個のパターンを2分割します。2分割した後の小さなパターンの集合について、同じようにすべてに一致する文字列集合の要素数を調べます。
- 分割後の小さなパターンの集合に対する文字列集合の要素数の最小値がわかった場合は、メモ化をして結果を使い回します。
- n個のパターンを2分割する方法をすべて試して、その結果の最小値をとれば、集合Xの要素数の最小値が分かります
満点解法
n個のパターンから任意の2つのパターンを比較して常に矛盾を起こさないならば、n個のパターンすべてに対して一致する文字列が存在します。この性質を用いれば文字列の比較回数は、(n * n - 1) / 2回で済みます。
これにより、たとえ文字列が長くても時間内に答えをだすことができます。