−目次
AtCoder Beginner Contest 409 F,G問題メモ
F - Connecting Points
問題文
- 2 次元平面上に N 頂点 0 辺のグラフ G があります。頂点には 1 から N までの番号が付いており、頂点 i は座標 (xi,yi) にあります。
- G の頂点 u,v に対して、u,v の距離 d(u,v) をマンハッタン距離 d(u,v)=|xu−xv|+|yu−yv| で定義します。
- また、G の 2 つの連結成分 A,B に対して、A,B の頂点集合をそれぞれ V(A),V(B) としたとき、A,B の距離 d(A,B) を d(A,B)=min{d(u,v)∣u∈V(A),v∈V(B)} で定義します。
- 以下で説明されるクエリを Q 個処理してください。クエリは次の 3 種類のいずれかです。
'1 a b
' : G の頂点数を n としたとき、頂点 n+1 の座標を (xn+1,yn+1)=(a,b) として、G に頂点 n+1 を追加する。'2
' : G の頂点数を n、連結成分数を m とする。- m=1 のとき、
'-1
' を出力する。 - m≥2 のとき、距離が最小である連結成分をすべてマージし、その最小の距離の値を出力する。
'3 u v
' : 頂点 u,v が同じ連結成分にあるならば'Yes
' を、そうでないならば'No
' を出力する。
制約
- 2≤N≤1500
- 1≤Q≤1500
- 0≤xi,yi≤109
- 1 種類目のクエリについて、0≤a,b≤109
- 3 種類目のクエリについて、そのクエリを処理する直前の G の頂点数を n としたとき、1≤u<v≤n
- 入力は全て整数
解法
一見複雑だが、解法は素直。
Heap Queue に、条件を満たすものも満たさないものもとりあえず突っ込んでおいて、
取り出すときにチェックする(条件を満たすものが見つかるまで pop し続ける)という操作は他の問題でもよく出てきがち。
最終的な頂点数の上限は O(N+Q) であり、全頂点間の距離 O((N+Q)2) を求めても十分間に合う。
初期状態で G にある N 頂点の全点間距離をHeap Queue H につっこんでおく。
また、連結状態を Union-Find T で管理する。
クエリ1では、新たに追加された頂点と、今ある n 頂点の距離を H に追加する。
クエリ2では、まだ連結でない頂点対 (i,j) が見つかるまで、H で距離の小さい方からpopし続ける。
見つかったらそれを k とし、T で (i,j) を結ぶ。
その後、H に含まれる最小距離が k である間、追加でpopし続け、その頂点も全部結ぶ。
H が空になるまで見つからなかったら、全て連結ということなので、−1 を出力して終了。
クエリ3は、普通に T 上で (u,v) が連結かを調べる。
以上で O((N+Q)2log(N+Q)) でできる。
G - Accumulation of Wealth
問題文
- 2 以上の整数 N と、0 以上 100 以下の整数 P が与えられます。以下、 p=P/100 とします。
- 数列 A があります。はじめ、A の長さは 1 で、唯一の要素は 1 です。
- 数列 A に対して、以下の操作を N−1 回繰り返します。
- A に現れない最小の正整数を m とする。確率 p で操作 1、確率 1−p で操作 2 を行う:
- 操作 1: A の末尾に m を追加する。
- 操作 2: 1,2,…,m−1 が A に含まれる個数を c1,c2,…,cm−1 とする。1 以上 m−1 以下の整数 k を ck に比例する確率で 1 つ選ぶ。すなわち、確率 ck/∑m−1j=1cj で k を選ぶ。そして、A の末尾に k を追加する。
- 各 k=1,2,…,N について、N−1 回の操作後に A に含まれる k の個数の期待値を mod998244353 で求めてください。
制約
- 2≤N≤105
- 0≤P≤100
- 入力はすべて整数
解法
数式をこねくり回して畳み込みの形に持っていく系問題。
まぁそうだろうなとは思いつつ、どうやったら畳み込みの形になるか分からなかった。
立式
p=P100、q=1−p とする。
E(i,k) を「i 回の操作後の k の個数期待値」とする。E(N−1,k) を各 k につき求めたい。
ひとまず最初から存在する k=1 は別として、k≥2 に対して以下のアプローチを取る。
「① j 回目にはじめて k が追加される確率」と 「② 追加された1個から、残り N−j−1 回の操作で期待値が何倍になるか」を分けて考える。
①は、「j−1 回目までに操作1が k−2 回選ばれた後、j 回目で操作1が選ばれる」という事象なので、以下になる。
- j−1Ck−2pk−2qj−k+1×p
- ただし、j−1<k−2 の場合は 0
②は、k に依らない。k=2 であろうと 3 であろうと、 j 回目に追加された1個が最後までに期待値何個になるかは同じである。
①の「j 回目に始めて k が追加」が発生したという条件の下の E(i,k) を E′j(i) とする。
k は何であっても同じなので省略する。以下が成り立つ。
- E′=E×(①の式)
- E′j(j)=1
i+1 回目に追加されるのが k である確率は、まず確率 q で操作2が選ばれ、 次に i 個の要素から E′j(i) 個ある k が選ばれなければならないので、q×E′j(i)i である。
操作1が選ばれたり、操作2で他の要素が選ばれたときは E′j(i) のままなので、あわせると
- E′j(i+1)=E′j(i)×(1+qi)
となる。この遷移を N−1 回目まで繰り返すと、結局
- E′j(N−1)=N−2∏l=j(1+ql)
となる。E′N−1(N−1)=1 よりはじめて、j=N−2,...,1 と遡るたびに 1+qj を乗算していくことで、 E′j(N−1) を各 j に対して O(N) で求めることができる。
①と②をあわせ、初登場までにかかった操作回数 j によって場合分けして、E(N−1,k) は以下のようになる。
- E(N−1,k)=N−1∑j=1j−1Ck−2pk−2qj−k+1×p×E′j(N−1)
これを各 k に対して求めると答えだが、このままでは O(N2) となる。まだ高速化の必要がある。
形式的冪級数で考えると、二項係数を数式の累乗にまとめられるので、上の式は
- F(x)=N−1∑j=1px(px+q)j−1×N−2∏l=j(1+ql)
- k=2,3,...,N の時の答えは、F(x) の x1,x2,...,xN−1 の係数
となる。
Polynomial Taylor Shift
ここで、Polynomial Taylor Shift というテクニックが使える。
これは、x の N 次多項式 A(x)=a0+a1x+a2x2+...+aNxN と定数 c が与えられたとき、 A(x+c)=b0+b1x+b2x2+...+bNxN と表される (b0,b1,...,bN) を O(NlogN) で求めるテクニックである。
Polynomial Taylor Shift の式変形自体はけんちょん氏の記事に詳しいのでここでは割愛。
ともかく、これができるとして、
- A(x)=N−1∑j=1pjN−2∏l=j(1+ql)xj
- c=qp
とすると、上記の F(x) にも Polynomial Taylor Shift を適用できる。
この式だと、x の係数が1つずれて、x0,x1,...,xN−2 の係数が答えとなる。
最後に、k=1 の時の答えは、全体の答えの総和が N になることを利用してもいいし、 また E′1(N−1) であることを利用して計算してもよい。