読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Round #391: A問題からF問題

http://codeforces.com/contest/757

A. Gotta Catch Em' All!

s に現れる各文字の出現頻度 f を求めておき、min(f[B], f[u]/2, f[l], f[b], f[a]/2, f[r]) を出力すればいい。

B. Bash's Big Day

あらかじめ各値の出現頻度 f を求めておく。gcd が x であるような取り方の最大は f[x]+f[2x]+f[3x]+...で求められる。すべての 2≦x≦106 に対してこの値を求めたとしても、調和数の発散オーダーは対数的なので 106 log 106 程度のループ回数で計算できる。

C. Felicity is Coming!

i と j が交換できるとき、すべてのジムにおいて i と j の出現個数は同じでなければならない。i の出現回数のベクトルを (ジム 1 での i の個数, ジム 2 での i の個数, ジム 3 での i の個数, ...) としておけば、このベクトルが等しいタイプ同士は交換可能であるといえる。

等価比較ができれば十分なので、ローリングハッシュを用いる。誕生日のパラドックスを意識して、衝突しないように気を付けよう。

D. Felicity's Big Secret Revealed

n が非常に小さいのがポイント。現れる最大の値は、計算してみると 20 までしかない。よって dp[ i文字処理した ][ 現れた値の集合 1..20 ]:=パターン数として DP できる。MLE しそうに見えるが、int 型であれば 300 MB 程度なので問題ない。

実行時間も自分のコードは 499 ms だったので、かなり余裕があると思う。

E. Bash Plays with Functions

補足:関数 $f$ が乗法的であるとは、互いに素な $a$, $b$ に対して $f(ab)=f(a)f(b)$ が成り立つことを意味する。

なんとなく $f_1(pq)$ を求めてみると

$$ \begin{align} f_1(pq) &=f_0(1)+f_0(p)+f_0(q)+f_0(pq) \\ &=f_0(1)+f_0(p)+f_0(q)+f_0(p)f_0(q) \\ &=(f_0(1)+f_0(p))(f_0(1)+f_0(q)) \end{align} $$

であることが分かる。このことから察するに、$f_1$ は乗法的である。 帰納的に考えれば、一般に $f_r$ も乗法的である。

乗法的関数の計算は素因数分解が役立つ。

$$f(p^a q^b r^c)=f(p^a)f(q^b)f(r^c)$$

しかも、今回の関数は素因数が何であるかは関係なく、その指数にのみ値は依存する。したがって、あらかじめ $f_r(p^e)$の値を動的計画法で求めておけば、あとは素因数分解するだけとなる。

素因数分解はそれなりに高速に出来たほうがいい。エラトステネスの篩の要領で n が持つ素因数のひとつを求めておけば、無駄なく素因数分解を行える。

F. Team Rocket Rises Again

最短路 DAG を考えると、DAG のある頂点を消したとき、根から到達不可能になる頂点の最大数を求める問題となる。

dominator tree の定義を読んでみると、実は dominator tree の最大の部分木のサイズがそのまま答えであることが分かる。

動作原理については理解してないので、sigma さんのブログにあるものをお借りした。

全体的に解法そのものがあっさりしている。F問題はライブラリゲーすぎて何も言えない。