Codeforces #630

https://codeforces.com/contest/1332

A Exercising Walk

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

B Composite Coloring

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

C K-Complete Word

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

D Walk on Matrix

2の17乗をAとする。このとき[[A+k A K][K A+K K]]とすると、間違ったDPで計算される値は0になり、本当の答えはkとなる。

E Height All the Same

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

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

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

本質的に難しいのは白と黒が同数のときである。色イの上に高さタのものがいくつあるかを[イタ]と書くことにすると、答えは[白偶]×[黒偶]+[白奇]×[黒奇]である。[白偶]の求め方だけ考えよう。白マスがN個あり、LからRの間に奇数がA個、偶数がB個あるとすると[白偶]は

\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}

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

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

F Independent Set

これは単に面倒なだけ。

AtCoder Beginner Contest 159 感想

https://atcoder.jp/contests/abc159

f:id:pekempey:20200322225112p:plain

F 問題。$F_i=1+x^{A_i}$ とする。多項式 $G_i$ を次のように定める。

\begin{align}
G_i = (F_i) + (F_i \times F_{i-1}) + (F_i \times F_{i-1} \times F_{i-2}) + \cdots + (F_i \times \cdots \times F_1) = \sum_{j=1}^i \left( \prod_{k=j}^{i} F_k \right)
\end{align}

右端が $i$ のときは $G_i$ の $x^S$ の係数が答え。$G_{i+1} = (G_i + 1) F_{i+1}$ である。$S$ 次式と $1$ 次式の掛け算は $O(S)$ で計算できる。$S$ 次を超えた項は切り捨ててよい。よって全体の計算量は $O(SN)$。

C 問題は L/3 って書いて切り捨てられてしまった。最初、体積が与えられて辺の長さの和を最大化しろだと思ってて、立方体が答えだと一瞬思ってしまった。冷静になると違う。

B 問題は前半が回文、後半が回文は確かめたんだけど、全体が回文になるときを忘れてた。

AtCoder Beginner Contest 156 F - Modularness

見てすぐに苦手な問題だと理解したけど、結果としては思いつけたし良かった。

https://atcoder.jp/contests/abc156/tasks/abc156_f

まず D の各項を M で割ったあまりに置き換える。ただし割り切れた場合は 0 ではなく M としておく。このようにしても答えは変わらない。このとき数列の値を数直線に描くと次のようになる。

f:id:pekempey:20200222230644p:plain

m の倍数をまたいだとき、次の項は前の項以下になり、そうでなければ次の項は前の項より大きくなる。つまり何回 m の倍数をまたいだかが分かれば答えがわかる。末項以下の m の倍数はすべてまたぐはずなので、末項を求めて m で割ればア≧イである個数は求められる。あとは全体からこれを引けば答えである。

はじめにさりげなく D の各項を M で割ったあまりに置き換えた。これは桁あふれなどの対策とは異なり、それ以上の重要な性質が得られている。

AtCoder Beginner Contest 155 F. Perils in Parallel

F - Perils in Parallel

以下は公式解説とほとんど同じですが、捉え方がすこしだけ異なります。

スイッチのオフとオンをそれぞれ0と1とします。ある範囲のスイッチを切り替えるというのは、法を2としてある範囲に1を足すことに言い換えられます。ある範囲に値を足すという操作は、階差数列の上ではある二要素に値を足すという操作に変わります。また数列のすべての要素が0であるという条件は、階差数列の要素がすべて0であると言い換えられます。このことを踏まえ、階差数列の上で議論をすることにします。

階差数列の各要素を頂点とし、この操作によって変化する二要素を辺で結んだグラフを考えます。値が1である頂点の上にコマを置くことにしましょう。このときこの操作は、頂点上のコマを隣接頂点に動かしていく操作だと捉えることができます。ただし移動先にすでにコマがある場合は、この二つは消滅するものとしてください。このように考えると、コマが消えるときはかならず二つずつ消えるので、各連結成分ごとにコマは偶数個ずつでなければならないことがわかります。一方で、偶数個であればコマを動かしていってすべてが消せるのは明らかです。具体的なやり方としては、各連結成分に対して適当な全域木を作り、コマを根に向かって持ち上げていくというのがあります。

類題があります。

yukicoder No.980 Fibonacci Convolution Hard

https://yukicoder.me/problems/no/980

もとの数列の母関数を二乗したものが 2000000 項目までわかればよい。もとの数列の母関数が分数の形で書けるので、二乗しても分数の形で書ける。分子と分母が求まったら、分数の形から無限和の形に書き換えればよい。これは自然数多項式の割り算の筆算と同じようにできる。下ではフィボナッチ数の母関数 $x^2 / (1-x-x^2)$ に対して筆算を行っている。

f:id:pekempey:20200214112701j:plain