1/29 PKU
3844 Divisible Subsequences
与えられた数列の部分列で、和がDで割り切れるものの数を求めよ。
先頭からの和を(modDで)取ってやるだけ
3654 Electronic Document Security
「人と、その人に対する権利」の追加や剥奪のリストが与えられるので、最終的な権利のリストを出力せよ。
やるだけ
2333 Beach cut
海岸線の情報が与えられる。海岸線は折れ線で、折れ線をなす点のx座標は単調増加となっている。海岸線の上は海で、下は浜辺である。折れ線の2つの頂点を線分で結んで、その線分と海岸線で囲まれた浜辺の面積を最大にしたい。ただし、線分の長さはL以下でないといけなくて、線分は海岸線と交差してはいけない(接するのはいい)。最大の浜辺の面積を求めよ。
線分の一番左の頂点を固定して、右の頂点を右へとずらしていく。このとき、「いままで出てきた最小の線分の傾き」を覚えておいて、傾きがこれ以下であるなら、今線分は海岸線と交差しないことがわかる。ここで面積を求めて(毎回足していけばよい)、長さがL以下であるなら答えを更新する。この手順はO(N)である。この手順を、固定する左の頂点を動かして行うのでO(N^2)で解ける。