DISCO presents ディスカバリーチャンネル コードコンテスト2019 本戦:B - 大吉数列 (Array of Fortune)

問題

https://atcoder.jp/contests/ddcc2019-final/tasks/ddcc2019_final_b

考え方

条件の数式  a_j \le a_i - K\ (i \lt j) をぐっと睨む。条件を満たす個数が大きくなる場合は i になるべく大きい数を置く場合である。a_i の大きい順に左から考えていくと 1 \le a_i \le N なる a_i について条件を満たす数列の個数は一意に決まって、それは max(a_i-k,0) 個である。

よって r=0 になるまで a_i が大きい数から順番に左から数列を構築すると条件を満たす数列が構築できる。r \lt 0 になる a_i の場合はスキップする。条件を満たす数列に含まれない残りの数 a_j は、残りの数をソートして、左から順におけば、1 \le K より、ソート済の数列の残りの数によって条件を満たす個数は 0 になるので、構築することができた。

No Luck となる場合は条件を満たす個数の最大値よりも R が大きい場合である。

Submission #4128587 - DISCO presents ディスカバリーチャンネル コードコンテスト2019 本戦

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

条件である数式に着目する。要素が大きい数を一番右にならべたときの個数を考えると一意に決まる。

何がバグっていたか

R は最大 \displaystyle \frac{N \times (N-1)}{2} より long で宣言しないとオーバーフローする。

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

  • 端から貪欲
  • 大きい数から貪欲

類題