東大理系数学1998後期第3問改

もしかしたら新規性ある解法かもしれなかったので作ってみました。

$A$ のうち、最初から存在していた要素を $o$ とおき、数列 $L,R$ を用いて $A$ を $L,(o),R$ の結合という形で表します。

この時、$L$ の要素と $R$ の要素はどちらも片方の挿入の際にもう片方の要素を変化させません。また、$o$ は最初から存在しているため、$L$ と $R$ のどちらの要素を変化させることもありません。

よって、$L$ のみを考えた時の操作および、$R$ のみを考えた時の操作は、それ単体で行っても同じ数列 $L,R$ を得るような操作となります。(最初に追加される要素は代わりに最初から存在しているものとし、また空の数列に対しては考えません)

また、$L$ の部分の操作を完全に無視した場合の操作について $o$ が変化する回数と $R$ の部分の操作を完全に無視した場合の操作について $o$ が変化する回数の和が、本来 $o$ が変化する回数となります。よって、この $2$ つの偶奇は $A$ が問題文の条件を満たす場合等しくなければならないことがわかります。

これをもとに次のような動的計画法を考えることができます。

• $DP[i][j][k]$ は、長さ $i$ の数列 $X$ を得るような操作方法であって、$X$ の要素が全て $0$ であり、かつ上記の $R$ として $X$ を考え $L$ として空の数列を考えた時 $o$ が最終的に $j$ になり、かつ上記の $L$ として $X$ を考え $R$ として空の数列を考えた時 $o$ が最終的に $k$ になるようなものの個数である。ただし、$i=0$ の場合も便宜上考え、この場合は $o$ はどちらも最終的に $0$ になるため、$j=k=0$ である場合のみ $1$ つあるとする。

これは次のように計算することができます。

• $DP[0][0][0]=1$
• $DP[0][0][1]=DP[0][1][0]=DP[0][1][1]=0$
• $DP[i+1][j][k]=\sum_{l=0}^{i}((DP[l][1-j][0]\times DP[i-l][0][1-k]+DP[l][1-j][1]\times DP[i-l][1][1-k])\times \binom{i}{l})$

よって、この問題を $Ο(N^2)$ で解くことができました。

ちなみに、$DP[3\times m][0][0]$ もしくは $DP[3\times m+1][1][1]$ という形のもののみが正になることが帰納法によって証明できるためこれは $1$ 次元の動的計画法にすることができ、またその証明はそのまま元の問題の解法とすることができます。