codeFlyer (bitFlyer Programming Contest)

更新日時:

codeFlyer (bitFlyer Programming Contest)

ペンディング。 D までは書く。

ソースコード

解法のメモ

A - 本選参加者数

$l = 100, 99, \dots$ に対し $Bl \leq A$ であるか計算し、初めてこれが成り立った瞬間に $Bl$ を出力する。

B - 洋菓子店

場合分けしてシミュレーションをするだけである。こうとしか言いようがない。

C - 徒歩圏内

解説が理解できないので私が自分で考えたことをメモしておく。 0-indexed とする。

方針

それぞれ $j$ を固定して数えることにする。以下の 1. から 2. を引いたものが答えである。

  1. $j$ とも相異なる $(i, k)$ のうち、 $i < k$ かつ $\lvert X_i - X_j \rvert \leq D$ 、 $\lvert X_j - X_k \rvert \leq D$ を充たすものの場合の数
  2. $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 ぐだぐだ放送局を見ながら書いている)

D - ハンコ

ポイント

E - 祝日

ポイント

その他

コメントする