yukicoder 770 Median Sequence
https://yukicoder.me/problems/no/770
The first terms of A[i] can be written as
A[2] = max ( min ( B[1] , N - 1 ) , B[2] )
A[3] = max ( min ( B[1] , N - 2 ) , min ( B[2] , N - 1 ) , B[3] ).
In general,
To make it easy, we draw them on a graph. For example, B=[9,8,7,7,1,1,1,1,1,11,10,9] can be drawn as follows. Points are on ( i , B[i] ) and the maximum height on lines y = min ( B[i] , N - x + i ) equals A[i].
The maximum moves like the following figure.
It seems like a path. We can always move to the right and the upper right. We can move to the lower right only (+1, -1), and we can't always move there. We cannot move as follows.
The key is when we can move to (+1,-1). The most difficult part is done, so It is not difficult to solve it.
https://yukicoder.me/submissions/304962
https://ideone.com/aTk44Q
https://ideone.com/HGw4Gp
https://ideone.com/I5TR3S