SRM450 Div2

過去問している。

250 StrangeComputer

"01010001"とか0と1だけの文字列が与えられる。

初期状態0で、よくわからないけど何回色変える必要があるか。

class StrangeComputer {
public:
	int setMemory(string mem) {
		mem.erase(unique(all(mem)),mem.end());
		return mem.size() - (mem[0] == '0');
	}
};

500 OrderedNim

先頭の山からニムニムする。むずかしい・・・。Faild出しまくった。

int memo[51] = {0};
int dfs(int n , vector<int> &s){
	if(n == s.size())return 0;
	if(~memo[n])return memo[n];
	
	int get = dfs(n+1,s);
	return memo[n] = !get || (s[n] != 1 && get) ;
}
class OrderedNim {
public:
	string winner(vector <int> s) {
		rep(i,51)memo[i] = -1;
		return dfs(0,s) ? "Alice" : "Bob";
	}
};

1000 EnemyTowers

実装重かった。無駄なことをしている気がするけど、とりあえず配分する人数を二分探索。

struct RES{
	int round,remain;
	RES(int a,int b){round = a , remain = b;};
};
bool operator<(const RES &a ,const RES &b){
	if(a.round == b.round)
		return a.remain < b.remain;
	return a.round < b.round;
}

RES group(int ppl,int hpT,int numT,int attackT){
	long long all = hpT * numT;
	int ans = 0;
	while(all > 0){
		ans++;
		if(ppl <= 0) return RES(INT_MAX,0);
		all -= ppl;
		if(all > 0) ppl -= ((all+hpT-1) / hpT) * attackT;
	}
	return RES(ans,max(0,ppl));
}
bool simulate(int &ref,int one,int two,int hpT, int attackT, int numWodT, int numStoT){
	RES A = group(one,hpT,numWodT,attackT);
	RES B = group(two,hpT,numStoT,attackT);
	ref = min(ref,max(A.round,B.round));
	return A < B;
}

class EnemyTowers {
public:
	int attack(int myUnits, int hpT, int attackT, int numWodT, int numStoT) {
		
		int l = 1 , r = myUnits-1 , ans = INT_MAX;
		
		rep(i,100){
			int m = (l+r) / 2;
			bool t = simulate(ans,myUnits-m,m,hpT,attackT,numWodT,numStoT);
			if(t){
				l = m+1;
			}else{
				r = m-1;
			}
		}
		return (ans==INT_MAX?-1:ans);
	}
};