Loading [MathJax]/jax/output/CommonHTML/jax.js

目次

AtCoder Regular Contest 163 C,D問題メモ

AtCoder Regular Contest 163

C - Harmonic Mean

C - Harmonic Mean

問題

解法

N=5 のサンプルの答え 3 4 5 6 20 をOEISで検索してみると、 A216975 が見つかり、「エジプト式分数」というキーワードを得る。

作り方に決まったものはないが、単位分数1つを2つに置き換える簡潔な方法として、以下がある。

N=1 の時は A=(1,)N=2 の時は解無しで、 N=3 以降は(かぶりと、上限に気をつければ)再帰的に置き換えていくことで必ず構築できそう。

N=3 の時の解 A=(2,3,6) からはじめて、被らないように変換していきたい。

小さい方から変換していくと、かぶりの管理が難しそう。
(ある時点では a+1A に存在するので a の変換ができなかったが、 a+1 が変換されて無くなったので a も変換できるようになった、という差し戻しが連鎖的に発生する)

そこで、大きい方から変換していくことにする。

この方法だと一度変換に失敗した数はずっと失敗する(差し戻しが発生しない)ので、 次に何に対して変換を行えばよいかの管理が楽。

N=500 で試してみて問題なかったので、制約の範囲内ではとりあえず大丈夫。
N=31623 まではできたので、結構余裕がある)

Python3

D - Sum of SCC

D - Sum of SCC

問題

スマートな解法

公式Editorialの解法。

トーナメントでは、全ての頂点間に有向辺があるので、強連結成分を縮約した上でのトポロジカルソートを考えると、その順番は一意に決まる。
自分より下流にある頂点への辺は、全て 上流→下流 の向きになっている。

  ②  →  ①  →  ③
 ④⑤ --------→  ⑥

逆に、「2つの頂点集合 A,B があって、A の頂点と B の頂点を結ぶ全ての辺は AB の向きに張られている」場合、 B から A に行くことは不可能であり、強連結が途切れているといえる。

このような「強連結成分の境界」に着目する。
境界の個数を数えると、それに良いグラフの個数 (N(N1)/2M) を加えたものが答えとなる。

主客転倒の考え方を用いると、以下のようになる。

主客転倒すると、全ての辺が AB の向きである時点で A,B 間に確実に境界が1つ存在し、 他に AB が複数の強連結成分に分けられようが関係ないところが計算を楽にする。

頂点番号の小さい順に A,B どちらに入れるかを確定させていくDPで求められる。
具体的な遷移や実装は公式Editorial参照。

地道な解法

ABC-F~G などに出てくるような解法を繰り返す・組み合わせることでも、地道にやっていけば解けなくはない。

以下のDPをおこないたい。

j で数える昇辺の範囲は、確定した i 個に少なくとも一方の端点を持つ辺とする。 (未処理の Ni 個間に張られる辺は対象外ということ)

                     未処理頂点
○→○ → ○←○ → (○○○)
↑×↓ →  ↘↗  →
○←○ →   ○   →

|--- i個 j本-------|

このような状態から、次に来る強連結成分を未処理頂点から切り出すことで遷移していく。
別途、以下の情報があればよい。

残り頂点の番号が具体的に分からなくても、残り頂点内での辺が昇辺かどうかは相対的な順序で決まるので、p,q さえ同じなら同じになるところがポイント。

もらうDPで考えて、DP[iq,jr] から新規で q 頂点、r 昇辺の強連結成分を1つ決めて DP[i,j] にする方法は、

このようになる。

普通に i,j,q,r でループを回すと、i,q は頂点数 O(N)j,r は辺数 O(N2) なので O(N6) となってしまうが、 もらうDPの形にすると j,r を固定する部分は畳み込みができるので、O(N4logN) になる。

さて、では解けたかというとそうでもなく、DP2 を求めるのが難しい。

DP2 を、以下の2つに分けて求める。

この2つがあれば、DP2p,q ごとに r,s を添字とした畳み込みにより O(N4logN) で求まる。

DP4は、“スマートな解法”と似た感じで、小さい頂点から「q 個に含まれる側と、未処理側のどちらに入れるか」を確定させるDPでできる。O(N4)

DP3は、なんかOEISをあさると A339590 が見つかる。
さらにそこからこんな 論文 が見つかる。

それによると、DP3は以下の要領で計算できる。

u を形式的な変数とした形式的冪級数 tn(u) を、以下で定義する。(nk)q はq-二項係数とする。

t1(u)=1,t2(u)=0 として、n の小さい方から計算できる。すると、[ur]tq(u)(※ tq(u) における ur の係数)が、DP3[q,r] に相当する。

これで全ての情報が計算できて、解けました。めでたしめでたし。

DP3の式のひもとき

(1+u)(n2) は普通の二項係数を作る式なので、u0,u1,u2,... の係数は「n 頂点のトーナメントで昇辺が 0,1,2,... 個のものの個数」を表す。

そこから、内部を2つ以上の強連結に分けられるものを引いている。

重複しないよう、一番上流の強連結成分を k 頂点と固定して、残りを自由に決めている感じ。

なので、Σの中でのあと1項 (nk)u が、「n 頂点から k 個選ぶパターン数、ただし選んだ頂点→選ばれなかった頂点間にできる昇辺の個数毎」を示していることになる。

これって、DP4 と一緒じゃん! 知らないうちに同じことをしてしまっていたらしい。

noshi氏のサイトによると、q-二項係数は以下の性質があるらしい。

「昇辺の個数ごとに n 頂点から k 個選ぶパターン数」も、この問題に言い換えられることが確認できる。

Python3