SRM670 div2

Easy

問題概要

省略

解法

全探索。
あり得る組み合わせを全て試し、その結果をsetなどにつめていく。
最終的な答えは、setのsizeとなる。

コード

class Cdgame {
public:
    int rescount(vector <int> a, vector <int> b) {
	set<int> st;
	int sum1 = 0,sum2 = 0;
	int A = a.size(),B = b.size();
	for(int i = 0 ; i < A ; i++) sum1 += a[i];
	for(int i = 0 ; i < B ; i++) sum2 += b[i];
	for(int i = 0 ; i < A ; i++){
	    for(int j = 0 ; j < B ; j++){
		int nsum1 = sum1 - a[i] + b[j];
		int nsum2 = sum2 - b[j] + a[i];
		st.insert(nsum1*nsum2);
	    }
	}
	return st.size();
    }
};

Med

問題概要

省略

解法

貪欲法。
文字列のうち、'+'を'-'にすることは明らかに無意味である。

そこで、'-'を'+'にすることを考える。
prefixを考えると、文字列の中でより前にある文字が多くのprefixに影響を与えることがわかる。

よって、以下の操作を繰り返すと答えが出る。

1. 文字列Sのうち、最も左に現れる'-'を'+'に変える。
2. 変更された文字列Sを文字列Tとする。
3. 文字列Tでnegative balanceの個数を数える。
4. counterを+1する。
5. もし、negative balanceの個数がk以下なら終了し、counterが答えとなる。
6. そうでなければ、文字列Tを文字列Sに代入し、最初の操作に戻る。

コード

class Drbalance {
public:
    int N;
    bool check(ll S,int k){
	int sum = 0;
	for(ll i = 0 ; i < N ; i++){
	    if(S >> i & 1LL) sum++;
	    else sum--;
	}
	int cnt = 0;
	for(int i = N-1 ; i >= 0 ; i--){
	    if(sum < 0) cnt++;
	    if(S >> i & 1LL) sum--;
	    else sum++;
	}
	return (cnt <= k);
    }
     
    int lesscng(string s, int k) {
	ll S = 0LL;
	N = s.size();
	for(int i = 0 ; i < N ; i++){
	    if(s[i] == '+') S |= 1LL<<i;
	}
	int res = 0;
	while(!check(S,k)){
	    for(ll i = 0 ; i < N ; i++){
		if(!(S >> i & 1LL)){
		    S |= 1LL<<i;
		    break;
		}
	    } 
	    res++;
	}
	return res;
    }
};