CodeChef October Challenge 2016

Chef and Keyboard

作れる長方形をh×wとすると、h は c の約数になる。なので、cの約数を列挙してn×mに収まるかを判定すればいい。

Chef and Three Dogs

軌道は速度に依存しないし、三角形のサイズが変わっても相似になる。なのでサンプルの答えから弧長は 1000s かなぁとか思ったけどそんな訳がない（サンプルの答えは絶対誤差1e-6をいいことに滅茶苦茶になってた）。

適当に投げてもダメだったので、s=1,v=1のケースを数値的に計算してみる。やってみたら 0.666 くらいになったので 2/3 かなと思って提出したら AC した。ひょっとして有名な問題なんだろうか。

証明

エレガント云々は諦めて微分方程式で殴る。解くべき微分方程式は簡単なもので、微分方程式を立てる作業が難しい。

速度は意識せず軌道だけ求めよう。極座標で考えた方が解きやすそうなので、軌道を $r=r(\theta)$ とする。原点は正三角形の中心とする。$r(\theta+\Delta\theta)$ がどうなるのかを考えてみよう。

以下の図を頼りに $r(\theta+\Delta\theta)$ を計算してみる。

f:id:pekempey:20161012140042p:plain:w400

その結果を用いて次のような関係式がわかる。

$$ \frac{r(\theta+\Delta\theta)-r(\theta)}{\Delta\theta}= r\frac{1}{\cos\Delta\theta+\sqrt{3}\sin\Delta\theta}\left(\frac{1-\cos\Delta\theta}{\Delta\theta}-\sqrt{3}\frac{\sin\Delta\theta}{\Delta\theta}\right) $$

極限を取れば以下の微分方程式が現れる。

$$ \frac{dr}{d\theta}=-\sqrt{3}r $$

$r(0)=1$ とすれば、$r=e^{-\sqrt{3}\theta}$ となる。どうやら対数螺旋のようだ。

$r:0\to1$ で積分すれば経路長が得られる。$dL=\sqrt{(r d\theta)^2+dr^2}=\sqrt{r^2(d\theta/dr)^2+1}dr$ であることを用いて積分すると経路長は次のようになる。

$$ \int_{C} dL=\int_{0}^{1} \sqrt{r^2\left(-\frac{1}{\sqrt{3}r}\right)^2+1} \;dr=\frac{2}{\sqrt{3}} $$

辺の長さを $s$ として考え直してみると、経路長は $2/3 s$ になり正しいことが示された。

Chef and Two String

good かどうか判定する代わりに、1→Nのパスがあるかを判定する。文字列に対してパスは一意に決まるはずなので同じ結果が得られる。

パスを数える際は入次数と出次数に着目すると DP しやすい。始点・終点以外はかならず入次数と出次数が 1 になる。本来はこれに加えて連結であるという条件が必要であるが、今回は連結でないようなものは作れそうもないことが実験で分かる。

DP テーブルは bitDP 的に dp[ pos ][ fst used in (pos-1 | pos | pos+1) ][ snd used in (pos-1 | pos | pos+1) ]:=パターン数 とする。pos-2に入る辺がすでにあるかどうかの情報も必要なのではないかと思うかもしれないが、-2移動すると確実にパスが作れなくなるので考えなくて良い。

Fenwick Iterations

Fenwick tree における query 操作でアクセスするノード数を求める問題。i&(i+1)-1 ではなくて i&(i-1)の間違いでは？と思うかもしれないが、0-indexed だとこうなる。以下のスライドを参考にするといい。

http://hos.ac/slides/20140319_bit.pdf

セグメント木もそうなのだが、Fenwick tree は 1-indexed の方が二進数的な性質がきれいに現れる。1-indexed な Fenwick tree であれば query でアクセスするノード数はインデックスを二進表記したときの 1 の個数になる。これは i&(i-1) が最下位ビットを削る操作であることから機械的にも分かる。

よって、この問題は入力を 1-indexed に変えることができれば高速に解ける。L1++L2*n++L3 という少し変わった数の与えられ方でも 1 を足すくらいなら簡単。

Big Queries

trailing zeros の個数を数えるには、素因数分解したときの 2 の個数と 5 の個数を数えて min をとればいい。遅延セグ木やるだけかと思う。

Power Sums

関数F(k)の具体値 F(0),F(1),...,F(n-1) が与えられ、F(x) の値を補間する問題。$x^n+y^n$ が $x+y$ と $x^2+y^2$ と漸化式を用いて計算できることを知っていれば、同様のアプローチを掛けるのが自然かと思う。それでは冪和対称式の性質を探ってみよう。

