CodeForces #106 (Div. 2)

A.
ソートして、大きいのから使っていけばよい。

int main(){
	int t,w[12];
	cin>>t;
	for(int i = 0; i < 12; i++){
		cin>>w[i];
	}
	sort(w,w+12,greater<int>());
	for(int i = 0; i <= 12; i++){
		if(t<=0){
			cout<<i<<endl;
			return 0;
		}
		if(i==12){
			cout<<-1<<endl;
			return 0;
		}
		t -= w[i];
	}
	return 0;
}

B.
入力→任意のn進法で不正なものを見つける→任意のn進法で正しいものを見つける→(入力に含まれる最大の数字+1)進法から59進法まで調べる。
で解ける。
解き方によって順番は前後すると思いますが、hourもminuteも1桁のときに-1を返したい場合は、先にhourが23以下であることを確認することが必要となります。60進法のときに成り立つときに-1を返す場合は、hourが23以下であることを確認することは不必要です。(このコードでは前者の方法で解いています)

string str;
vector<int> h,m;
int hlen,mlen;

bool f(int x){
	int t = 0;
	int x2 = 1;
	for(int i = 0; i < hlen; i++){
		t += h[i]*x2;
		if(t>=24) return false;
		x2*=x;
	}
	x2 = 1;t = 0;
	for(int i = 0; i < mlen; i++){
		t += m[i]*x2;
		if(t>=60) return false;
		x2*=x;
	}
	return true;
}

int main(){
	cin>>str;
	int len = str.size(),k=0,k2=0,minl=1,flag=0;
	
	while(str[k] == '0') k++;
	while(str[k2] != ':') k2++;
	int k3 = k2;
	
	for(k2--; k2>=k; k2--){
		if(isdigit(str[k2])){
			h.push_back(str[k2]-'0');
			minl = max(minl,str[k2]-'0');
		}
		else{
			h.push_back(str[k2]-'A'+10);
			minl = max(minl,str[k2]-'A'+10);
		}
	}
	
	
	k = k3+1;
	while(str[k] == '0') k++;
	for(k2 = len-1; k2 >= k; k2--){
		if(isdigit(str[k2])){
			m.push_back(str[k2]-'0');
			minl = max(minl,str[k2]-'0');
		}
		else{
			m.push_back(str[k2]-'A'+10);
			minl = max(minl,str[k2]-'A'+10);
		}
	}
	hlen = h.size(); mlen = m.size();
	if(h.empty()){
		h.push_back(0);
		hlen++;
	}
	if(m.empty()){
		m.push_back(0);
		mlen++;
	}
	if(h[0]>=24){
		cout<<0<<endl;
		return 0;
	}
	if(hlen <= 1 && mlen <= 1){
		cout<<-1<<endl;
		return 0;
	}
	
	for(int i = minl+1; i < 60; i++){
		if(f(i)){
			if(flag) cout<<' '<<i;
			else cout<<i;
			flag = 1;
		}
	}
	if(!flag)cout << 0 << endl;
	return 0;
}

C.
ソートして、差が小さくなるようにします。
例えば、ソート後に100,50,40,20,10となった場合は

1.とりあえず、xに100、yに50を足す。
2.x>yとなるから、yに40、xに20を足す。
3.x>yとなるから、yに10を足す。

とすれば、xとyの個数の差が1以下となり、xとyの(skillの和の)差が最も大きいskill(今の例では100)より小さくなります。
差がa[0]よりも小さくなればよく、a[k]-a[k-1]の絶対値は必ずa[0]以下になることは明らかだから、これで解けます。

int n,s;
vector<int> x,y;
pair<int,int> m[100000];

int main(){
	cin>>n;
	for(int i = 0; i < n; i++){
		cin>>m[i].first;
		m[i].second = i;
	}
	sort(m,m+n,greater<pair<int,int> >());
	for(int i = 0; i+1 < n; i+=2){
		if(s<=0){
			s += m[i].first-m[i+1].first;
			x.push_back(m[i].second);
			y.push_back(m[i+1].second);
		}
		else{
			s -= m[i].first-m[i+1].first;
			x.push_back(m[i+1].second);
			y.push_back(m[i].second);
		}
	}
	if(n%2){
		if(s<=0){
			x.push_back(m[n-1].second);
		}else{
			y.push_back(m[n-1].second);
		}
	}
	cout<<x.size()<<endl;
	for(int i = 0 ; i < x.size(); i++){
		cout<<x[i]+1;
		if(i == x.size()-1)cout<<endl;
		else cout<<' ';
	}
	cout<<y.size()<<endl;
	for(int i = 0 ; i < y.size(); i++){
		cout<<y[i]+1;
		if(i == y.size()-1)cout<<endl;
		else cout<<' ';
	}
	return 0;
}