問題 aまたはbからなる文字列が与えられる。 このとき、文字列に2回以上、重ならないで出現する空でない部分文字列の個数を求めよ。 文字列が同じときは一つと数える。 制約条件 文字列は乱数により生成される。 n≦10^5

問題 n個の箱があり、i番目の箱は 時刻in[i]に倉庫に入り、out[i]に倉庫から出る。 この荷物は重さがw[i]であり、上にs[i]までの荷物を載せることができる。 この荷物を倉庫に出し入れするとv[i]円もらえる。 倉庫には、同時に全体でSの重さの荷物しか入れら…

問題 wavy numberとは、数字を10進法で書いたときの数字をx1,x2,x3,...,xnとすると x1＜x2＞x3＜x4…が成り立つまたは、x1＞x2＜x3＞x4…が成り立つ数のことを言う。Nの倍数のwavy numberでK番目に小さいものを求めよ。 答えが存在しない場合や10^14より大きく…

問題 長方形の板がN枚並んで出来ているフェンスがある。 i番目の板は幅1, 高さがh[i]の長方形で、下側の辺は地面にぴったりとくっついている。 このフェンスに看板を貼る候補がQ通りある。 各候補は、l, r, wで表され、l枚目からr枚目の板の内部に幅wの長方…

問題 K日間にわたって写真を撮る。カメラの記憶容量はLであり、写真一枚が消費する記憶容量は非圧縮の場合Dである。 i日目にはti枚の写真を撮り、j番目の写真のできばえはQijである。 写真は好きなものを好きなだけ削除することができる。 また、同じ日の写…

問題 無限に広いグリッドがある。 N個の長方形があり、(xi, yi)を左下, (Xi, Yi)を右上としていて、範囲のマスにそれぞれ一人ずつ人間がいる。 長方形は重ならない。 M個の爆弾があり、(bxi, byi)に置かれていて、p1iの確率で、y = byiの直線にいる人が全員…