SRM544 Div1

0ptでした。

Easy
票の合計を固定してから、票が少ない時の合計と多い時の合計を調べて、最初の仮定が成り立つか調べる。
同じ数だけ票が入る人が複数人いるときにも、成り立つということが分からなかったけど、テストは通りました。

class ElectionFraudDiv1{
public:
	int MinimumVoters(vector <int> p) {
		int l = p.size();
		vector<double> p1(l),p2(l);
		for(int i = 0; i < l; i++){
			p1[i] = p[i]==0?0:(p[i]-0.5);
			p2[i] = p[i]+0.5-1e-8;
		}
		
		for(int i = 1; i < 100000; i++){//上限は201だから、もう少し小さくても良い
			int s1=0,s2=0;
			for(int j = 0; j < l; j++){
				s1 += ceil(p1[j]*i/100);
				s2 += floor(p2[j]*i/100);
			}
			if(s1<=i && i<=s2)return i;
		}
		return -1;
 	}
};

Medium
簡単(Div2 Mediumよりも簡単だったかもしれない)でしたが、時間が足りなくて間に合いませんでした。

右上から貪欲に確定させていくと、解けます。

int pos[51];

class FlipGame{
public:
	int minOperations(vector <string> g) {
		int h = g.size(),w = g[0].size(),par = 0,ans = 0;
		pos[0] = w;
		while(pos[h]<w){
			int flag = 0;
			for(int i = 0; i < h; i++){
				for(int j = w-pos[i+1]-1; j >= w-pos[i]; j--){
					if(g[i][j]-'0'==par)pos[i+1]++;
					else{
						flag = 1;
						break;
					}
				}
			}
			
			par = !par;
			ans+=flag;
		}
		return ans;
 	}
};

Score 0
Rating 1272 -> 1249