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

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

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

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

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

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

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)$ であることを使うと同じように導けます。

2020-01-15

Educational Codeforces Round 80 A から E

A. Deadline

x と d/(x+1) が近いほど値が小さくなりそうなので d の正の平方根の前後を 100000 くらいを探したんだけど、これやるなら 1 から 1000000 を全探索で良かった。

B. Yet Another Meme Problem

b の桁数を L だと仮定する。そうすると与えられた条件は $ab + a + b = a \cdot 10^L + b$ と言い換えられる。式変形すると $a(b+1-10^L)=0$ となる。$a$ は零でないため $b+1-10^L=0$ である。つまり $b=10^L - 1$ である。$b=10^L - 1$ とすると確かに $L$ 桁になっているから、これは解である。$L$ としてありうるものは 1 から 10 しかないため、すべて探しても間に合う。なお各 $b$ に対して $a$ は任意であるから、$b$ としてありうる場合の数に A を掛けたものが答えになる。

C. Two Arrays

これは本番自分が思いついた方法とは異なる。b を反転して a の後ろにつければ、この問題は長さ 2m の数列を数え上げる問題に言い換えられる。これは C(2m+n-1,n-1) 通りある。

D. Minimax Problem

最大値を $x$ 以上にできるかを二分探索する。i 番目の数列に対して集合 $S_i$ を $A_{i,j}$ が $x$ 以上となる $j$ 全体とする。$S_i$ と $S_j$ の和集合が $\{1,2,\ldots,m\}$ となれば i と j は答えである。$S_i$ としてありうるものは 256 通りしかないため、$S_i$ を 256 通り確かめればよい。

E. Messenger Simulator

ある人に着目する。この人を赤い人と呼ぶ。また添字を身長に対応させる。履歴を古いものから新しいものの順で見ていき $n$ 回赤い人が現れたとする。最大値となる候補は履歴に現れる時点か終了時点しかないことに気をつける。1 回目では、履歴の先頭からいままでに赤い人よりも身長の高い人が現れた回数だけ後ろに下がっているはずである。k 回目では、k - 1 回目から k 回目までに現れた人の数だけ先頭から後ろに下がるはずである。

以上を踏まえると、数列のある区間の値の種類数がわかれば解けることがわかる。うまくやると点更新区間和だけで解ける。

2020-01-13

AtCoder Beginner Contest 151

Tasks - AtCoder Beginner Contest 151

A

言語を間違えてしまい 1WA。char 型に一を足すと int 型になることを考えてなくて 1WA。インクリメントなら壊れません。

B

N 掛ける M 引く総和をそのまま出力して 1WA。点数に上下限があることにきづいて修正しましたが、100 点満点だと勘違いして 1WA。

C

定期的に似たような問題が出されるので、AC してない問題の WA は数えないことは印象に残っていました。

D

グラフの直径といいます。木であれば線形時間で解けますが、一般には二乗時間かかると思います。

E

max X の総和から min X の総和を引けば求まります。max X の総和と min の総和は対称的なので、max X を求めることだけ考えます。A を整列しておきます。N 個から K 個選んだときの最大値は、選ばれた数のうちもっとも右側の数です。もっとも右側の数が A[x] であるような組合せは A[1] から A[x-1] までから K - 1 個選ぶ組合せの数だけあるので、A[x] は C(x-1,K-1) 回足されます。これをすべての A[1] から A[N] に対して行えばよいです。

余談ですが A[1] から A[N] までから K 個選ぶ選び方は、「A[x] が最も右側である K 個の選び方」をすべての x=1 から N までをあわせたもの、なので

\begin{align}
\sum_{x=1}^{N} {}_{x - 1}\mathrm{C}_{K - 1} = {}_{N} \mathrm{C}_{K}
\end{align}

という恒等式が成り立ちます。

F

最小包含円の形は二通りあって、ある二点を直径とする円か、ある三点を通る円です。このことから最小包含円の中心の候補は、二点の中点と、三点の外心に限られます。二点の中点はすぐに求められますが、三点の外心はそこまで明らかではありません。

外心は三角形の各辺に対する垂直二等分線の交点です。よって交点が求められればよいです。任意の三角形は平行移動によって原点を頂点にもつ三角形に移せるので、一点が原点のうえにあるような三角形 OAB に対して外心を与えることを考えます。

直交座標

A(a,b), B(c,d) とします。線分 OA の垂直二等分線は $(a,b) \cdot ( (x, y) - (a / 2, b / 2) ) = 0$ です。原点を通りベクトル $(a,b)$ と直交する直線は $(a,b) \cdot (x,y) = 0$ なので、これを $(a/2, b/2)$ だけ平行移動したと考えればよいです。同様にして線分 OB の垂直二等分線は $(c,d) \cdot ( (x, y) - (c / 2, d / 2) ) = 0$ です。この二直線の交点は連立方程式

\begin{align}
ax + by &= \frac{a^2 + b^2}{2} \\
cx + dy &= \frac{c^2 + d^2}{2}
\end{align}

の解になります。クラメルの公式によって

\begin{align}
x = \frac{\begin{vmatrix} \frac{a^2+b^2}{2} & b \\ \frac{c^2+d^2}{2} & d\end{vmatrix}}{\begin{vmatrix} a & b \\ c & d \end{vmatrix}}
\end{align}

\begin{align}
y = \frac{\begin{vmatrix} a & \frac{a^2+b^2}{2} \\ c & \frac{c^2+d^2}{2}\end{vmatrix}}{\begin{vmatrix} a & b \\ c & d \end{vmatrix}}
\end{align}

です。

複素座標

