SRM397 Div2

Easy

ソース

class BreakingTheCode{
public:
	string decodingEncoding(string s, string t) {
		string ans;
		if('0'<=t[0]&&t[0]<='9'){
			for(int i = 1; i < t.size(); i+=2){
				int a = 10*(t[i-1]-'0')+t[i]-'0';
				ans+=s[a-1];
			}
		}else {
			for(int i = 0; i < t.size(); i++){
				for(int j = 0; j < 26; j++){
					if(t[i]==s[j]){
						j++;
						char a = j/10+'0',b = j%10+'0';
						ans+=a;
						ans+=b;
						break;
					}
				}
			}
		}
		return ans;
 	}
};

Medium

解法

mapとqueueを使って、BFS
sortされた状態から、動かしましたが、入力の状態からソートされた状態にするのでも、恐らく解けます。

ソース

class SortingGame{
public:
	int fewestMoves(vector <int> s, int p) {
		int n = s.size();
		vector<int> d(n);
		for(int i = 0; i < n; i++)d[i]=i+1;
		map<vector<int>,int> m;
		m[d]=1;
		queue<vector<int> > q;
		q.push(d);
		while(!q.empty()){
			vector<int> f = q.front();
			q.pop();
			for(int i = 0; i <= n-p; i++){
				vector<int> e(f);
				reverse(e.begin()+i,e.begin()+i+p);
				if(!m[e]||m[e]>m[f]+1){
					m[e] = m[f]+1;
					q.push(e);
				}
			}
		}
		return m[s]-1;//sにできないときは、m[s]=0
 	}
};

Hard

解法

バッグの個数をb,ビー玉の個数をnとしたとき、O(b*2^(2n)*n)になるDPをする。
b = 10, n = 13なので、TLEが怖いですが、
{1,1,1,1,1,1,1,1,1,1,1,1,1}
13
10
を入力しても、1.6s未満でした。

dp[a][b]=true のとき、a(=入れれるビー玉をbit集合で表現したもの)をb個のバッグに入れられる。
dp[k][i+1]がtrueになる条件は、j∈k、かつ、dp[j][i]=true、かつ、k-jの重さの合計が1つのバッグに入る大きさである。

書いているときに気が付きましたが、jとkを逆にすると、高速になりそうです。

ソース

int dp[1<<13][11];

class CollectingMarbles{
public:
	int mostMarbles(vector <int> s, int c, int d) {
		int n = s.size();
		//sort(s.begin(),s.end());
		dp[0][0]=1;
		for(int i = 0; i < d; i++){
			for(int j = 0; j < 1<<n; j++){
				if(!dp[j][i])continue;//無くても、TLEしない
				for(int k = 0; k < 1<<n; k++){
					if((j&k)==j){//ここはfalseになることが多いので、TLEしない
						int l = k^j,t = 0;
						for(int m = 0; m < n; m++){
							if((1<<m)&l){
								t+=s[m];
							}
						}
						if(t<=c)dp[k][i+1]=true;
					}
				}
			}
		}
		int ans = 0;
		for(int i = 0; i < 1<<n; i++){
			if(dp[i][d]){
				int t = 0;
				for(int j = 0; j < n; j++){
					if(i&(1<<j))t++;
				}
				ans = max(ans,t);
			}
		}
		return ans;
 	}
};