SRM 667 div2 Easy Med

Easy

問題文

省略

解法

全探索

コード

class PointDistance {
public:
    int dist(int x1,int y1,int x2,int y2){
	return pow(x1-x2,2.)+pow(y1-y2,2.);
    }
    vector <int> findPoint(int x1, int y1, int x2, int y2) {
	for(int x3 = -100 ; x3 <= 100 ; x3++){
	    for(int y3 = -100 ; y3 <= 100 ; y3++){
		int d1 = dist(x1,y1,x3,y3);
		int d2 = dist(x2,y2,x3,y3);
		if(d1 > d2){
		    return vector<int>{x3,y3};
		}
	    }
	}
	return vector<int>{};
    }

Med

問題文

省略

解法

BitDP.
dp[どの命令を実行したかのbit] := 最短実行時間

最初、
dp[今何個目の命令を実行しているか][どのセルを使ったか] := 最短実行時間
でやっていたが、これでも通った.

コード

#define INF 1e9

int dp[1<<20];

class OrderOfOperationsDiv2 {
public:
    int N,M,bit[20];
   
    int solve(int idx,int S,int used,vector<string> &s){
	if(idx == N) return 0;
	int &res = dp[used];
	if(res != -1) return res;
	res = INF;
	for(int i = 0 ; i < N ; i++){
	    if(used >> i & 1) continue;
	    int c = 0;
	    for(int j = 0 ; j < M ; j++){
		if(!(S >> j & 1) && (bit[i] >> j & 1)) ++c;
	    }
	    res = min(res,solve(idx+1,S|bit[i],used|(1<<i),s) + (int)pow(c,2.));
	}
	return res;
    }
    
    int minTime(vector<string> &s) {
	memset(dp,-1,sizeof(dp));
	N = s.size(), M = s[0].size();
	for(int i = 0 ; i < N ; i++){
	    bit[i] = 0;
	    for(int j = 0 ; j < M ; j++){
		if(s[i][j] == '1'){
		    bit[i] |= 1<<j;
		}
	    }
	}
	return solve(0,0,0,s);
    }
}