ferinの競プロ帳

競プロについてのメモ

JAG夏合宿2019 Day2

J

各操作で左崎さんは $a_1$ ，右男さんは $a_n$ を必ず1減らす
相手の値を減らせるなら減らすべきなので数列に0が存在しないときは[1,n]を選択するべき
よって $\text{min}(A_i)$ 回[1,n]を選択する操作を繰り返す
この操作をした後はお互いa_1とa_nを減らし合って先に0になった方が負けになるゲーム
よって $(a_1 > a_n)$ か $(a_1 = a_n$ かつ minが奇数 $)$ なら勝てる

$a_1 > a_n$ → $\frac{(S+1)^n - (S+1)^{n-1}}{2}$ 通り
$a_1 = a_n$ かつ minが奇数 → $f(S) = S^(n-1) - (S-1)^(n-1) + … - 2^(n-1) + 1^(n-1)$ f(x)はn-1次の多項式っぽいのでn点を使用してf(S)を多項式補完で求める

https://onlinejudge.u-aizu.ac.jp/beta/review.html#JAGSummerCamp19Day2/3884679

変形すると $\sum_{i=0}^{S} i^{n-1}$ の形になる
$\sum_{i=0}^{n-1} i^k$ はベルヌーイ数がわかっていれば $O(k)$
ベルヌーイ数の前計算は $O(k^2)$

https://onlinejudge.u-aizu.ac.jp/beta/review.html#JAGSummerCamp19Day2/3884834

C

s[i]のsuffixとs[j]のprefixが一致する最大の文字数(=w(i,j))の分削減できる
頂点を2n個並べた二部グラフをつくって文字列i → 文字列j に重みw(i,j)の辺を貼って最大二部マッチング
これは最小費用流を使えばできる

w(i,j)はkmpとかで求まる

https://onlinejudge.u-aizu.ac.jp/beta/review.html#JAGSummerCamp19Day2/3886334

F

グラフの最大独立集合 = 線グラフの最大マッチング
最大マッチングのサイズはtutte行列でO(n³)で計算可能

https://onlinejudge.u-aizu.ac.jp/beta/review.html#JAGSummerCamp19Day2/3886596

残りは解けたら…