yukicoder 770 Median Sequence

https://yukicoder.me/problems/no/770

The first terms of A[i] can be written as

A[1] = B[1]
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,

A[i] = max ( min ( B[1] , N - i + 1 ) , min ( B[2] , N - i + 2 ) , ... , min ( B[i] , N ) )

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].

f:id:pekempey:20181219073616p:plain:w400

The maximum moves like the following figure.

f:id:pekempey:20181219081803p:plain:w400

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.

f:id:pekempey:20181219084219p:plain:w400

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