torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder, SRM 623, Division 2, Level 2 : CatAndRat

問題概要

 半径が R のリング状のチューブがあり、このチューブには一箇所の入り口がある。時刻 0 のとき、チューブにネズミが一匹入る。ネズミはチューブに入ったあと、Vrat 以下の早さで任意に移動できる。続いて、時刻 T のとき、チューブにネコが入る。ネコもネズミと同様に、Vcat 以下の早さで任意に移動できる。
 ネコとネズミが同一の点に存在するとき、ネコはネズミを食べてしまう。両者が最適に行動したとき、ネズミが生き残れる時間はいくらか、求めよ。無限に生き残れる場合は -1 で示せ。なお、チューブは円、ネコとネズミは点と同一視でききるものとする。

解法

 まず、Vcat <= Vrat のとき、ネコはネズミに追いつけないので -1 になります。そうでないとき、ネコの移動速度はネズミのそれを上回るので、いずれは追い付かれてしまいます。
 では、ネズミの最適な行動はどのようなものか考えましょう。これは明らかに、ネコが入ってくる地点からできるだけ離れておく方が、追い付かれるまでの時間を長くできます。時刻 T までに移動できる距離は T * Vrat で、チューブ内部の内、入り口から最も遠い点までは円周の半分の距離なので、\pi R です。従って、ネズミが到達可能な点の内で入り口から最も離れている点までの距離は min( T \times Vrat, \quad \pi R ) となります。この距離を d とします。ネズミの方からネコに近づくのは明らかに損なので、ネズミはネコから遠ざかります。このとき、ネコがネズミと逆向きに動いたとすると、ネズミは即座に方向転換することになるので、ネコとネズミは同一方向に進みます。このとき、ネコとネズミの相対速度は Vcat - Vrat と表されます。時間と速さの関係から、距離 d が 0 まで詰まるのにかかる時間は d / ( Vcat - Vrat ) と求まります。

コード

const double PI = acos( -1 );

class CatAndRat
{
public:
	double getTime(int R, int T, int Vrat, int Vcat)
	{
		if ( Vcat <= Vrat)
		{
			return -1;
		}

		const double d = min<double>( PI * R, T * Vrat );
		return d / ( Vcat - Vrat );
	}
};