8問abcは知らないこと、勉強してこなかったことを学べるので嬉しい
■A - Bitwise Exclusive Or
a xor c = b
a xor a xor c = a xor b
c = a xor b
■B - Booby Prize
idxつけてsort
■C - Reorder Cards
座圧。
■D - Takahashi Tour
オイラーツアー
■E - Stronger Takahashi
もったいないことをした。
問題を読むとどう見ても01bfs
0も1もpush_frontしているせいでtleしているのを
方針ミスだと思い、気がつくのに15分消費。。。。
■F - Common Prefixes
Suffix ArrayとLCP Arrayを全く知らなかった。
Suffix Array：
文字列 Sの suffix を辞書順に並べたものをSの何文字目以降からなる文字列かを持った数列
例：aacabのsuffixは aacab, acab, cab, ab, b
これをソートするとaacab, ab, acab, b, cabなので(0,3,1,4,2)を得る。
LCP Array：
辞書順で隣接するsuffixの類似度を得る。
Suffix Arrayが計算済みならO(|S|)で計算ができる。
上の例だと(1,1,0,0)が得られる。
ここまでが前提知識として必要。
以下、問題文で使われているf(Sa,Sb)を類似度としてそのまま扱う。
辞書順でソートされている文字列a,b,cに対して
f(a,c) = min(f(a,b),f(b,c))が成り立つことがわかる。
なので、区間minがわかればf(Si,Sj)が計算できる。
また、ソートとされている辞書順の連続する要素のfは、先に考えたLCP Arrayそのもの。
問題で求める必要があるのは
以下、g(i,j):=min(ai,ai+1,,,,,,,,aj-1)として(aはLCP Array)
ans[k] = f(s1,sk) + f(s2,sk) + .....f(sk-1,sk) + f(sk,sk) + f(sk,sk+1)+ ........f(sk,sn)
なので
ans[k] = g(1,k) + g(2,k) +.......g(k-1,k) + g(k,k+1) + g(k,n) + f(sk,sk)
を求めればいい。
また
ans[k+1] = g(1,k+1) + g(2,k+1) +.......g(k,k+1) + g(k+1,k+2) + g(k+1,n) + f(sk+1,sk+1)
であり
前半部分にのみ着目すると
ans[k]_bef = g(1,k) + g(2,k) +..........g(k-1,k)
ans[k+1]_bef = g(1,k+1) + g(2,k+1) +....g(k-1,k+1)+g(k,k+1)
これはstackなりpriority queueを使って計算していけばいい。
後半パートはreverseして同じようにやればいい。
■G - Connectivity 2
殆どできていたのに、少し足りてなかった。
部分集合の部分集合の列挙がO(3^n)で出来るのは、
過去のabcにも出ているし、典型90にも、edpcにも出ている。
f(s):=sを頂点集合とする連結部分グラフの個数
g(s):=sを頂点集合とする部分グラフの個数
と答えは
ans[i] = Σf(s)*g(V＼S)となる(但しSは{1,i}を部分集合として含む集合)
fとgの求め方を考える
明らかにgのほうが条件がゆるいのでgを先に考える。
g(s)は辺がどちらもsから生えている辺の数をcとすると2^cなのは明らか
fを考える。
fはgを厳しくしたものなので
f(s) = g(s)-?の形になる。
正確には、
f(s) = g(s)-{頂点集合がsであり、非連結なグラフの個数}である。
引いている部分をどうやってかんがえるかがこの問題の肝になる
sに含まれている頂点vを一つ選んで固定する。
{頂点集合がsであり、非連結なグラフの個数}は全て、
vを含む連結集合と、一つ以上の集合になるので
f(s) = g(s)-Σf(t)*g(s＼t)となる(v∈t,t!=s)
これは、最初に書いた通りO(3^n)で求められるので解くことが出来る
fをgから求めるときにvを固定することが思いつかなかった。
