yukicoder 770 Median Sequence

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

A[i] のはじめをいいかえると

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

となる。イッパンにはつぎのようになる。

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

わかりづらいのでグラフにしよう。たとえば B=[9,8,7,7,1,1,1,1,1,11,10,9] はつぎのようにかける。( i , B[i] ) にテンがうたれていて セン y = min ( B[i] , N - x + i ) のサイダイチが A[i] である。

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

サイダイチだけみると つぎのようになる。

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

ここからみえることは なんだろう。なんとなくケイロにみえる。みぎと みぎうえには いつでもいける。みぎしたは ( +1 , -1 ) にしかいけなくて かならずいけるとも かぎらない。たとえば つぎはありえない。

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

どういうときに みぎしたにいけるのか これが モンダイをとく かぎになっている。ここまでわかれば あとはむずかしくないだろう。

https://yukicoder.me/submissions/304962


ズ(い)https://ideone.com/aTk44Q
ズ(ろ)https://ideone.com/HGw4Gp
ズ(は)https://ideone.com/I5TR3S