TopCoder SRM 815 : Div1 Medium BilliardsMaster

しょうもないResubmitが痛い。
https://community.topcoder.com/stat?c=problem_statement&pm=17220&rd=18891

問題

(tx,ty)の大きさのビリヤード台を考える。
(sx,sy)から球を任意の方向に打ち、B回壁に反射させて(fx,fy)に止めたい。（強さは任意に設定できるものとする）
条件を満たす打ち方のうち、総移動距離が最短となるものを求めよ。
もしそのようなものが複数あれば、それぞれ上下左右の壁で反射した回数の最大値を求めよ。

解法

左右方向の反射回数を総当たりすると、上下の反射回数の高々2通りに決まるので、それぞれ移動距離を求めよう。

class BilliardsMaster {
	public:
	vector <int> play(int tx, int ty, int sx, int sy, int fx, int fy, int b) {
		vector<vector<ll>> cand;
		
		for(int bx=-b;bx<=b;bx++) {
			for(int i=-1;i<=1;i+=2) {
				int by=i*(b-abs(bx));
				
				ll ax=0,ay=0;
				if(bx%2==0) ax=fx+1LL*bx*tx;
				else ax=(2*tx-fx)+1LL*(bx-1)*tx;
				if(by%2==0) ay=fy+1LL*by*ty;
				else ay=(2*ty-fy)+1LL*(by-1)*ty;
				
				ll d=(ax-sx)*(ax-sx)+(ay-sy)*(ay-sy);
				
				vector<ll> a;
				a.push_back(d);
				if(bx>=0) {
					a.push_back(abs(bx)/2); //左
					a.push_back(abs(bx)-abs(bx)/2); //右
				}
				else {
					a.push_back(abs(bx)-abs(bx)/2); //左
					a.push_back(abs(bx)/2); //右
				}
				if(by>=0) {
					a.push_back(abs(by)-abs(by)/2); //下
					a.push_back(abs(by)/2); //上
				}
				else {
					a.push_back(abs(by)/2); //上
					a.push_back(abs(by)-abs(by)/2); //下
				}
				cand.push_back(a);
				if(by==0) break;
			}
			
		}
		sort(ALL(cand));
		vector<int> V={0,0,0,0};
		FORR(r,cand) {
			if(r[0]==cand[0][0]) {
				V[0]=max(V[0],(int)r[1]);
				V[1]=max(V[1],(int)r[2]);
				V[2]=max(V[2],(int)r[3]);
				V[3]=max(V[3],(int)r[4]);
			}
		}
		
		sort(ALL(V));
		return V;
		
	}
}

まとめ

Resubmitもったいないけど、Resubmitしてなければもっと大事故だったしなぁ。