codeFlyer (bitFlyer Programming Contest):C - 徒歩圏内

問題

https://atcoder.jp/contests/bitflyer2018-qual/tasks/bitflyer2018_qual_c

考え方

以下の条件を満たす (i,j,k) の3点の組を求める。条件は数式で表現する。

  1. i \le j \le k
  2. X_j - X_i \le D
  3. X_k - X_j \le D
  4. X_k - X_j \gt D

制約上ある1変数は全探索できるので、3点の真ん中 j を全探索することとする。また条件(4)についてはこのままでは求めにくいので余事象を考えるとする。つまり(4)の条件を除いて求めた場合の数から

  • X_k - X_j \le D

を満たす場合の数を差し引くこととする。

条件(1),(2),(3)を満たす個数は j を全探索すると、それぞれ cnt_i,cnt_k の個数は [X_j-D,X_j), (X_j,X_j+D] に含まれる値の数である。これは二分探索で求めることができる。よって条件を満たす場合の数は

\displaystyle \sum_{j=1}^{N-1} cnt_i * cnt_k

である。

条件を満たさない場合の数は j の全探索の場合とは別に独立して求めてよくて、その時の場合の数は (X_i,X_i+D] なる個数 c_i から 2 点を選ぶ場合の場合の数である。よって以下の場合の数を差し引く

\displaystyle \sum_{i=1}^{N-1} \frac{c_i * (c_i-1)}{2}

どこに着目して考察するべきだったか

数えやすい値が何かを考えると余事象が見えてくる気がする。また条件を満たす数え上げと条件を満たさない数え上げはそれぞれ独立して求めることというのがポイントな気がする。

何がバグっていたか

条件を満たす数え上げと満たさない数え上げが独立にできることに気づかなかった。

得た知見(典型ポイント)

  • 余事象で考える(求めやすい値を引く
  • 条件を独立して考える
  • 3点の真ん中全探索

類題