第9回 日本情報オリンピック本選3：つらら

問題

https://www.ioi-jp.org/joi/2009/2010-ho-prob_and_sol/2010-ho.pdf

制約

  • 2 \le n \le 10^5
  • 2 \le l \le 5 \times 10^4

考え方

つららはいずれすべて 0 cm になる。つららの長さ a_i が大きいものから降順に考えていく。a_i が伸び始めることができるのは i-1, i+1 のつららよりも i のつららの長さが大きいときである。一番最初から a_{i-1} \lt a_i > a_{i+1} なる i については L - a_i 秒後につららが L cm になって折れる( 0 cm になる)。そうでない場合は、となりのつららが折れてから伸び始めることができる。

結局、a_i の大きいつららから考え、それぞれのつららが折れる時間を cost_i とすると、cost_{i} = max(cost_{i-1}, cost_{i+1}) + L - a_i であることがわかる。

よって各 i について上記の式によってつらら i が折れる時間がわかるのでそれらの最大値が解になる。

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

つららが伸び始める条件を整理すると、両隣のつららにしか依存しないことがわかるので、両隣のつららが何秒後に折れるが事前にわかっていれば、つららが伸び始める時間がわかり、折れる時間もわかる。

Submission #3692637 - 第９回日本情報オリンピック 本選（オンライン）

何がバグっていたか

得た知見

何に依存するか考える。

類題