1916 Rat Attack 1025*1025のグリッドからなるフィールドがある。そこのいくつかの点にはネズミがいる。ネズミ駆除会社は、威力dの殺鼠剤を使って駆除をしたい。殺鼠剤は、それが置かれた地点と、ネズミの座標のx,y座標の差がともにd以下であるような位置に…

ひさしぶりにPKU

300 いきなりぶっ飛んだ配点。 レジスタ1つで、+,-,*,/の処理しかできないコンピュータがある。それぞれの処理は、レジスタの内容を演算子の両側にぶち込んで実行してレジスタに戻す。プログラムは処理を書き並べたものである。ある値から、目標の値にすると…

1609 Tiling Up Blocks それぞれ属性(l, m)を持つブロックを積み上げる。ブロック(l, m)はブロック(l', m')の上に、l >= l' かつ m >= m' が成り立つとき、積み上げられる。何段まで積める？lでソートして最長部分列。mが高々100なのでO(100*N)で通る。

2417 Discrete Logging 離散対数問題。整数B,N,P(Pは素数)が与えられたとき、B^L mod P = Nなる最小の整数Lを求めよ。Pが2^31ぐらいあるので普通にやるとTLEするが、だいたいO(√P log P)ぐらいで計算できる方法がある。 P

1659 Frogs' Neighborhood 蛙が何匹かいる。何組かの蛙はお互いに隣人であるらしい。各蛙の隣人の数が与えられるので、条件を満たす関係を1つ出力せよ、という問題。2 2311 Cutting Game 長方形を切っていくゲーム。１回に１枚を、X軸かY軸に平行に切ること…