Codeforces #630 - pekempey's blog

A Exercising Walk

ｘとｙは独立に考えてよい。どんな移動方法であっても最終位置は同じである。隣接する２マスをジグザグ動くことで、始点から終点へ一直線に移動することができる。これがもっとも無駄のない動きである。

B Composite Coloring

ある集まりの最大公約数が１でないというのは、ある整数が存在して、その集まりに属するすべての要素がその整数の倍数であるということと同じである。２の倍数の集まり、３の倍数の集まり、５の倍数の集まり、のように素数のうち小さい方から集まりを作っていくと、１１番目の集まりは３１の倍数の集まりとなる。３１の次の素数は３７であり、３７×３７は１０００より大きいから、どの入力された整数も３１以下の素因数をもつ。よって解けた。

C K-Complete Word

汎用的な方法をとった。ｉ番目とＮーｉ＋１番目が等しく、ｉ番目とｉ＋Ｋ番目が等しいため、ユニオンファインドを使ってｉ番目とＮ－ｉ＋１番目、ｉ番目とｉ＋Ｋ番目を繋ぐ。このとき各連結成分が同じ文字になればいい。

D Walk on Matrix

２の１７乗をＡとする。このとき［［Ａ＋ｋ　Ａ　Ｋ］［Ｋ　Ａ＋Ｋ　Ｋ］］とすると、間違ったＤＰで計算される値は０になり、本当の答えはｋとなる。

E Height All the Same

白黒の市松模様に塗る。各マスの高さの偶奇がすべて一致している状態からは完成状態に移れる。そのため各マスの偶奇だけに着目すればいい。

白と黒のマスが同数であるとき、白の総和と黒の総和の偶奇が等しいことが必要十分条件になる。まず白高さの総和と黒高さの総和の偶奇は不変である。完成できるならば等しいことは不変量から明らかである。逆をしめす。任意のますアとますイの偶奇をそれぞれ反転できる。。実際にどうするかというと、アからイへの道アカキクケコイをとり、アカ、カキ、キク、クケ、ケコ、コイのような操作をすればいい。するとアとイだけが反転する。これを繰り返せば高さの偶奇を一致させることができる。

白と黒のマスが同数でないとき、つまり奇数×奇数のとき、すべての状態から完成状態に移れる。奇数マスが偶数個あれば、奇数マスをすべて偶数マスに変えればよい。偶数マスが偶数個あれば、偶数マスをすべて奇数マスに変えればよい。これは白と黒が同数のときの構成方法と同様にできる。

本質的に難しいのは白と黒が同数のときである。色イの上に高さタのものがいくつあるかを［イタ］と書くことにすると、答えは［白偶］×［黒偶］＋［白奇］×［黒奇］である。［白偶］の求め方だけ考えよう。白マスがＮ個あり、ＬからＲの間に奇数がＡ個、偶数がＢ個あるとすると［白偶］は

\begin{align}
\binom{N}{0} A^0 B^N + \binom{N}{2} A^2 B^{N-2} + \binom{N}{4} A^4 B^{N-4} + \cdots
\end{align}

である。

\begin{align}
(A+B)^N = \binom{N}{0} A^0 B^N + \binom{N}{1} A^1 B^{N-1} + \binom{N}{2} A^2 B^{N-2} + \cdots
\end{align}

と

\begin{align}
(-A+B)^N = \binom{N}{0} A^0 B^N - \binom{N}{1} A^1 B^{N-1} + \binom{N}{2} A^2 B^{N-2} - \cdots
\end{align}

を足して２で割ればいい。［白奇］は全体から［白偶］を引けば求まるから、これで解けた。

別の解法としてこんなのものある。多項式 $f(x)=(x^L + \cdots + x^R)^{N}$ の偶数次の係数の和が求められれればいいから、$(f(1)+f(-1))/2$ を計算する。こっちの方が計算しやすいと思う。

F Independent Set

これは単に面倒なだけ。