pekempeyのブログ

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

Ad Infinitum 17

https://www.hackerrank.com/contests/infinitum17/challenges

Primitive Problem

原始根のひとつを $g$ としたとき、 $p-1$ と互いに素な $k$ に対して $g^k$ も原始根になる。このことから $\phi(p-1)$ 個の原始根が存在することがいえる。

最小の原始根は、$i=1$ から順に確かめればすぐに見つかる。 順に確かめるにしても、位数の計算は高速に行わなければならない。位数の計算は、位数が $p-1$ の約数にしかならないことを使えば高速にできる。

The Matchstick Experiment

  • サイズ 1 の連結成分の個数
  • サイズ 2 の連結成分の個数
  • サイズ 3 の連結成分(L型)の個数
  • サイズ 3 の連結成分(I型)の個数

の期待値をそれぞれ求めて足し合わせればいい。

たとえばサイズ 1 の連結成分の個数の期待値は、期待値の線形性を用いて、(0,0)が孤立する期待値、(0,1)が孤立する期待値、(0,2)が孤立する期待値…、のように分解して、それぞれの期待値の総和を取ることで求められる。

四隅・隅・内部の 3 パターンに分類することで、期待値の計算は O(1) でできる。

解き方は自明かもしれないが、解きたくはならない。

V-Cutting Tool

もともと V が一個あったら、その V と4 回交差するようにカットできる。4 回交差するということさえ分かれば、オイラーの定理 $v-e+f=1$ を使って面の個数を求められる。

V の先端も頂点としてみると楽なので頂点として数える。もともと n 個のVがあれば、カットしたとき 4n 回交差するので 3+4n 個頂点が増える(3は交差に関係なく増える分)。辺の数は交差するたびに 2 ずつ増えるので 4+8n 本増える。

108 という制約が目に入ったので、108 回ループを回すことにした。

Birthday Triplets

$6 \le f_1 \le 15 \times 10^3$ という制約があるので、$f_1$ を全探索して見つける。数列の総和は行列累乗とかきたまさ法とかでできる。

ちなみに $s_i$ を $i$ 次の基本対称式としたとき、一般に以下のような漸化式が成り立つ。

$$f(n)=s_1f(n-1)-s_2f(n-2)+s_3f(n-3)-\cdots$$

$s_i$と$f_i$の関係も一般化できて、

$$ \begin{align} s_1&=s_0 f_1 \\ 2s_2&=s_1f_1-s_0f_2 \\ 3s_3&=s_2f_1-s_1f_2+s_0f_3 \\ 4s_4&=s_3f_1-s_2f_2+s_1f_3-s_0f_4 \\ \vdots \end{align} $$

である。詳しくはhttp://www.geocities.jp/ikuro_kotaro/koramu/taisyo.htmを参考にしてほしい。

実は cheflong で $f_1,f_2,f_3,\ldots$ が与えられるので $f_n$ を求めよという一般的な問題が出題されている。自分はそれを解いていたため、今回はやることがなかった。

また、別の余談であるが、きたまさ法で総和を求めるときは

  • a[n]=s[n+1]-s[n] という関係式を使って s[n] に関する漸化式を立て直す
  • 1+x+x2+...+xn mod M(x) を計算

の 2 通りの方法がある。前者の方が速いとは思うが、どちらも O(n2 log m) ではある。前者はその場ですぐに書けるものなので、今回は後者を実装してみた。

Divisor Exploration II

たとえば $p^2 q^3$ の約数の総和は

$$ (1+p+p^2)(1+q+q^2+q^3) $$

で計算できる。今回の式はほとんど同じ方法で計算できて、以下のようになる。

$$(s(1)+s(p)+s(p^2))(s(1)+s(q)+s(q^2)+s(q^3))$$

$p$ と $q$ が互いに素であれば $s(pq)=s(p)s(q)$ が成り立つ、つまり $s$ が乗法的関数であることを利用している。

Number of M-Coprime Arrays

もし仮に $m=p^e$ の形だった場合、$1,p,1,1,p^2,1,\ldots$ のように $p$ が連続しないような長さ $n$ の数列を求める問題になる。この問題は1階の連立漸化式で解けるので、行列累乗をすればいい。この解の値を $f_n(e)$ としよう。

$m=p^a q^b$ という形だった場合、答えは $f_n(a) \times f_n(b)$ となる。なぜかというと、$p$ が連続しない数列 $a_i$ と、$q$ が連続しない数列 $b_i$ をそれぞれ持ってきて、各要素の積を取った数列 $a_i b_i$ を作ることで、答えになるすべての数列を構成できるためである。

よって、 $ m=p_1 ^{e_1}p_2 ^{e_2}p_3 ^{e_3} \cdots $ のように素因数分解したときの指数部分の列 $(e_1,e_2,e_3,\ldots)$ を求められれば解くことができる。ここで重要なのが、必要なのは指数だけであり、具体的な素因数を求める必要はないことである。

指数列を求める計算は $O(m^{1/3})$ 時間でできる。まず $m^{n/3}$ 以下の素数を用いて $ m $ を素因数分解する。これでは完全に分解できないケースがあるが、分解できなかった部分が $1$, $p$, $p^2$, $pq$ のいずれかの形をしていることだけは分かる。指数列を得るにはこの4種類のどれであるかを判別するだけでいい、というのが高速化の鍵である。

判定はどのようにやればいいだろうか。$1$ は自明である。$p^2$ は平方数判定を行えば分かる。$p$ は高速な素数判定(Miller-Rabin法など)を行えば分かる。$pq$ は前 3 つのどれにも当てはまらないかどうかで見分けられる。

以上のことを踏まえることで無事解くことができた。

余談だが、ロー法と呼ばれるアルゴリズムがあり、これを使うことで $n$ の非自明な約数のひとつを $O(n^{1/4})$ 時間で見つけられる(らしい)。実際走らせてみると確かにすぐに見つけてくれる。これを使うと $O(n^{1/4})$ 時間で指数列を求められる(計算量を信じるなら)。

二問目は愚痴りたい。