mini notes

競技プログラミングの解法メモを残していきます。

Donutsプロコンチャレンジ2015 C - 行列のできるドーナツ屋

問題:C - 行列のできるドーナツ屋

解答:Submission #11037583 - Donutsプロコンチャレンジ2015

解法:スタックを準備し、数列を前から見てゆく。人iについて出力するのはその人より前でできている狭義単調減少列の長さであり、その単調列をスタックに格納しておく。

人iの出力はその時点でのスタックのサイズである。その後スタックを更新する。これはスタックに含まれる要素が人iの身長h[i]より小さいときにスタックからPopし続けたあと、h[i]をスタックに格納する。(人iよりより前にいる人iより小さい人は、人iの後ろの人から見えなくなるため)