2変数、3変数のときは次の関係式が見つかった。

$$ x^{11}+y^{11}=(x+y)(x^{10}+y^{10})-xy(x^9+y^9) $$ $$ x^{11}+y^{11}+z^{11}=(x+y+z)(x^{10}+y^{10}+z^{10})-(xy+xz+yz)(x^9+y^9+z^9) + x y z (x^8+y^8+z^8) $$

一般的には以下のような線形漸化式になりそうではある。

$$ F(n)=s_1F(n-1)-s_2F(n-2)+s_3F(n-3)-\cdots $$

$s_k$ は k 次の基本対称式$で、F(n)=x_1^n+\cdots+x_k^n$。つまり基本対称式が求まれば漸化式を解くだけになる。

冪和対称式から基本対称式に変形できれば良いので、うまく関係性を見つけ出したい。ネットを漁ると見つかる。

対称多項式入門

それっぽい式を立てて wolfram alpha に投げればおそらくは見つかると思うが、きれいな導出があったのでこの記事でも簡単に説明する。$s_i$ をi次の基本対称式、$p_i=a_1^i+\cdots a_n^i$ と定義する。$s_i$ の母関数は次のような関係式を満たす。 $$f(x)=(1+a_1x)(1+a_2x)\cdots(1+a_n x)=s_0+s_1x+s_2x^2+\cdots s_n x^n$$

ここで $s_0=1$ としている。$f(x)$の対数を取ると次のようになる。

$$ \log f(x)=\sum_{i=1}^{n} \log(1+a_i x) $$

さらに微分すると次のようになる。

$$ \begin{align} \frac{f'(x)}{f(x)} &=\sum_{i=1}^{n} \frac{a_i}{1+a_i x} \\ &=\sum_{i=1}^{n} \sum_{j=0}^{\infty}(-1)^{j}a_i^{j+1}x^j \\ &=\sum_{j=0}^{\infty}(-1)^{j}p_{j+1}x^j \end{align} $$

一方、普通に微分すれば次のようになる。

$$ f'(x)=s_1+2s_2 x+3s_3 x^2+\cdots n s_n x^{n-1} $$

これで $f'(x)$ の 2 種類の表示が得られた。それぞれ係数比較することにより次の関係式が得られる。

$$ \begin{align} s_1&=s_0 p_1 \\ 2s_2&=s_1p_1-s_0p_2 \\ 3s_3&=s_2p_1-s_1p_2+s_0p_3 \\ 4s_4&=s_3p_1-s_2p_2+s_1p_3-s_0p_4 \\ \vdots \end{align} $$

漸化式を行列累乗で解くと間に合わないと思うので、きたまさ法（多項式剰余）を使った。しかし TLE。別の高速化の余地はあったが、折角なのでモンゴメリ乗算というのを使ってみた。モンゴメリ乗算のコードは Min_25 氏の記事を参考にした。感謝したい。

Bear and Shuffled Points

あまり解かれてないけど瞬殺では…？（といいつつキャリパー法が無限ループしてたらしく苦しんでた）。

全体の最遠点対を求めて後ろから削っていく。最遠点対のどちらかが消されるまでは再計算不要である。最遠点対を意図的に消されると困るのだが、点の並びがランダムだからそういったことはあり得ない。たぶん期待値的にはO(nlogn)なんじゃないかなあ。

Sereja and Stones

貪欲法や他の賢い DP が使えるのかもしれないが、割と愚直な方法を強引に通した。E[i]≦77 が怪しいんだけど、結局使わずじまい。

基本的に動的計画法（メモ化再帰）なんだけど、もちろん全体をメモするのは無理なので小さいサイズの問題だけ記憶しておく。これだけでも平均 10 sec 未満で終わる。計測した感じだとアクセスするノード数は 3,000,000 程度しかないので、今度は遷移を高速化させる。

小さいサイズは比較的何度も呼び出されるので、その部分を高速化させたい。i % j < i / j となる(i,j)が少ないというのが肝で、小さい部分ではこの j を前計算しておくことで無駄なループが回るのを回避した。この工夫はかなり効果的で手元では 0.1 sec 程度にまで速くなった。計算量は不明。大量のケースで試したが遅くなるものは見つからなかった。

Tree Balancing

O(n2) から落とせず 50pts で終了。最適値のイメージは掴めたが結局計算量が落ちなかった。

割と面白い性質を知ることができた。