Codeforces Round #391: A問題からF問題
http://codeforces.com/contest/757
- A. Gotta Catch Em' All!
- B. Bash's Big Day
- C. Felicity is Coming!
- D. Felicity's Big Secret Revealed
- E. Bash Plays with Functions
- F. Team Rocket Rises Again
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_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 さんのブログにあるものをお借りした。