SRM 538 450pt : TurtleSpy

問題概要

前進、後進、回転の操作列を適切に並び替えて原点からの距離を最大化する問題。

解法

前進、後進は全部まとめた方が良い。後は回転をその間にどう挟むか。つくれる角度は超簡単なDPで計算しておく。

acceptされたコード

色々無駄はあるけどバグの生まれにくい書き方ではあったと思う。

#include <cmath>
#include <vector>
#include <string>
#include <sstream>
#include <numeric>
using namespace std;

const int MAX_N = 50;
const double PI = atan(1.0) * 4.0;

bool can_make[MAX_N + 1][360];

struct TurtleSpy {

	double sq(double x){
		return x * x;
	}

	double maxDistance(vector <string> commands) {
		vector<int> fs, bs, as;
		for(int i=0; i<(int)commands.size(); i++){
			stringstream ss(commands[i]);
			string cmd;
			int x;
			ss >> cmd >> x;
			if(cmd == "forward"){
				fs.push_back(x);
			}
			else if(cmd == "backward"){
				bs.push_back(x);
			}
			else if(cmd == "right"){
				as.push_back(x);
			}
			else{
				as.push_back( (360 - x) % 360);
			}
		}

		if(fs.empty()){
			return (double)accumulate(bs.begin(), bs.end(), 0);
		}
		else if(bs.empty()){
			return (double)accumulate(fs.begin(), fs.end(), 0);
		}

		can_make[0][0] = true;
		const int N = as.size();
		for(int i=0; i<N; i++){
			for(int j=0; j<360; j++)if(can_make[i][j]){
				can_make[i+1][j] = true;
				can_make[i+1][(j + as[i] + 360) % 360] = true;
			}
		}

		double f = (double)accumulate(fs.begin(), fs.end(), 0);
		double b = (double)accumulate(bs.begin(), bs.end(), 0);
		double ans = 0.0;
		//forward -> backward

		for(int a=0; a<360; a++)if(can_make[N][a]){
			double x = f - cos(a*PI/180)*b;
			double y = 0 - sin(a*PI/180)*b;
			ans = max(ans, sqrt(sq(x) + sq(y)));
		}

		//backward -> forward
		for(int a=0; a<360; a++)if(can_make[N][a]){
			double x = -b + cos(a*PI/180)*f;
			double y = -0 + sin(a*PI/180)*f;
			ans = max(ans, sqrt(sq(x) + sq(y)));
		}

		return ans;
	}

};