[Codeforces] Educational Round 69 (Div. 2) B. Pillars

問題

方針

柱を \( a_1 < a_2 < \cdots < a_n \) のように並び替えることができるかという問題です。どのようにして整列させるかというと、\( a \) を昇順に整列させた配列を \( b \) とします。このとき、\( b_i \) を \( i \) 番目の要素として、\( b_i.id \) を元の配列の添え字とします。一番大きい半径を持つ柱 (\( b_n\)) が一番下になるので、\( b_{n-1} \) を \( b_n \) の上に置くためには、\( |b_n.id – b_{n-1}.id = 1 | \)を満たす必要があります。

柱を上に置いたとき、配列のサイズが一つ減ると考えてよいので、\( b \) に元の配列における、前後の要素の添え字を管理して、配列のサイズが一つ減る操作を実現させます。

コード