第9回 日本情報オリンピック本選3:つらら
問題
https://www.ioi-jp.org/joi/2009/2010-ho-prob_and_sol/2010-ho.pdf
制約
考え方
つららはいずれすべて cm になる。つららの長さ が大きいものから降順に考えていく。 が伸び始めることができるのは のつららよりも のつららの長さが大きいときである。一番最初から なる については 秒後につららが cm になって折れる( cm になる)。そうでない場合は、となりのつららが折れてから伸び始めることができる。
結局、 の大きいつららから考え、それぞれのつららが折れる時間を とすると、 であることがわかる。
よって各 について上記の式によってつらら が折れる時間がわかるのでそれらの最大値が解になる。
どこに着目して考察するべきだったか
つららが伸び始める条件を整理すると、両隣のつららにしか依存しないことがわかるので、両隣のつららが何秒後に折れるが事前にわかっていれば、つららが伸び始める時間がわかり、折れる時間もわかる。
Submission #3692637 - 第9回日本情報オリンピック 本選(オンライン)
何がバグっていたか
得た知見
何に依存するか考える。