yukicoder No.940 ワープ ε=ε=ε=ε=ε=│;p>д<│

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

いくつかの組合せ問題は多項式によって解くことができます。これがどういうことか、簡単な例を取り上げて説明します。サイコロを二個振ったとき目の和が k となる場合の数を求める問題を考えましょう。いきなりですが次の式を考えます。

\[ (x+x^2+x^3+x^4+x^5+x^6)(x+x^2+x^3+x^4+x^5+x^6) \]

これを展開すると

\[ x^2 + 2x^3 + 3x^4 + 4x^5 + 5 x^6 + 6 x^7 + 5 x^8 + 4 x^9 + 3x^{10} + 2x^{11} + x^{12} \]

になります。さて $x^k$ の係数は何になっているでしょうか。実はサイコロの目の和が k になる場合の数と一致しています。なぜかを詳しく説明しませんが、このように多項式の係数を見ることでいくつかの問題は解くことができます。

さて、このことを踏まえて今回の問題を多項式で表すと

\begin{align}
[x^X y^Y z^Z] \sum_{k=0}^{X+Y+Z} \left( \frac{1}{(1-x)(1-y)(1-z)} - 1 \right)^k
\end{align}

を計算する問題になります。ここで $[x^X y^Y z^Z] f(x,y,z)$ は多項式 $f(x,y,z)$ の $x^X y^Y z^Z$ の係数を表します。この式の組合せ的意味を考えるには、$1/(1-x)=1+x+x^2+\cdots$ と置き換えた方がいいでしょう。なお $1/(1-x)$ は一般には多項式ではなく形式的冪級数と呼ばれますが、ここでは多項式と呼びます。形式的冪級数に慣れていない人のために補足を入れておきます:$[x^2] 1/(1-x)$ を計算する問題を考えましょう。この式には $x^2$ の項がどこにもないため答えは 0 だと思うかもしれませんが、実際には 1 となります。$1/(1-x)$ は $1-x$ の形式的冪級数における乗法逆元と呼ばれるもので、数 II で習う分数式とは異なる概念なのでこのようなことが起こります。これは有理数における 1/2 と有限体における 1/2 が異なるという話と同じで、表記や規則は似ているけどあくまで違うものです。詳しいことは英語版の wikipedia にまかせます。大学で習うテイラー展開を知っていればあまり不思議に思わないかもしれません。

Formal power series - Wikipedia

形式的冪級数の概念を知るには Wikipedia で事足りると思います。Wikipedia 以外の文献としてはNotes にも挙げられている Niven Ivan の Formal Power Series がわかりやすいと思います。高校数学で習う概念の類推でだいたいは式操作できると思いますが、形式的冪級数の合成に関しては注意が必要です。たとえば 1/(1-x) に 1-x を合成すると $(1-x)^0 + (1-x)^1 + (1-x)^2 + \cdots$ となって定数項が $1+1+1+\cdots$ となってしまいます。この場合、定数項の値が定まらなくなってしまうので、このような合成は避けないといけません。厳密に言えば無限個の項を持つ形式的冪級数に対して定数項がゼロでない形式的冪級数を合成してはいけません。

さて、問題に戻りましょう。冒頭の式を計算するにあたって次のことを大切にします。

\[ [x^a y^b z^c] \left( \frac{1}{(1-x)(1-y)(1-z)} \right) ^n = {}_n \mathrm{H}_a \cdot {}_n
\mathrm{H}_b \cdot {}_n \mathrm{H}_c \]

これは $[x^k]1/(1-x)^n = {}_n \mathrm{H}_k$ であることと、$[x^a y^b] f(x)g(y)=([x^a] f(x))([y^b] g(y))$ であることから導けます。前者は式の組合せ的意味から分かることです。後者は明らかです。もちろん分解しなくても組合せ的に直接導けます。

ここから先は $f=1/(1-x)(1-y)(1-z)$ とします。これにより計算対象は $[x^X y^Y z^Z] \sum_{k=0}^{X+Y+Z} (f-1)^k$ に変わります。この式は等比数列の和の形をしているので、数学 B で習う等比数列の和の公式を使いまとめられます。

\[ [x^X y^Y z^Z] \sum_{k=0}^{X+Y+Z} (f-1)^k = [x^X y^Y z^Z] \frac{(f-1)^{X+Y+Z+1} - 1}{(f-1) - 1} \]


右辺の分子ですが、二項定理で展開すると $\square + \square f + \square f^2 + \cdots + \square f^{X+Y+Z+1}$ の形になります。$X+Y+Z+1$ 次式を一次式 $f - 2$ で割るというのは数学 II で習う筆算を使えば $O(X+Y+Z)$ で計算できます。最後に係数を取り出せば良くて、

