ferinの競プロ帳

競プロについてのメモ

チーム練習 (05/27)

2019 ICPC Asia-East Continent Final をやった

A は気づいたら通ってた

M

i^k = j となるような i,j の組はあまりない
2,4,8,\ldots3,9,27,\ldots のように素数のべき乗に分割する
各集合の要素数O(\log n) 個でbit全探索の要領で全部見てもok

E

universeなグラフ: 頂点1とn以外は次数が2で分岐しないグラフで、並列な同じ長さのパスの集合で構成される

このグラフの最大流は \sum_{path P} \min_{e \in P} (eの重み) となる
一つのパスに全て重みを移した場合、流量が最適となる
この最適な流量は \lfloor 流量の総和 / パスの長さ \rfloor となる
この最大流を達成するときに操作回数の最小化を行いたい

i 番目のパスに流れる流量が x_i となるようにする
+1する操作回数だけ数えたとしても、x_i の和が最適になるように定めているので、-1する操作の方の回数についてもつじつまが合う
i 番目のパスの操作回数は \sum_{w  \lt  x_i} x_i -(辺重みw) となるのでこの回数を最小化すればよい

この操作回数は x_i に対して大体等差数列のようになっている
x_i が辺重みを超えるタイミングでのみ公差が1増える
公差が小さいものから順にできるだけ採用する貪欲法を行えば操作回数の最小化ができる
この貪欲法はpriority_queueに公差などを挿入しておき、小さいものから順番に取っていけばよい

H

n/2 個以上の要素を取ろうと思うと、隣接する要素は距離2以下となっているものが大半を占める
したがって距離2以下の要素の公比のうち要素数n/4 以上のもののみが公比の候補となる
これによって公比の候補を限定することができる

あとは公比を固定したときの最大の部分列の長さをpolylog(n)で求めたい
これは \text{dp} \lbrack i \rbrack  = (iを最後に取ったときの部分列の長さの最大) とすればよい
遷移は \text{chmin}(\text{dp} \lbrack j \rbrack , dp \lbrack i \rbrack +1) (jv_j=v_i*rとなる最小のj) とすればよい

C

f(1)=g(1)=1 だと f^{\text{mod}}(n) = \epsilon(n) となるらしい
ただし、\epsilon(n)n=1 のときのみ1でそれ以外の場合0となる関数
証明できない

これを用いると g,k が与えられたとき f \equiv g^{k^{-1}}\ (\text{mod} M) となる
g^{k^{-1}} はダブリングで求められるので O(n\log n\log M) で答えがわかる

なんで検索なしでこれがこんな解かれてるんだ…