点 A(a), B(b) とします。線分 OA の垂直二等分線は $|z|^2 = |z-a|^2$ です。$|z|^2 = z \overline{z}$ なので $z \overline{a} + \overline{z} a = a \overline{a}$ と書き換えられます。同様に線分 OB の垂直二等分線は $|z|^2 = |z-b|^2$ であり、書き換えれば $z \overline{b} + \overline{z} b = b \overline{b}$ です。$z$ と $\overline{z}$ の連立方程式を解けばよく、クラメルの公式より

\begin{align}
z = \frac{\begin{vmatrix} a \overline{a} & a \\ b \overline{b} & b\end{vmatrix}}{\begin{vmatrix} \overline{a} & a \\ \overline{b} & b \end{vmatrix} }
\end{align}

です。

直交座標だと x と y の両方を解かなければならないのに対して、複素座標だと z だけ解けばいいので実装するのが楽です。

ちなみに本番は検索して出てきた tubo さんのコードを貼りました。

2020-01-11

AtCoder Beginner Contest 150 D. Semi Common Multiple

https://atcoder.jp/contests/abc150/tasks/abc150_d

初項 $A_i / 2$、公差 $A_i$ の等差数列が $N$ 個ある。これらの共通部分を求め、そのうち 1 以上 M 以下のものがいくつあるか求めればよい。ふたつの等差数列の共通部分はまったく存在しないかふたたび等差数列となるかである。そのため等差数列と等差数列の共通部分が求められれば、それを繰り返すのみである。

https://atcoder.jp/contests/abc150/submissions/9411300

2020-01-11

Codeforces 614 Div. 2 A から F

A

ありうる最も左の点と右の点がわかれば、その間の点はすべてありうるので植木算。自分は気づかなかったが、要素数足す一が答え。

B

連続部分列の和の最大値は動的計画法で求められる。この問題では列全体が答えにならないようにしなければならない。そこで前半 $N - 1$ 個と後半 $N - 1$ 個でそれぞれでわけて解くとよい。

C

$a$ と $b$ が互いに素でないとき $a$ と $b$ を最大公約数で割ったものを選んだほうが得であるため、$a$ と $b$ は互いに素であると仮定してよい。このとき $a$ は $X$ の約数となるはずである。よって $X$ の約数 $d$ であり $d$ と $X/d$ が互いに素になるようなもののなかに答えはある。

D

桁数 $L$ 以下であり、長さ $N$ の列 $A$ が与えられたとき最小値を求める問題 $f(L,A)$ を考える。$X$ を上の桁から決めていくことを考える。$L$ 桁目が $0$ であるものを $A_0$ に、$1$ であるものを $A_1$ に振り分ける。このとき $A_0$ が空ならば $f(L - 1, A_1)$ が答え、$A_1$ が空ならば $f(L - 1, A_0)$ が答え、そうでないならば $f(L - 1, A_0)$ と $f(L - 1,A_1)$ のうち小さい方が答えになる。

E

どの区間も互いに包含関係にならない場合を考える。このとき左端で整列すれば右端も整列される。そのため左から見ていくことで解ける。

包含関係にある場合、ある区間に包含されているような区間を消していくと、どの区間も互いに包含関係にならない区間集合が得られる。この区間集合はどのような消し方をしても同じものが得られる。この過程で消された区間は答えを与えることはないため、得られた区間集合だけを考えればよい。

得られた区間集合を $I_1,\ldots,I_n$ とする。$I_k$ に包含されている区間の集合を $ J_1, \ldots ,J_m $ としたとき、$ I_1, \ldots,I_{k - 1},I_{k+1},\ldots,I_n,J_1,\ldots,J_m $ の和集合の連結成分数を数えられればよい。$ J_1,\ldots,J_m $ を列挙するとき $I_{k - 1}$ や $I_{k+1}$ にも包含されているようなものは列挙する必要がないため、$k$ が $1$ から $n$ を動くとき $ m $ の和は $n$ 以下にできる。また連結成分数の計算は $f(I_1,\ldots,I_{k - 1}) + f(I_{k - 1},J_1,\ldots,J_m,I_{k + 1}) + f(I_{k + 1},\ldots,I_{m}) - 2$ でできる。ただし $I_{k - 1}$ や $I_{k + 1}$ が存在しないときは $2$ の部分を適切に減らす。

F

解説を読んでから解いた。これは賢い。

最大公約数を g に固定する。このとき $g, 2g, 3g, \ldots$ だけを見ればよい。g が 1 から 100000 まで動くとき、見ることになる数は 100000 log 100000 個程度であることに気をつける。

最大公約数が 1 の場合を考える。100000 から 1 へと見ていく数を減らしていき、見終えるたびに見た数をスタックに積んでいく。このときスタックの上の方に小さい値が積まれることに気をつける。いま見ている数と互いに素な数がスタックに含まれている場合、その数より上に積まれている値は取り除いてしまってよい。もしもスタックの中に互いに素な数が含まれているのかが高速に判定できればこの問題を解くことができたことになる。

たとえば 12 と互いに素なものの個数は「1 の倍数の個数」引く「2 の倍数の個数」引く「3 の倍数の個数」足す「6 の倍数の個数」で求められる。「k の倍数の個数」が 1 から 100000 のすべての k に対して計算されていれば、たかだか 12 の約数の個数分の足し引きで互いに素なものの個数が数えられる。

計算量解析においては「k の約数の個数」の二乗を 1 から 100000 まで足したものが現れるが 26324772 であるため間に合う。

pekempey's blog

AtCoder Beginner Contest 152 F. Tree and Constraints