CodeChef July Challenge 2016

min, max, sum を計算すればいい。

Prim 法っぽく priority queue で繋いでいった。

A[0] への落とし方が 4 通りしかないので、統一する値のパターンも 4 通り、ということを使って DP した。4通り計算しなくても総和から分かるので無駄なことをしたかな。

ロボットはその場に留まれる（(0,0)の移動をしたと考えればいい）ので、独立に最短経路を求めて max を取ればいい。

左側の区間の R を決めて、L=R→0 のように拡大させていく。そして、各 (L,R) に対して [R+1,N-1] の中にある部分列を数える。

f:id:pekempey:20160712114539p:plain

[L,R]にある値（使用禁止要素）は赤色で塗った。禁止要素を含む部分列は作ってはいけないので、禁止要素の隙間だけを使って部分列を構成する必要がある。

禁止要素の位置を set で覚えておけば、新しく禁止要素を追加したときの部分列の総数を高速に再計算することができる。

R 各々に対して禁止要素の追加回数は O(N) 回なので、全体の計算量は O(N² log N) になる。

ゴリ押し DP。

codechefのメモリは潤沢。

cheflong だといつもゴリ押しDPをしてる気がする。