DISCO presents ディスカバリーチャンネル コードコンテスト2019 本戦:B - 大吉数列 (Array of Fortune)
問題
https://atcoder.jp/contests/ddcc2019-final/tasks/ddcc2019_final_b
考え方
条件の数式 をぐっと睨む。条件を満たす個数が大きくなる場合は になるべく大きい数を置く場合である。 の大きい順に左から考えていくと なる について条件を満たす数列の個数は一意に決まって、それは 個である。
よって になるまで が大きい数から順番に左から数列を構築すると条件を満たす数列が構築できる。 になる の場合はスキップする。条件を満たす数列に含まれない残りの数 は、残りの数をソートして、左から順におけば、 より、ソート済の数列の残りの数によって条件を満たす個数は になるので、構築することができた。
No Luck
となる場合は条件を満たす個数の最大値よりも が大きい場合である。
Submission #4128587 - DISCO presents ディスカバリーチャンネル コードコンテスト2019 本戦
どこに着目して考察するべきだったか
条件である数式に着目する。要素が大きい数を一番右にならべたときの個数を考えると一意に決まる。
何がバグっていたか
は最大 より long
で宣言しないとオーバーフローする。
得た知見(典型ポイント)
- 端から貪欲
- 大きい数から貪欲