\[ [x^X y^Y z^Z] (\square + \square f + \square f^2 + \cdots + \square f^{X+Y+Z+1}) = \square [x^X y^Y z^Z] 1 + \square [x^X y^Y z^Z] f + \square [x^X y^Y z^Z] f^2 + \cdots + \square [x^X y^Y z^Z] f^{X+Y+Z} \]

です。これで解けました。和を $X+Y+Z$ まで取りましたが、無限に広げることもできますし、そちらの方が自然かもしれません。ただし僕が知る限りでは計算が大変になります。

AtCoder Beginner Contest 144 F - Fork in the Road

https://atcoder.jp/contests/abc144/tasks/abc144_f

問題文には書いていないが制約に書いてある $s_i < t_i$ という条件から与えられるグラフは閉路を持たないことが分かる。この性質を使えば動的計画法によって期待値を求められる。それは以下の式によって得られる。

\begin{align}
E_i = \frac{1}{|N(i)|} \sum_{ j \in N(i)} (E_j + 1)
\end{align}

この式を計算するには $O(M)$ 掛かるため、ある辺を消してみて再び求めなおすと $O(M^2)$ 掛かってしまう。ここで諦めずに、ある辺を消してみて再び求めなおす処理をもっと速く行えないか考えてみよう。実は適切な前計算をしておくと辺一本あたり $O(1)$ で再計算できる。

辺 $(a,b)$ を消したときの期待値の変化量 $E_1' - E_1$ に着目する。実はこの変化量は $E_a' - E_a$ の変化量に比例する。これは上で書いた式の線形性に基づく。よってこの比例定数さえ知っていれば $E_1'-E_1$ は $E_a'-E_a$ から知ることができる。この比例定数を求める最も単純な方法は $E_a=1$ として上に書いた式を計算することだろう。計算し終えたときの $E_1$ が比例定数になっている。これを各頂点に対して行えば合わせて $O(NM)$ 掛かる。これでこの問題は解くことができるが比例定数を求める部分はもっと高速にできて $E_1=1$ として辺を逆向きに上記の計算をすればいい。よく考えると同じものを求めていることが分かるので、これで計算量 $O(M)$ になる。



このグラフが閉路を持たないことは次のように確かめられる。閉路が $v_1, v_2, \ldots, v_n, v_1$ があるならば矛盾することを示す。このときこのグラフの性質から $v_1 < v_2 < \cdots < v_n < v_1$ であり $v_1 < v_1$ となる。$v_1 < v_1$ かつ $v_1 \ge v_1$ より矛盾する。

この性質を持つような頂点の並べ方がトポロジカルソートであり、トポロジカルソートができるグラフは閉路を持たない、ということを知っていれば閉路を持たないことがすぐに分かるかもしれない。問題文に書いてくれていても良さそうな気がするが、引っかかったことで印象が強くなったと思えば悪くはなかったのかもしれない。


The problem statement doesn't say this graph is a DAG, but we can prove that this graph is a DAG. So we can solve this problem by using DP. The update formula is as follows.

\begin{align}
E_i = \frac{1}{|N(i)|} \sum_{ j \in N(i)} (E_j + 1)
\end{align}

We need O(M) time to calculate this formula, so straight forward solution takes O(M^2) time. We shouldn't give up at this point, this approach can be faster than $O(M)$ per edge. That is, O(1) algorithm exists.

Focus on the difference $E_1' - E_1$ when edge (a,b) is removed. Actually, this difference $E_1' - E_1$ is proportional to the difference $E_a' - E_a$. So if we already know the proportionality constant, we can easily obtain the new answer from $E_a' - E_a$. The easiest way to calculate the constant is to use the recurrence relation similar to the above formula. Needless to say, its requires $O(NM)$ in total, which is fast enough in this problem. However, we can speed up this solution more efficiently by doing similar DP on the reversed graph. I won't explain the details, but I believe that you can understand it by yourself. The true time complexity is only $O(M)$.

AtCoder Beginner Contest 144 E - Gluttony

https://atcoder.jp/contests/abc144/tasks/abc144_e

積の最大値を $x$ 以下にできるかどうかを二分探索する。$F_i$ は降順に並んでいるものと仮定する。このとき各 $F_i$ と対となる値は $\lfloor x/F_i \rfloor$ 以下になるはずである。

