2019年4月29日月曜日

ABC 021 C - 正直者の高橋くん

ABC 021 C - 正直者の高橋くん

与えられたグラフの隣接行列をAAとするとき、aaからbbへの距離ddのウォークの総数はAdA^daabb行に一致するので、これを最短距離について求めればよい。繰り返し二乗法をすれば計算量はO(n3logn){\mathcal O}(n^3 \log n)1

最短経路でDAGを作る話をまったく把握していなかったので、なんかおかしいなと思いながら知っている事実を使った。よく考えると、最短経路であることを何も活用していない。


  1. もっとも、この制約ならO(n4){\mathcal O}(n^4)でも間に合う可能性がある。 ↩︎

2019年4月27日土曜日

ABC 125 C - GCD on Blackboard

ABC 125 C - GCD on Blackboard

危うく平方分割するところだった……

AiA_iを書き換えるとき、最大公約数は高々gcd(A1,...,Ai1,Ai+1,...,AN)\gcd(A_1, ..., A_{i-1}, A_{i+1}, ..., A_N)であり、実際、AiA_igcd(A1,...,Ai1,Ai+1,...,AN)\gcd(A_1, ..., A_{i-1}, A_{i+1}, ..., A_N)に書き換えればこの値にできる。したがって、G(i):=gcd(A1,...,Ai1,Ai+1,...,AN)G(i) := \gcd(A_1, ..., A_{i-1}, A_{i+1}, ..., A_N)とすると、G(i)G(i)の最大値が答えである。

L(i):=gcd(A1,...,Ai1)L(i) := \gcd(A_1, ..., A_{i-1}), R(i)=gcd(Ai+1,...,AN)R(i) = \gcd(A_{i+1}, ..., A_N)とするとG(i)G(i)

G(i)=gcd(L(i),R(i))G(i) = \gcd(L(i), R(i))
で計算できるので、

L(i):=gcd(L(i1),Ai1)R(i):=gcd(R(i+1),Ai+1) \begin{aligned} L(i) := \gcd(L(i-1), A_{i-1}) \\ R(i) := \gcd(R(i+1), A_{i+1}) \end{aligned}

を利用して先にL(i)L(i), R(i)R(i)のテーブルを作っておけばよい。

最大公約数の定義

今まで意識したことがなかったけど、gcdの単位元として00が使えるという知見を得た。(N0,gcd,0)({\mathbb N}_0, \gcd, 0)は冪等な可換モノイドということになりそう。以下、形式的な整理。

a,bN0a, b \in {\mathbb N}_0が与えられたとき

aabbの約数 def\stackrel{\operatorname{def}}{\Longleftrightarrow} nN0n\in {\mathbb N}_0が存在してb=nab = na

と定め、また、kN0k \in {\mathbb N}_0の約数の集合をDkD_kと表す。このとき、最大公約数は

gcd(a,b):=max(DaDb)\gcd(a, b) := \max(D_a \cap D_b)

と定義できる。ただし、max\maxは通常の大小関係\leではなく、半順序\preceq
abdefaa \preceq b \stackrel{\operatorname{def}}{\Longleftrightarrow} abbの約数

に関するmax\maxとする。 aNa \in {\mathbb N}またはbNb \in {\mathbb N}のときは\leでも\preceqでも同じなので素朴な定義と変わりないが、
gcd(0,0)=max{0,1,2,...}=0\gcd(0, 0) = \max_{\preceq} \{0, 1, 2, ... \} = 0
が決まるところが異なる。

参考: https://math.stackexchange.com/questions/1386651/is-this-gcd0-0-0-a-wrong-belief-in-mathematics-or-it-is-true-by-conventi/1387924

N{\mathbb N}を追加して\leを拡張するのでもいい気がしたけど、00を両方追加すると破綻するので、それだったら00のほうがよいとなるのはわかる。

別解とか

これはうまい考え方だと思った。……けど、最初の2つの数の約数から素朴に調べる方針だと、例えば

100000
735134400 698377680 735134400 ... (99996個連続) ... 735134400 1 1

みたいな入力でけっこう時間が怪しい。とはいっても、高々2×1082 \times 10^8程度のループですむので、C++なら大丈夫だろうな。1

Divisor function d(n)d(n)の上限を見る限り、計算量は任意のϵ>0\epsilon > 0に対してo(N(maxAi)ϵ){\mathcal o}(N(\max A_i)^\epsilon)と評価できるようだが、漸近的な評価があまり役に立たない例にも見える。supind(i)\sup_{i \le n} d(i)の具体的な値を覚えておいたほうが良さそう。

