SRM 665 div2 Easy Med

Easy

問題文

aが与えられる. a Xor b の計算結果の各桁の数字が全て4or7になり、かつ、a < bとなるbを出力せよ. 複数ある場合はどれを出力しても良い.

解法

全探索

aとbのXorはC++ならa^bで書ける.

コード

class LuckyXor {
public:
    bool check(int x){
	if(x == 0) return false;
	while(x > 0){
	    if(x % 10 != 4 && x % 10 != 7){
		return false;
	    }
	    x /= 10;
	}
	return true;
    }
    int construct(int a) {
	for(int b = a+1 ; b <= 100 ; b++){
	    if(check(a^b)){
		return b;
	    }
	}
	return -1;
    }
}

Med

問題文

ノード数Nの木が与えられる.
N-1本の各エッジには重みがあり、4or7である.

多重辺とならないように重み4or7のエッジを追加したとき、
長さが偶数のCycleになり、かつ、Cycleの各エッジの重みが4となる数と7となる数が等しくなる場合、
その追加したエッジの端点と重みを出力せよ.

解法

追加するエッジの端点と重みを決めうちし、Cycle判定をする.

もっといい方法ありそう…

コード

class LuckyCycle {
public:
    struct Edge{
	int to,w;
	Edge(){}
	Edge(int to,int w) : to(to),w(w) {}
    };
    
    vector<Edge> G[114];   
    bool ok;
    int visited[114],num[114];
    
    void init(){
	for(int i = 0 ; i < 114 ; i++){
	    G[i].clear();
	}
    }

    void dfs(int v,int c,int weight){
	visited[v] = 0; num[v] = c;
	for(int i = 0 ; i < (int)G[v].size() ; i++){
	    Edge e = G[v][i];
	    int nweight = weight + (e.w == 4 ? 1 : -1);    
	    if(visited[e.to] == -1){
		dfs(e.to,c+1,nweight);
	    }else if(visited[e.to] == 0){
		int cycle = num[v]-num[e.to]+1;
		if(cycle >= 3){
		    if(cycle % 2 == 0 && nweight == 0){
			ok = true;
		    }
		    throw 0;
		}
	    }
	}
	visited[v] = 1;
    }
    
    vector <int> getEdge(vector<int> edge1, vector<int> edge2, vector<int> weight) {
	int N = edge1.size()+1;
	if(N <= 2) return vector<int>{};
	init();
	bool isEdge[114][114];
	memset(isEdge,false,sizeof(isEdge));
	for(int i = 0 ; i < N-1 ; i++){
	    int a = edge1[i]-1,b = edge2[i]-1;
	    G[a].push_back(Edge(b,weight[i]));
	    G[b].push_back(Edge(a,weight[i]));
	    isEdge[a][b] = isEdge[b][a] = true;
	}
	const int W[2] = {4,7};
	for(int i = 0 ; i < N-1 ; i++){
	    for(int j = i+1 ; j < N ; j++){
		if(isEdge[i][j]) continue;
		for(int w = 0 ; w < 2 ; w++){
		    memset(num,-1,sizeof(num));
		    memset(visited,-1,sizeof(visited));
		    ok = false;
		    G[i].push_back(Edge(j,W[w]));
		    G[j].push_back(Edge(i,W[w]));
		    try{
			dfs(i,1,0);
		    }catch(...){}
		    if(ok){
			return vector<int>{i+1,j+1,W[w]};
		    }
		    G[i].pop_back();
		    G[j].pop_back();
		}
	    }
	}
	return vector<int>{};
    }
}