pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

CodeChef July Challenge 2016

Andrash and Stipendium

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

Chef and Electricity

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

Chef and Tetris

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

Chef and Robots Competition

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

Chef and Segments

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

f:id:pekempey:20160712114539p:plain

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

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

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

Chef and special numbers

ゴリ押し DP。

  • dp[ pos ][ more ][ less ][ mod 2520 ][ use mask ] := num

codechefのメモリは潤沢。

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