よって$A$ を自由に並び替えていいとき $\sum_{i=1}^{N} \max(0, A_i - \lfloor x/F_i \rfloor)$ としてありうる最小の値を求める問題が解ければいい。この最小の値が $K$ 以下ならば $x$ 以下にすることができる。結論をいうと、この値を最小にするには $A_i$ を昇順に並べるのがいい。そのことは以下のような図から分かる(操作後の大小関係が入れ替わるものはもっと値を小さくできるから大小関係が入れ替わる操作がいらない旨を示す図がこの次に入る)。

二分探索の各判定に $O(N)$ 掛かるので全体の計算量は $O(N \log (\max A_i \max F_i))$ である。



ずっと積の最大値じゃなくて和を最小化する問題だと思ってたんだけど、サンプル3を見つめていたら答えが12になるはずがなくて勘違いに気がついた。


We can find the maximum product $x$ by using binary search. Suppose that $F_i$ are sorted in descending order. Then, the value correspond to $F_i$ is must be less than or equal to $\lfloor x/F_i \rfloor$.

Therefore, we only have to solve this problem: We can rearrange the array $A$ arbitrarily, then please find the minimum possible $\sum_{i=1}^{N} \max(0, A_i - \lfloor x/F_i \rfloor)$. If this value is smaller or equal to $K$, we can achieve $x$. Actually, if A is sorted in ascending order, this value becomes the minimum. That's why if the order of $A_i$ and $A_j$ are switched, we can construct more efficient solution by swapping the role of the both.

Each check in binary search can be done in $O(N)$, so the entire time complexity is $O(N \log \square)$.

AtCoder Beginner Contest 144 D - Water Bottle

https://atcoder.jp/contests/abc144/tasks/abc144_d

まず水をなみなみ入れておいてそれを傾けていったとき水の量がちょうど $X$ になる角度を求めればいい。どこまで傾ければいいかは二分探索によって求められる。二分探索するには傾けた角度に対してどのくらいの水が残るのかを知らなくてはならない。傾けた角度を $\theta$ としたときの水の量を求めよう。求め方は $\tan \theta < b/a$ を満たすかで変わる。これは水面がちょうど対角線の上に来るときの前後で求め方が変わるということである。条件を満たすなら以下の式になる。

f:id:pekempey:20191029011237p:plain:w400

条件を満たなさないなら以下の式になる。

f:id:pekempey:20191029011255p:plain:w400

以上でこの問題を解くことができた。式を見ればすぐわかるように逆正接関数で直にも解ける。



最初は二分探索書いたんだけど3ケースだけ落ちて戸惑ってた。誤差が厳しいのかと思って結局逆正接関数を使って解いたんだけど、誤差が厳しいわけがないし結局式が間違ってた。解説放送みたいに辺の長さが求まることに気づけば二分探索する気にはならないんだけど慣れでやってしまう。

図 https://github.com/pekempey/figure/tree/master/ABC144C_water_bottle



Binary Search. If we know the amount of the water remaining in the bottle when tilt theta, we can find the theta such that the amount becomes exactly X. Let's try to find the amount. First, we notice that there are two states, which switched by the condition tan theta < b/a. If this condition is satisfied, the amount can be expressed by the following formula.

f:id:pekempey:20191029011237p:plain:w400

If this condition isn't satisfied, the amount can be expressed by the following formula.

f:id:pekempey:20191029011255p:plain:w400

So we have solved this problem. By the way, where does this condition come from? Actually, tan theta = b/a means the water surface is just on the diagonal line.

AtCoder Beginner Contest 143 E Travel by Car

https://atcoder.jp/contests/abc143/tasks/abc143_e

Because I hear that O((n + m) log n) Dijkstra is slow, I tried that too. That's indeed slow. I hear that fibonacci heap is faster than binary heap, so I tried that too. That's indeed fast. But does that conclude fibonacci heap is better than binary heap? I doubted that's true. Then, I noticed that this implementation of binary heap doesn't use decrease key. So I tried binary heap with decrease key, then it become faster than fibonacci heap.

method time link
binary heap without decrease key 1252 ms link
fibonacci heap 178 ms link
binary heap with decrease key 117 ms link

To compare performance, I made the following graph: For $j - i \ge 2$, connect i and j with weight $5000(N-i) + \mathrm{rand}(0, 4999)$, and for $j-i=1$, connect i and j with weight 0. In this graph, decrease key will be called N(N-1)/2 times. Moreover, the values in the heap will be shuffled for each iteration. For $N=5000$, the result becomes as follows.

method time
fibonacci heap 384 ms
binary heap with decrease key 201 ms
binary heap without decrease key 1539 ms
straight forward 94 ms

https://ideone.com/IVsxkl