ACL Contest 1 総括 - kaage精進録

問題ごとに解説を書くのは面倒なのでコンテスト単位で書いてみる。

A Reachable Towns

ある方向に遷移可能なら逆にも当然遷移可能なので、Union-Find Tree で管理したい気持ちになる。ただ、張れる辺は明らかに $O(N^2)$ でしか抑えられないので、必要な辺以外張らない必要がある。とりあえず、全部の頂点を $x_i$ でソートして $y_i$ のみ考えてみる。

ここで、頂点 $i$ から $j$ 、$j$ から $k$ （ただし $i\lt j\lt k$）にそれぞれ辺を張れるとき、$i$ から $k$ までも辺を張れるので、$j$ から辺を張ることは考えなくていい。これを利用して、$x_i$ の順に頂点を見て行って張れるところに全部辺を張ると、張る辺は $O(N)$ 本で済むようになる。

あとは張るべき辺を抽出するパートだが、これは std::set などで $y_i$ の値を管理しておけば、全体の計算量は $O(N\log N)$ で解ける。

ACコード

B Sum is Multiple

$$ \sum_{i=1}^ki=\frac{1}{2}k(k+1) $$ なので、$k(k+1)$ が $2N$ で割り切れればよい。

とりあえず $2N$ の約数を全列挙してやって、それをペアごとに $k,k+1$ に割り当ててみる。この約数を定数倍して差が $1$ にできればいいので、これは約数のペアを $(d_0,d_1)$ として、不定方程式 $d_0x-d_1y=1$ を解く作業に相当する。これは拡張ユークリッドの互除法を使うと解けるので、これで $k$ の最大値を調べてやればよい。 $k=0$ となるときの場合分けが多少面倒だが、これで解けた。

ACコード

C Moving Pieces

制約がフローに見えるので、フローを考える。

まずは各マスに駒を与えて、これを適切に流して移動した先のマスから駒が出ていけばよい。最適化したいのは駒を移動させる回数なので、最小費用流が使える。具体的には、移動できる各マスの間に、容量が十分大きくコストが $-1$ の辺を張って、あとは駒の入り口と出口を用意して流してやればよい。

ACコード

D Keep Distances

最適解を求めるだけの問題ならダブリングで解けて、これとセグ木二分探索とかを頑張って使うのだろうけど、わからず。

E Shuffle Window

ぱっと見手のつけようがないが、とりあえず数のペアごとに転倒数の期待値を考えてやる。左の駒の index を $L$, 右の駒の index を $R$ とすると、この2つの順番が入れ替わらない確率は次のようになる。

$R\leq K$ のとき

$$ \frac{1}{2} $$

$L\leq K\lt R$ のとき

$$ 1-\frac{1}{2}\left(\frac{K - 1}{K}\right)^{R-K} $$

$K\lt L$ のとき

$$ 1-\frac{1}{2}\left(\frac{K - 1}{K}\right)^{R-L} $$

これを利用して期待値を計算する。まず、一番上の場合については、元がどのような順番でも必ず期待値は $\frac{1}{2}$ なので、$\frac{K(K - 1)}{4}$ になる。 2つ目の場合は、累積和で $K$ 以下の場所についての数の分布を管理しながら、$R$ を全探索して対応する $L$ の数をかけてやればよい。 3つめの場合は、BIT を2つ持って、$L$ では毎回 BIT の対応する場所に

$$ \frac{1}{2}\left(\frac{K - 1}{K}\right)^{-L} $$ を正負別に足して、$R$ で大小関係に対応するように区間を選んで $$ \left(\frac{K - 1}{K}\right)^{R} $$ をかけて加算してやれば、定数項 $1$ 以外は管理できる。

最後に、定数項の $1$ は、数列の index が $K$ 以上の部分においての転倒数と同じだけ結果に寄与するので、これを足してやればよい。

ACコード

F Center Rearranging

知らん

感想

A, B の数学問を早めに解いて E に時間が回せたので良かった。