ARC086 D - Non-decreasing
問題
提出コード
隣り合った要素を比較すると、正負によって4パターンに分けることができます。
前後が正だった場合
前の方が大きいならば、前の値を後ろに足してあげれば、1回の操作で条件を満たします。前後が負だった場合
前の方が大きいならば、後ろの値を前に足してあげれば、1回の操作で条件を満たします。前が正、後ろが負だった場合
後ろを正にするか、後ろを負にする必要があります。その後でも条件を満たしてなければ、上記のどちらかに帰着できます。前が負、後ろが正だった場合
必ず条件を満たしています。
ということで、上記のような4パターンが存在します。一番厄介なのが、3つめの「前が正、後ろが負」だったパターンになります。
前から(もしくは後ろから)貪欲にそろえていった場合、このようなパターンの処理が難しい上、両方正のパターンと両方負のパターンを混在させるのは、いろいろなパターンが存在し場合分けが難しそうです。
ということで、「前が正、後ろが負」だった場合、どちらかの符号が必ず逆にならなければならないことから、符号を変える最小回数をいったん求めてみます。
すると、数列の中で、絶対値が最大の数(xとします)を持ってきてあげると、xを別の数に足せば、かならず符号がxと同じになるか、0になるということが判明します。
ということで、この操作を行うことにより、数列のすべての符号をそろえることができるようになりました。
ここで、最初の場合分けに戻ってみると、前後の符号がそろっているとき、必ず1回の操作で隣り合っている場所の条件を満たすことができるということでしたので、あとは前から(負であれば後ろから)見ていき、今見ている場所とその1つ先が、条件を満たしていなければ条件満たすように操作を行う、ということを繰り返すことで答えが求まります。
符号をそろえるのに多くてN-1回、前後を見比べて条件をそろえるのに多くてN-1回の操作が必要になりますので、2N回以内に抑えることができました。
符号をそろえるパートでは注意が必要で、例えばi番目の数が絶対値最大のとき、i番目の数をとりあえずN個の要素に足したいですが、i番目自身に足し合わせてしまうと、i番目の値が変わってしまいそれ以降足す数字が変わってしまうので注意が必要です(i番目を足す操作をスキップするか、i番目に足した時点でそれ以降は2倍に直す、という操作が必要になると思います)。
