Mitsubachiのメモ

組合せ論をしています

Div1 バチャ日記1 - Codeforces Round #485

今回は #485 を走った。C,Dが割と辛かった。
codeforces.com

f:id:Mitsubachi88:20211220113326p:plain

AB2完。C,D,Eは解説AC。

 

A - Fair

制約の 1 \leq s \leq k \leq 100 が露骨にヒントっぽいので多始点BFSを k 回すれば通った。

 

B - Petr and Permutations

転倒数の偶奇とswap数の偶奇は一致するというよくある典型。 O(N \log N) を N \leq 10^6 で2secで出すの、少し攻めすぎじゃない？

 

C - AND Graph

これ面白い。 X \ AND \ Y =0 なら Y が X の否定 \sim X に包含されてる ( AND=Y )という言い換えすら思いつかなかったのは反省。

m 個の頂点集合 S と 2^n 個の頂点集合 T を用意して S_i から T_{\sim a_i} への有向辺を張って、 T_i から T_j に j が i から 1 bit削ってできるなら有向辺を張って、 T_{a_i} から S_i への有向辺を張ると、 S_i から S_j へのパスがあることが A_i \ AND \ A_j =0 と同値になる。

で、 AND は交換則があるので、逆方向のパスも存在するっていうこと。なので、後はDFSなりBFSをすればいい。

のだが、グラフを陽に持つとMLEするので陰に持ちつつDFS内部で次に行ける頂点を探す必要がある。 n \leq 20 にしてほしい。

 

D - Perfect Encoding

問題文の読解が難しい。要約すると

数列 b = \left(  b_1,b_2, \cdots , b_m \right) に対し、 f(b) = \prod b_i とする。 f(b) \geq n を満たす b のうち \sum b_i が最小となるものについて \sum b_i を求めろ。

とりあえず最適な b を考えると、 4 以上があるなら半分ごとに分割して損はないし、 2 が 3 つ以上あるなら 2,2,2 を 3,3 にしても損はしないので、最適解は 2 を 2 つ以下で、残りは 3 という形。

なので、 3^k \geq n を満たす最小の整数 k を求める問題を 3 回解けばいいのだが、 n が 1.5 \times 10^6 桁あるのが難しい。多倍長の掛け算は畳み込みで O(N \log N) でできるので二分探索+繰り返し二乗法で頑張ったのだがTLE。

結論としては、桁数を d とすると \log {}_3 n が d \times \log {}_3 10 の前後になるので、ここの間だけ全探索すればよいという。これでもTLEしたが、原因は数を 10 進数で考えていたからだった。 1000 進数で考えるすなわち 3 桁をまとめて畳み込みすると定数倍高速化が効く。

 

それにしてもきつかった。制約とTLが厳しい。

 

E - Prince's Problem

とりあえず素数ごとに分離する。LCAを考えるとパスの端点を 1 の場合に帰着できる。オイラーツアーの順にセグ木に乗せるテクを使うと数列の範囲に対して \min を取った場合の総和を求める問題になる。

ここで悩んでいたが、数列の値は a の次数なので合計が O(n \log a) になる。これを利用して 1 以上のやつに加算して 1 との \min はただの範囲和として求める。 2 以上のやつに加算して 2 との \min はただの範囲和として求める。というのを繰り返せばよいとなって面白かった。