2020年1月31日金曜日

yukicoder No.980 Fibonacci Convolution Hard

yukicoder No.980 Fibonacci Convolution Hard

Cq:=a1aq1+a2aq2+...+aq1a1C_q := a_1a_{q-1} + a_2a_{q-2} + ... +a_{q-1}a_1とすると、漸化式は次のように書ける:

Cq=a1aq1+a2aq2+...+aq2a2+aq1a1=a1(paq2+aq3)+a2(paq3+aq4)+...aq2(pa1+a0)+aq1a1=p(a1aq2+...+aq2a1)+(a1aq3+...+aq3a1)+aq2=pCq1+Cq2+aq2 \begin{aligned} C_q & = a_1a_{q-1} + a_2a_{q-2} + ... + a_{q-2}a_2 +a_{q-1}a_1 \\ & = a_1(pa_{q-2} + a_{q-3}) + a_2(pa_{q-3} + a_{q-4}) + ... a_{q-2}(pa_1 + a_0)+ a_{q-1}a_1 \\ & = p(a_1a_{q-2} + ... + a_{q-2}a_1) + (a_1a_{q-3}+...+a_{q-3}a_1) + a_{q-2} \\ & = pC_{q-1}+C_{q-2} + a_{q-2} \end{aligned}

ただしa0=1a_0 = 1とする。

yukicoder No.979 Longest Divisor Sequence

yukicoder No.979 Longest Divisor Sequence

一見して端からDPすれば良さそうに見える。つまり、dp[x]:=dp[x] :=位置xxから始まる最長の部分列の長さ、としてdp[N1]=1dp[N-1]=1から逆順に埋めていく方法が考えらえるが、単純にdp[x]:=1+max{dp[y]:xyx<yAx<Ay}dp[x] := 1+\max \{dp[y] : x|yかつx < yかつA_x < A_y\}と遷移すると間に合わない。

約数の数があまり多くないことを利用すると遷移の数を減らせそう。つまり、Ay(<Ax)A_y (< A_x)AxA_xの約数であるようなy(<x)y(<x)をまとめておいて

dp[y]:=max(dp[y],1+dp[x])dp[y] := \max (dp[y], 1 + dp[x])

と遷移したい。ただ、これでは同一の約数がたくさん存在するときに遷移先の候補が減っていない。同一の約数についてはいちばん右のものだけ見ればよいから、

stack[k]:=(Ai)kstack[k] := 数列(A_i)中に登場する整数kの位置を降順に保持したスタック

を最初に作っておいて、適当にポップしながらスタックの先頭にだけ遷移すればよい。

2020年1月29日水曜日

JOI2007 春合宿 - lines

JOI2007 春合宿 - lines

同一の直線は最初に除いておく。以下、NN本の直線は相異なるとする。

平面走査的に考えてみる。つまり、十分に大きな正数aaについてxx軸に平行な直線L:y=aL: y=aを用意して、この直線を下に移動しながら領域の数を数える。y=ay=aと平行な直線はないとしてよい。1 最初に直線LLNN本の直線と交わっていて、これらに区切られたN+1N+1個の領域にまたがっている。LLを下に移動していくとき、LLが新たな領域に出会うのは直線の交点に一致した瞬間である。このとき、交点を通る直線が2本なら領域が1つ増え、3本なら2つ増え、一般にkk本の直線の交点ではk1k-1本増えている。

以上の観察より、単にl1l_1から順に直線を追加していき、新しい直線を追加するたびにこれまで追加した各直線と交わる点を(平行でなければ)検出し、同じ交点を検出した回数を数えていけばよい。

NN本の直線を処理したあと、ある交点PPをちょうど22本の直線が通ったなら、PP11回数えられ、33本なら1+2=31+2 = 3回数えられる。一般に、k+1k+1本の直線の交点は1+2+...+k=k(k+1)/21+2+...+k = k(k+1)/2回数えられていて、そこで増えた領域はkk個になっている。二次方程式を解くと、点PPvv回数えられたならそこで増えた領域は(1+1+8v)/2(-1+\sqrt{1+8v})/2個である。計算量はO(N2){\mathcal O}(N^2)


  1. あったら、全体を適当に回転させたものを考えればよい。 ↩︎

2020年1月26日日曜日

Code Festival 2014 - eject

Code Festival 2014 - eject

f(x):=xf(x) :=x回目でONになっている確率とすると、漸化式は

f(x)=kx1k回目でOFFで、あとはずっとONである確率=kx1(1f(k))p(1p)xk1\begin{aligned} f(x) & = \sum_k^{x-1} k\text{回目でOFFで、あとはずっとONである確率} \\ & = \sum_k^{x-1}(1-f(k))p(1-p)^{x-k-1} \end{aligned}

このままでは間に合わないので差分を計算すると、f(x)f(x1)=p(12f(x1))f(x)-f(x-1) = p(1-2f(x-1))になっていて、f(x)=p+(12p)f(x1)f(x) = p + (1-2p)f(x-1)という線形漸化式が従う。f(x)1/2=(12p)(f(x1)1/2)f(x)-1/2 = (1-2p)(f(x-1) -1/2)より、f(x)=1/2+(12p)x(f(0)1/2)=1/2+(12p)x(1/2)f(x) = 1/2 + (1-2p)^x(f(0)-1/2) = 1/2 + (1-2p)^x\cdot(-1/2)と表せて、これなら計算できる形になっている。

……と迂遠な導出をしてしまったが、よく見ると自明にf(x)=p(1f(x1))+(1p)f(x1)f(x) = p(1-f(x-1)) + (1-p)f(x-1)だった。直前から求まるかどうかは常に最初に考えるべき。


p=1p=1の場合に計算誤差が問題になるようだった。(expt -1d0 奇数)は-1になってほしいが、指数が大きいと1になる。手元だと境界はこの辺:

> (expt -1d0 9007199254740991)
-1.0d0
> (expt -1d0 9007199254740993)
1.0d0

計算の仕組みを何も知らないけど、前者(=2531=2^{53}-1)がdouble-floatで正確に表現できる最大の整数なので、そこまでは偶奇が落ちないという理解でたぶんいい。