2052-Optimal Rest

超良問

問題概要

RXを1/X秒休むという命令とする．
また，その後ろに'.'が付いた場合は前の命令の1/2秒だけ休むとする．
例えばR1..の場合1+1/2+1/4=7/4秒休むことになる．
そして分母に65以上の数が出ることは無く，Xとして用いて良い数は1,2,4,8,16,32とする．
これらの規則にそったある表現が与えらえるので出来るだけ短く，かつ辞書順に早いものを答えろ．
例：R1R2R4→R1..

解法

文字数が小さい場合の動的計画法を行う．
そして文字数が多い場合は必ず"R1.R1.R1.…………"の形を含むので，それをどこに含むのかを全探索する．

実装(C++)

#include <iostream>
using namespace std;

int count(const string &in){
	int back=1;
	int res=0;
	int L=in.size();
	for(int i=0;i<L;i++){
		if(in[i]=='.'){
			res+=back/2;
			back/=2;
		}else if(in[i]=='R'){
			if(in[i+1]=='1'&&i+2<L&&in[i+2]=='6'){
				back=64/16;
				res+=back;i+=2;
			}else if(in[i+1]=='1'){
				back=64/1;
				res+=back;i+=1;
			}else if(in[i+1]=='2'){
				back=64/2;
				res+=back;i+=1;
			}else if(in[i+1]=='4'){
				back=64/4;
				res+=back;i+=1;
			}else if(in[i+1]=='8'){
				back=64/8;
				res+=back;i+=1;
			}else if(in[i+1]=='3'){
				back=64/32;
				res+=back;i+=2;
			}else if(in[i+1]=='6'){
				back=64/64;
				res+=back;i+=2;
			}
		}
	}
	return res;
}
const int k_mod=64*3*2;
string dp[31][k_mod*2];
string d[28]={"R1","R1.","R1..","R1...","R1....","R1.....","R1......","R2","R2.","R2..","R2...","R2....","R2.....","R4","R4.","R4..","R4...","R4....","R8","R8.","R8..","R8...","R16","R16.","R16..","R32","R32.","R64"};
int d_len[28];
int d_val[28];
string pre_ans[k_mod*2];
int main() {
	int n;
	for(int i=0;i<28;i++){
		d_len[i]=d[i].size();
		d_val[i]=count(d[i]);
	}
	for(int i=0;i<31;i++){
		for(int j=0;j<k_mod*2;j++){
			if(i==0&&j==0){
			}else{
				if(dp[i][j]=="")continue;
			}
			for(int k=0;k<28;k++){
				if(j+d_val[k]<k_mod*2&&i+d_len[k]<31){
					if(dp[i+d_len[k]][j+d_val[k]]==""){
						dp[i+d_len[k]][j+d_val[k]]=dp[i][j]+d[k];
					}else{
						if(dp[i+d_len[k]][j+d_val[k]]>dp[i][j]+d[k])dp[i+d_len[k]][j+d_val[k]]=dp[i][j]+d[k];
					}
				}
			}
		}
	}
	int q=0;
	for(int i=1;i<k_mod*2;i++){
		for(int j=0;j<31;j++){
			if(dp[j][i]!=""){
				pre_ans[i]=dp[j][i];
				q=max(j,q);
				break;
			}
		}
	}
	for(cin>>n;n--;){
		string in;
		cin>>in;
		int cnt=count(in);
		int pcnt=cnt/k_mod;
		cnt%=k_mod;
		if(pcnt>0){
			cnt+=k_mod;
			pcnt-=1;
		}
		string res="";
		if(cnt!=0){
			res=pre_ans[cnt];
		}
		string pres="";
		for(int i=0;i<pcnt*k_mod/96;i++){
			pres+="R1.";
		}
		string ans=pres+res;
		int L=res.size();
		for(int i=0;i<L;i++){
			if(res[i]=='R'){
				ans=min(ans,res.substr(0,i)+pres+res.substr(i));
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}