SRM401

250

与えられたn(<=30)に対してa_1 >= a_2 >= a_3 >= ... >= a_n, a_i <= n - i + 1を満たす数列の数を求めよという問題。メモ化再帰、もしくはDPで解ける。

550

次の二つの媒介変数表示の曲線が与えられたとする。ここで2つのt,sは独立に動く、またt,s以外の変数は与えられる。


このとき、二つの曲線が交わるかどうかを判定して、交わるならばその交点の座標を返せ、ただし複数の点で交わるならば(0,0,0)を交わらないならば空の配列を返す。
まず、

より

が成立しなければならない、でこれはsに関する二次方程式なので解ける。sが求まれば(sは2つ求まる場合がある)

より、tも求まる。あとはs,tを代入してp_1=p_2が成立するかどうかを見ればよい。このとき2つのsについて成り立つのならば複数の点で交わっていることになる。
基本的なアルゴリズムはあっていたけど以下の二点で間違えた。
1. sが重解をもつときに複数の解をもつと判定した。
2. p_2がつねに1点かつx_0^2+y_0^2=1の時に(x_0,y_0,z_0)をそのまま返していた、実際はtにz_0を代入したときのp_1とp_2を比較する必要がある。
550の書き直したバージョンを張っておきます、割と条件分岐が多くて面倒でした。

public class ParticleCollision {
	final static double[] MUL = { 0, 0, 0 };
	final static double[] EMP = {};

	boolean eq(double x, double y) {
		return Math.abs(x - y) < 1.0E-7;
	}

	double[] col(int vx, int vy, int vz, int x0, int y0, int z0, double t) {
		double ux = vx * t + x0;
		double uy = vy * t + y0;
		double z = vz * t + z0;
		double cx = Math.cos(Math.PI * z);
		double cy = Math.sin(Math.PI * z);
		if (eq(ux, cx) && eq(uy, cy))
			return new double[] { ux, uy, z };
		return EMP;
	}

	public double[] collision(int vx, int vy, int vz, int x0, int y0, int z0) {
		int a = (vx * vx + vy * vy);
		int b = (x0 * vx + y0 * vy);
		int c = (x0 * x0 + y0 * y0 - 1);
		int det = b * b - a * c;
		if (det < 0) return EMP;
		if (a == 0)
			if (vz == 0) {
				double cx = Math.cos(Math.PI * z0);
				double cy = Math.sin(Math.PI * z0);
				if (eq(x0, cx) && eq(y0, cy))return new double[] { x0, y0, z0 };
				else return EMP;
			}else
				return c == 0 ? MUL : EMP;
		double t1 = (-b + Math.sqrt(b * b - a * c)) / a;
		double t2 = (-b - Math.sqrt(b * b - a * c)) / a;
		double r1[] = col(vx, vy, vz, x0, y0, z0, t1);
		double r2[] = col(vx, vy, vz, x0, y0, z0, t2);
		if (r1 != EMP)
			if (det != 0 && r2 != EMP)return MUL;
			else return r1;
		else if (r2 != EMP)return r2;
		else return EMP;
	}
}