Codefestival 2017 Finals Eに対する雑な考察

この問題の線形代数による考察を記しておきます。線形代数が何もわからない。

まずbjxzjaを26を法とするベクトルとして考えます。


S =
	\left(\begin{array}{c}
		1 \\
		8 \\
		23 \\
		25 \\
		9 \\
		0
    \end{array}
    \right)

これをあるベクトル群の一次結合によって表現出来るかを考えます。

ここで、回文の基底を考えると以下のようになります。


palindrome =

	a_1
	\left(\begin{array}{c}
		1 \\
		0 \\
		\vdots \\
		0 \\
		1 \\
    \end{array}
    \right)

    +

    a_2
    \left(\begin{array}{c}
		0 \\
		1 \\
		\vdots \\
		1 \\
		0 \\
    \end{array}
    \right)

    + \dots

各操作も同様にベクトルで表すと次のようになります。


v_i =
	\left(\begin{array}{c}
		0 \\
		\vdots \\
		0 \\
		1 \\
		\vdots \\
		1 \\
		0 \\
		\vdots \\
		0
    \end{array}
    \right)


回文の基底と操作ベクトルを合わせたベクトル群の一次結合により S が表現することが出来たなら答えはYESになります。

式で書くと次のようになります。


S = palindrome

	+ 

	\sum b_i v_i

さて、 v_iは密なので拡大行列を簡約化するコストは大きいように見えます。しかし、先に差分行列(累積行列も差分行列も正則なのは簡単に確かめられます)を掛けてやることでこれらは疎になります。

疎行列に対する簡約化のコストは小さいので十分間に合います。 Z/26Zは体でないので諸所が面倒に見えますが解けます(ほんまか)(多分、列ベクトルに注目すると1, -1をちょうど同じ数だけ含むので逆元を持たないことが問題にならないと思う)(ユニモジュラ行列っぽい何かに思うからなんか性質良くなれ良くなれ)。

想定解のUnionFindを使う方法は、連結した頂点数 = rank(それを結んだ辺(ベクトル)で構成される行列)となるということに注目するのだと思います(この辺がよくわからない)。これはつまり連結している頂点のコストの合計が変わらないなら自由に再分配出来ることを意味します。