codeFlyer （bitFlyer Programming Contest）
Updated:
codeFlyer （bitFlyer Programming Contest）
ペンディング。 D までは書く。
Source codes
Solutions
A - 本選参加者数
$l = 100, 99, \dots$ に対し $Bl \leq A$ であるか計算し、初めてこれが成り立った瞬間に $Bl$ を出力する。
B - 洋菓子店
場合分けしてシミュレーションをするだけである。こうとしか言いようがない。
C - 徒歩圏内
解説が理解できないので私が自分で考えたことをメモしておく。 0-indexed とする。
方針
それぞれ $j$ を固定して数えることにする。以下の 1. から 2. を引いたものが答えである。
- $j$ とも相異なる $(i, k)$ のうち、 $i < k$ かつ $\lvert X_i - X_j \rvert \leq D$ 、 $\lvert X_j - X_k \rvert \leq D$ を充たすものの場合の数
- $j$ とも相異なる $(i, k)$ のうち、 $i < k$ かつ $\lvert X_i - X_j \rvert \leq D$ 、 $\lvert X_j - X_k \rvert \leq D$ 、 $\lvert X_i - X_k \rvert \leq D$ を充たすものの場合の数
一応説明すると、 1. から 2. を引いたものは $i < k$ かつ $\lvert X_i - X_j \rvert \leq D$ 、 $\lvert X_j - X_k \rvert \leq D$ 、 $\lvert X_i - X_k \rvert > D$ を充たすものであるが、 $\{ X_n \}$ の狭義単調増加性より $i < j < k$ も従う。
数え方
$R_i = i$ 以上の数字のうち、 $\lvert X_i - X_j \rvert \leq D$ を充たす最も大きな $j$。
$L_i = i$ 以下の数字のうち、 $\lvert X_i - X_j \rvert \leq D$ を充たす最も小さな $j$。
と定める。これらは尺取り法で合計 $O(N)$ で求まる。この時点で 1. は求まる。 $j$ ごとに $(i, k)$ の数字の候補は $n_j = R_j - (L_j - 1) - 1$ 個であり、このうち自由に $2$ 個選んで良いので組の場合の数は $n_j (n_j - 1) / 2$ である。
以下 2. を求めにいく。 2. の条件は $L_j \leq i < k \leq R_j$ かつ $\lvert X_i - X_k \rvert \leq D$ と同値である。高速に計算するためには、後者の条件を添字の条件に置き換える必要がある。
ここをどうするかなのだが、発想としては次のとおりである。まず $i = L_j$ かつ条件を充たす $(i, k)$ の組の数は、 $k$ の数、つまり $k = i+1, \dots, R_i$ のうち $j$ を除いたものである。これは当然 $(R_i - i) - 1$ 個である。これを $i$ に $1$ を足して繰り返して行けばいいので、累積和で計算量を削減できる。さて、問題はどこで止まるかである。実は単純に $i$ に $1$ を足していくだけでは求まらない。 $R_i$ が $L_j$ を超えた場合は $L_j$ で止めないといけない。ゆえに、これは単純な累積和ではない。この管理は、 $k \leq R_j$ の方を動かせばできる。数え方は類比的である。後者の累積和から前者の累積和を引く。すなわち、
$sumR[i] = \sum_{j = 0}^{i - 1} (R_j - j),$
$sumL[i] = \sum_{j = 0}^{i - 1} (j - L_j).$
と定めると、 $sumL[R_j + 1] - sumR[L_j] - n$ である。
ポイント
間違いを書いたんだけど、どう間違えたか思い出せない… (執筆は 6/6 の FGO ぐだぐだ放送局を見ながら書いている)