competitive: 4月 2019

2019年4月29日月曜日

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

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

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

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

2019年4月27日土曜日

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

$L(i) := \gcd(A_1, ..., A_{i-1})$ , $R(i) = \gcd(A_{i+1}, ..., A_N)$ とすると $G(i)$ は

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

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

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

あと、今まで意識したことがなかったけど、gcdの単位元として $0$ が使えるという理解を得た。

別解とか

今回のCってこれだけだと思うんですけど pic.twitter.com/JKK0zBK1bf
— じゅぴちゃん (@jupiro_jupi) April 27, 2019

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

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

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

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

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

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

2019年4月26日金曜日

ABC 018 C - 菱形カウント

問題
AC

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

xxxxxxx
xxoooox
xooooxx
xooooox
xoxxoox
xxxxxxx

xからの最短距離が $K$ 以上であるマスがわかれば、その数が答えである。具体的には、マスxを $0$ に、マスoを $\inf$ に初期化した上で、 $0$ に初期化した点をすべてキューに入れて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

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

2019年4月25日木曜日

ABC 011 D - 大ジャンプ

問題
AC

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

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

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

しかし、上の $P$ をそのまま計算すると倍精度ではオーバーフローしてしまうので、 $\log$ を経由することにする:
$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\binom{n}{m}= \log n! - \log m! - \log (n-m)!$ だから、階乗の対数が求まればよい。今回は $N$ が小さいので素朴に足す¹だけでも問題ないし、大きい場合も精度のよい漸近公式がいろいろある。²

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

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

$\log n! = \sum_{i=1}^n \log i$ ↩︎
言語によってはそもそも標準ライブラリにlgammaがあったりするらしい。 ↩︎