K - Sum is One Editorial
by 
otoshigo
Editorial for printing
以下、\(G\) における頂点 \((i,j)\) を単に \((i,j)\) と表すことにします。
部分点解法
辺の数が \(\Theta(N^3)\) となることがあり、愚直に辺を繋ぐと間に合いません。そこで、超頂点の考え方を用います。
\(j=2,3,\cdots,N-1\) の対し、集合 \(L_0\), \(R_0\) を \(L_0\coloneqq\{i\mid A_i=0,i<j\}\), \(R_0\coloneqq\{k\mid A_k=0,j<k\}\) と定義します。
\(A_j=1\) の場合を考えます。任意の \(i\in L_0,k\in R_0\) に対し \((i,j)\) と \((j,k)\) の間には辺が張られるため、 \(L_0\neq\emptyset,R_0\neq\emptyset\) のとき \(\{(i,j)\mid i\in L_0\}\cup\{(j,k)\mid k\in R_0\}\) に属する頂点はすべて \(G\) の同一連結成分に属します。これより \(L_0\neq\emptyset,R_0\neq\emptyset\) のときは、辺の張り方を以下のように変更しても連結成分数は変わりません。
- 超頂点 \(S_{1,j}\) を用意し、任意の \(i\in L_0\) に対して \(S_{1,j}\) と \((i,j)\) の間に辺を張る。また、任意の \(k\in R_0\) に対して \(S_{1,j}\) と \((j,k)\) の間に辺を張る。
\(A_j=0\) の場合についても同様に超頂点を用いることで、辺の本数を \(O(N^2)\) まで減らすことができます。詳細は実装例を参考にしてください。
以上より、この問題を \(O(N^2)\) または \(O(N^2\alpha(N))\) で解くことができます。
満点解法
孤立点とそうでない連結成分に分けて考えます。
孤立点の個数
以下の条件のいずれかを満たすとき、かつそのときに限り、\((l,r)\) は孤立点となります。
- \(A_l=1,A_r=1\)
- \(A_1=A_2=\cdots=A_l=1,A_r=0,A_{r+1}=A_{r+2}=\cdots=A_N=1\)
- \(A_1=A_2=\cdots=A_{l-1}=1,A_l=0,A_r=A_{r+1}=\cdots=A_N=1\)
- \(A_1=A_2=\cdots=A_l=A_r=A_{r+1}=\cdots=A_N=0\)
この性質を用いると、孤立点の個数は \(O(N)\) で求めることができます。
孤立点以外の連結成分の個数
\(1\leq j\leq N\) と \(x,y\in\{0,1\}\) について、\(G\) の頂点からなる集合 \((x,j,y)\) を以下のように定義します。このとき、 \((x,j,y)\) に属する頂点はすべて \(G\) の同一連結成分に属します。
\[ (x,j,y) \coloneqq \begin{cases} \{(i,j)\mid i<j,A_i=x\}\cup\{(j,k)\mid k>j,A_k=y\} & (\exist i<j,\exist k>j, \text{s.t.}\, A_i=x,A_k=y,x+A_j+y=1) \\ \emptyset & (\text{otherwise}) \end{cases} \]
孤立点以外の連結成分の個数は、\((x,j,y)\) を用いた以下のグラフ ( \(G^{\prime}\) とおく) の連結成分の個数と一致します。
- 頂点集合は \(\{(x,j,y)\mid 1\leq j\leq N,x,y\in\{0,1\},(x,j,y)\neq\emptyset\}\) である。
- \((x,j,y)\neq(z,k,w),(x,j,y)\cap(z,k,w)\neq\emptyset\) を満たすとき、かつそのときに限り、頂点 \((x,j,y)\) と頂点 \((z,k,w)\) の間に辺が張られている。
証明
\(G^{\prime}\) の連結成分の個数を \(\alpha\) とし、連結成分を \(G^{\prime}_1,\cdots,G^{\prime}_{\alpha}\) とする。また、\(G^{\prime}_t\) の頂点集合を \(V^{\prime}_t\) とし、\(U^{\prime}_t\) を \(V^{\prime}_t\) の要素すべての和集合とする。
ここで、\(U^{\prime}_1,\cdots,U^{\prime}_{\alpha}\) が相異なる \(G\) の孤立点以外の連結成分の頂点集合であり、孤立点以外の連結成分は他に存在しないことを示す。
以下の \(4\) つのことが示せればよい。
- 任意の \(G\) の孤立点でない頂点 \(v\) に対し、ある \(t\) \((1\leq t\leq\alpha)\) が存在して、\(v\in U^{\prime}_t\) が成り立つ。
- 任意の \(s,t\) \((1\leq s<t\leq\alpha)\) に対し、\(U^{\prime}_s\cap U^{\prime}_t=\emptyset\) が成り立つ。
- 任意の \(t\) \((1\leq t\leq\alpha)\) に対し、\(U^{\prime}_t\) の要素はすべて \(G\) の同一連結成分に属する。
- 任意の \(G\) の孤立点でない頂点 \(u, v\) \((u \neq v)\) に対し、\(u\) と \(v\) が \(G\) の同一連結成分に属するならば、ある \(t\) \((1\leq t\leq \alpha)\) が存在して \(u, v \in U^{\prime}_t\) が成り立つ。
(1 の証明) 任意の \(G\) の孤立点でない頂点 \(v\) に対し、ある \(G^{\prime}\) の頂点 \((x,j,y)\) が存在して \(v\in(x,j,y)\) を満たす。\((x,j,y)\) を含む \(V^{\prime}_t\) は一意に存在し、この \(t\) に対して \(v\in U^{\prime}_t\) が成り立つ。
(2 の証明) \(U^{\prime}_s\cap U^{\prime}_t\neq\emptyset\) となると仮定する。このとき、ある \(G\) の頂点 \(v\) が存在して、\(v\in U^{\prime}_s,v\in U^{\prime}_t\) を満たす。これより、ある \(G^{\prime}\) の頂点 \((x,j,y),(z,k,w)\) が存在して、\(v\in(x,j,y),(x,j,y)\in V^{\prime}_s,v\in(z,k,w),(z,k,w)\in V^{\prime}_t\) を満たす。\(G^{\prime}_s\) と \(G^{\prime}_t\) は異なる \(G^{\prime}\) の連結成分であるため、\((x,j,y)\neq(z,k,w)\) でなければならない。ここで、\((x,j,y)\) と \((z,k,w)\) はともに \(v\) を含むため、共通部分が空でない。よって \(G^{\prime}\) において 頂点 \((x,j,y)\) と 頂点 \((z,k,w)\) の間に辺が張られるが、これは \(G^{\prime}_s\) と \(G^{\prime}_t\) が異なる \(G^{\prime}\) の連結成分であることに矛盾する。
(3 の証明) 任意の \(G^{\prime}\) の頂点 \((x,j,y),(z,k,w)\) に対し、\((x,j,y)\cap(z,k,w)\neq\emptyset\) のとき、\((x,j,y)\cup(z,k,w)\) は \(G\) の同一連結成分に属する。任意の \(t\) \((1\leq t\leq\alpha)\) に対し、\(U^{\prime}_t\) は \(G^{\prime}\) の頂点の和集合で表されるため、\(U^{\prime}_t\) の要素はすべて \(G\) の同一連結成分に属する。
(4 の証明) ある \(s, t\) \((s \neq t)\) が存在して \(u \in U^{\prime}_s, v\in U^{\prime}_t\) となると仮定する。\(u\) と \(v\) は \(G\) の同一連結成分に属するため、\(U^{\prime}_s\cup U^{\prime}_t\) の要素はすべて \(G\) の同一連結成分に属する。\(U^{\prime}_s \cap U^{\prime}_t=\emptyset\) より、ある \(u^{\prime}, v^{\prime}\) \((u^{\prime} \neq v^{\prime})\) が存在して \(u^{\prime} \in U^{\prime}_s, v^{\prime} \in U^{\prime}_t\) を満たし、\(G\) 上で頂点 \(u^{\prime}\) と頂点 \(v^{\prime}\) は辺で結ばれている。これより、ある \(G^{\prime}\) の頂点 \((x,j,y)\) が存在して、\(u^{\prime} \in (x,j,y)\) と \(v^{\prime} \in (x,j,y)\) が成り立つ。\((x,j,y)\) は \(G^{\prime}_s\) と \(G^{\prime}_t\) のいずれか一方に属するため、\(u^{\prime}, v^{\prime} \in U^{\prime}_s\) または \(u^{\prime}, v^{\prime} \in U^{\prime}_t\) が成り立つが、これは \(U^{\prime}_s \cap U^{\prime}_t=\emptyset\) に矛盾する。
以上より、\(G\) の孤立点以外の連結成分の個数は \(\alpha\) であり、\(G^{{\prime}}\) の連結成分の個数と等しいことが示された。（証明終）
\(G^{\prime}\) の異なる頂点 \((x,j,y)\) と \((z,k,w)\) \((j\leq k)\) は、以下の条件を満たすとき、かつそのときに限り、共通部分が非空となります。
- \(j<k\) かつ \(A_j=z,A_{k}=y\)
この性質から、以下のように辺を張っても \(G^{\prime}\) と連結成分数は変わりません。
- \((x,y)=(0,0),(0,1),(1,0)\) に対し、
- \(A_j=1-x-y,(x,j,y)\neq\emptyset\) を満たすような \(j\) の最小値を \(m\) とし、最大値を \(M\) とする（そのような \(j\) がなければ \(m=N+1,M=0\) とする）。\(k=m+1,\cdots,N\) に対し、\(A_k=y,(1-x-y,k,x)\neq\emptyset\) を満たすならば、頂点 \((x,m,y)\) と 頂点 \((1-x-y,k,x)\) の間に辺を張る。また、\(k=1,\cdots,M-1\) に対し、\(A_k=x,(y,k,1-x-y)\neq\emptyset\) を満たすならば、頂点 \((x,M,y)\) と 頂点 \((y,k,1-x-y)\) の間に辺を張る。
このようにして \(G^{\prime}\) の連結成分を管理すると、孤立点以外の連結成分の個数を \(O(N)\) で求めることができます。
以上より、この問題をテストケースごとに \(O(N)\) で解くことができます。連結成分の管理に Union Find を用いて \(O(N\alpha(N))\) となっても十分高速です。
posted:
last update: