問題C Sunday Drive

合同練習会

もとのこの問題は小数点以下2桁出力していますが、練習会では出力形式が小数点以下4桁の出力に変更されています。

解法

DP(動的計画法)です。dp[i][j] := i番目の区間のj番目のレーンにたどり着く最短距離 となるように計算します。曲がる区間のカーブの距離の計算式や直線区間の車線変更の部分が間違えやすいので気をつけましょう。

コード(C++)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

const double PI = acos(-1);
const double INF = 1e+8;

//dp[i][j] := 区間 i の左から j 番目レーンにたどり着く最短距離
double dp[1001][11];

int main(){
	int N, M, K[1001];
	char T[1001];
	
	while( cin >> N >> M , N || M ){
		for(int i = 0 ; i < N ; i++ ) cin >> T[i] >> K[i];
		
		// 初期化
		for(int i = 0 ; i < 1001 ; i++ ){
			for(int j = 0 ; j < 11 ; j++ ){
				dp[i][j] = INF;
				if( i == 0 ) dp[i][j] = 0;
			}
		}
		
		// i := 区間, j := レーン
		for(int i = 0 ; i < N ; i++ ){
			for(int j = 0 ; j < M ; j++ ){
				if( T[i] == 'S' ){ // 直線の区間
					// 移動できるレーン数
					int r = K[i] / 100;
					
					// レーンを j -> k と移動する
					for(int k = j - r ; k <= j + r ; k++ ){
						if( j == k ){ // 直線で移動
							dp[i + 1][k] = min(dp[i + 1][k], dp[i][j] + K[i]);
						}else if( 0 <= k && k < M ){
							double a = K[i], b = abs(j - k) * 10;
							double d = sqrt(a * a + b * b);
							dp[i + 1][k] = min(dp[i + 1][k], dp[i][j] + d);
						}
					}
				}else if( T[i] == 'L' ){ // 左に曲がる区間
					double r = K[i] + 10 * j + 5;
					double d = 0.5 * PI * r;
					dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + d);
				}else if( T[i] == 'R' ){ // 左に曲がる区間
					double r = K[i] + 10 * M - 10 * j - 5;
					double d = 0.5 * PI * r;
					dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + d);;
				}
			}
		}
		double ans = INF;
		for(int i = 0 ; i < M ; i++ ) ans = min(ans, dp[N][i]);
		printf("%.4f\n", ans);
	}
}