参考: https://gist.github.com/dario2994/fb4713f252ca86c1254d


  1. jupiroさんの提出コード735134400 ... (99998個連続) ... 735134400 1 1で(コードテストでは)2600msだったが、これは改善可能で、前処理で約数の重複を除くくらいで十分なはず。 ↩︎

2019年4月26日金曜日

ABC 018 C - 菱形カウント

ABC 018 C - 菱形カウント

長方形領域の周りがxで囲われているものとして考える:

xxxxxxx
xxoooox
xooooxx
xooooox
xoxxoox
xxxxxxx

xからの最短距離がKK以上であるマスがわかれば、その数が答えである。具体的には、マスx00に、マスoinf\infに初期化した上で、00に初期化した点をすべてキューに入れてBFSすれば良い:

0   0   0   0   0   0   0
0   0   inf inf inf inf 0
0   inf inf inf inf 0   0
0   inf inf inf inf inf 0
0   inf 0   0   inf inf 0
0   0   0   0   0   0   0

0   0   0   0   0   0   0
0   0   1   1   1   1   0
0   1   2   2   1   0   0
0   1   1   1   2   1   0
0   1   0   0   1   1   0
0   0   0   0   0   0   0

計算量はO(RC){\mathcal O}(RC)

2019年4月25日木曜日

ABC 011 D - 大ジャンプ

ABC 011 D - 大ジャンプ

以下、X,YX, Yは最初からDDで割ったものを扱い、D=1D=1とする。xx軸に沿ってk+k^++1+1進み、kk^-1-1進み、yy軸に沿ってl+l^++1+1進み、ll^-1-1進む場合を考える。このように進む確率をP(k+,k,l+,l)P(k^+, k^-, l^+, l^-)とすると、
P(k+,k,l+,l)=(Nk+)(Nk+k)(Nk+kl+)4NP(k^+, k^-, l^+, l^-) = \binom{N}{k^+}\binom{N-k^+}{k^-}\binom{N-k^+-k^-}{l^+}4^{-N}

である。あとは(X,Y)(X, Y)にたどりつくようなk+,k,l+,lk^+, k^-, l^+, l^-の組み合わせについてPPを足し合わせればよい。具体的には、k+k^+が与えられたとき、k+k=Xk^+ - k^- = X, l+l=Yl^+ - l^- = Y, k++k+l++l=Nk^+ + k^- + l^+ + l^- = Nより、残りは以下のように定まる。
k=k+Xl+=12(Nk+k+Y)l=12(Nk+kY) \begin{aligned} k^- & = & k^+ - X \\ l^+ & = & \frac{1}{2}(N-k^+-k^-+Y) \\ l^- & = & \frac{1}{2}(N-k^+-k^--Y) \end{aligned}

したがって、各k+{0,1,...,N}k^+ \in \{0, 1, ..., N \}について(kk^-, l+l^+, ll^-が有効な値なら)P(k+,k,l+,l)P(k^+, k^-, l^+, l^-)を足し合わせると、それが答えになる。

しかし、上のPPをそのまま計算すると倍精度ではオーバーフローしてしまうので、log\logを経由することにする:
P(k+,k,l+,l)=exp(log(Nk+)+log(Nk+k)+log(Nk+kl+)Nlog4)P(k^+, k^-, l^+, l^-) = \exp \Bigl (\log\binom{N}{k^+} + \\\log\binom{N-k^+}{k^-} +\log \binom{N-k^+-k^-}{l^+} -N \log 4 \Bigr)

log(nm)=logn!logm!log(nm)!\log\binom{n}{m}= \log n! - \log m! - \log (n-m)!だから、階乗の対数が求まればよい。今回はNNが小さいので素朴に足す1だけでも問題ないし、大きい場合も精度のよい漸近公式がいろいろある。2

想定解法ではなさそうと思いながら書いた。対数を取る方法は、ABC 094 - Dがわからなくて苦し紛れに書いたのをコピペしただけなのだが、(精度的な意味で)どのくらい頑健なのかよくわかっていない。

想定解法は、最初から確率で遷移することで、値が大きくならないようにするというものだった。パスカルの三角形の(nm)/2n\binom{n}{m}/2^nバージョンは頭に入れておいたほうが良さそう。


  1. logn!=i=1nlogi\log n! = \sum_{i=1}^n \log i ↩︎

  2. 言語によってはそもそも標準ライブラリにlgammaがあったりするらしい。 ↩︎