AtCoder Beginner Contest 162 感想

https://atcoder.jp/contests/abc162

28位。F問題で2、3個飛ばしするDP書いたらバグっちゃった。

A,B,Cはいうことなし。Dはj-i≠k-jがなければ(赤の数)×(緑の数)×(青の数)で求まるので、そこからj-i=k-jであるものを引けばいい。

E問題は約数包除(?)ですぐ解ける。最大公約数が x になるような組の個数 F(x) を求めることを目標にする。これが求まれば答えは x F(x) の総和になる。直接 F(x) を計算するのは難しいため、まず公約数が x の倍数であるような組の個数 G(x) を求め、ここから F(x) を復元する。G(x) の計算は容易であり、F(x) への復元も包除原理によって達成できる。

F問題。自分は偶数個と奇数個で場合分けをした。この先では、選んだものを黒で塗り、選ばなかったものを白で塗ることにする。

偶数個のとき

2個ずつのまとまりにする。あるまとまりを見たとき、白と黒がひとつずつになっているはずである。

f:id:pekempey:20200412232736p:plain

さらに少し考えると次の形以外ありえないことがわかる。よって偶数個のときは累積和で解ける。

f:id:pekempey:20200412233057p:plain

奇数個のとき

偶数個のときと同じように2個ずつのまとまりにする。ただし一つ余るはずである。

f:id:pekempey:20200412233441p:plain

あまったものは白であるとしてよい。あまりはかならず奇数番目になるが、かならず奇数番目の白が存在する。全て黒だと取り過ぎになってしまうので。

このとき選んだものは次のような形をしているはずである。よってDPで解ける。

f:id:pekempey:20200412234842p:plain

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 155 F. Perils in Parallel

F - Perils in Parallel

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

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

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

類題があります。

AtCoder Beginner Contest 152 F. Tree and Constraints

F - Tree and Constraints

条件が一つだけの場合を考えてみます。つまりある頂点からある頂点の道の上に黒辺が少なくとも一つある、という条件のもとでの数え上げを考えます。全体から条件を満たさないものを引くことを考えると解けます。

条件が二つある場合を考えます。この場合も同じように考えられます。まず全体から、一つ目の条件を満たさないものを引き、二つ目の条件を満たさないものを引きます。このとき一つ目の条件と二つ目の条件を両方満たさないものを重複して引いてしまったので、一つ目の条件を満たさず二つ目の条件も満たさないものを足せばよいです。

条件が三つ以上も同様ですが、二つ以下の場合に比べると直感的には捉えづらいです。そこで、条件アと条件イを満たすものは「条件イを満たすもの」から「条件アを満たさず条件イを満たすもの」を引いたものである、という基本的な考え方を使って条件を言い換えていきます。このことを使うと「アかつイかつウ」は「イかつウ」引く「アでないかつイかつウ」となります。「イかつウ」は「ウ」引く「イでないかつウ」となります。「イでないかつウ」は「イでない」引く「イでないかつウでない」になります。「ウ」は「全体」引く「ウでない」となります。つまりこれを繰り返すと、最終的に否定命題の連言となります。このことから、一般に条件が連言で表される数え上げは、否定命題の連言の数え上げが解ければよいということになります。否定命題の連言としてありうる二の「命題数」乗の命題がちょうどひとつずつ現れます。その符号は連言で繋がれている命題の数が偶数ならば正号、奇数ならば負号となります。

このようなものの数え方を包除原理と呼びます。天下り的に証明する方法もありますが、ここでは地道に導きました。条件が連言の場合のほかに、選言で表されている場合も似たような方法がとれます。

よってこの問題は、「ある頂点からある頂点の間の辺がすべて白辺である」の形の複数の文の連言を条件とする問題を解けばよいです。これは易しい問題です。

次は、ある頂点間を結ぶ道上の辺の列挙について考えます。深さ優先探索幅優先探索などのアルゴリズムによって調べることができますが、次のようにもできます。まず適当な頂点を根として根付き木を作ります。このとき各頂点に対して、その頂点の親と、根からの距離、つまり深さを覚えておきます。二頂点の深さを比べて、深い方の頂点を親に持ち上げるということを繰り返します。このようにするとやがて二頂点は合流しますが、この二頂点が辿ってきた道を併せたものがちょうど二頂点を結ぶ道になっています。これをプログラムにすると次のようになります。

int x, y;
while (x != y) {
  if (dep[x] > dep[y]) swap(x, y);
  y = par[y];
}

以上より解くことができました。包除原理は再帰的に書けます。このように書くと自然数の範囲で計算できます。

let g (xs : nat list) : nat = (* xs の否定の連言 *)

let rec f (xs : nat list) (ys : nat list) : nat =
  match xs with
  | [] -> g ys
  | (x :: xs) -> f xs ys - f xs (x :: ys)

包除原理の例

包除原理を使う例としてオイラー関数を取り上げます。$1$ 以上 $n$ 以下の整数のうち $n$ と互いに素な整数の個数はオイラー関数 $\phi(n)$ と呼ばれます。たとえば 120 に対してオイラー関数の値を計算してみます。$120=2 \times 2 \times 2 \times 3 \times 5$ です。つまり「2 で割り切れない」かつ「3 で割り切れない」かつ「5 で割り切れない」ものを数えればよいです。これは連言で表されているので、包除原理より否定命題の連言に言い換えられます。たとえばそれには「2 で割り切れ、かつ 3 で割り切れる」がありますが、これは「6 で割り切れる」と同値なので、$120 / 6 = 20$ 個あります。同様に考えれば答えは

\begin{align}
\phi(120) = 120 - \frac{120}{2} - \frac{120}{3} - \frac{120}{5} + \frac{120}{2 \times 3} + \frac{120}{2 \times 5} + \frac{120}{3 \times 5} - \frac{120}{2 \times 3 \times 5}
\end{align}

です。さらにこの式は簡単にできて

\begin{align}
\phi(120) = 120 \left(1 - \frac{1}{2}\right) \left( 1 - \frac{1}{3}\right) \left( 1 - \frac{1}{5} \right)
\end{align}

になります。余談ですが、$a$ と $b$ が互いに素のとき $\phi(ab)=\phi(a)\phi(b)$ であることを使うと同じように導けます。