11/24 PKU - Algorithmer’s note

フェンスがいくつかX軸に平行にある平面上で、原点から(S, N)までの最短距離のうちX軸方向の移動距離を求めよ。

DPだが、ある位置について見るときにフェンスに邪魔されないならそのままスルーしてよくて、フェンスに邪魔されたらそのフェンスの端に逃げれば良い。std::setを使うとO(N log N)になり、しかも簡潔に書ける。

分母がN以下の既約分数(0/1,1/1も含む)を小さい順に並べた時、K番目に小さいものを求めるクエリをC個処理せよ。

Farey数列を用いて予めリストを生成しておくと解ける