JOI 17 本選-ストーブ
考察
まず分かることとして、K 個あるマッチは使い切ってしまったほうがお得です。
また、マッチを付けるのは来客の直前、そして消すのは客が帰った直後にしたほうがいいのも明らかです。
これらをふまえて、始めの客が来てから最後の客が帰るまでのストーブの様子を考えてみると、付いている期間と消えている期間は交互にあり、付いている期間の合計は K 個（それらに挟まれる消えている期間の合計は K-1 個）、といった感じになっているはずです。また、消えている間に来客を迎えることはできないので、1 つの消えている期間は、ある客が帰ってから次の客が来るまでの谷間の時間にあたっているはずです。
結局のところ、始めの客が来てから最後の客が帰るまでの間でストーブを消すことができるのは、N-1 個ある来客の谷間のうちの高々 K-1 個と分かります。
各谷間の長さを計算し、大きい順に K-1 個和をとって全体から引けば正解できます。
コード
上書きして消えた
