SRM 648

Easy

最大値は(N/2)*((N+1)/2)
Aを最初にN/2個並べておいて、Bをできるだけ右側に置いていけば良い

int b[100];

class AB {
public:
	string createString( int N, int K ) {
		memset(b, 0, sizeof(b));
		string res = "";
		for(int i = 0; i < (N+1)/2; i++){
			int r = min(K, N/2);
			b[r]++;
			K -= r;
		}
		if(K) return res;
		for(int i = 0; i < N/2+1; i++){
			for(int j = 0; j < b[i]; j++){
				res += 'B';
			}
			if(i<N/2) res += 'A';
		}
		return res;
	}
};

Medium

Nが小さい時は、安いりんごをgreedyに買えば良い.
金額K+1のりんごを買わない場合は、金額を決めたときに買うことができるりんごの個数を簡単に求めることができるので二分探索すれば良い.

Nが大きい時は、金額KのりんごをL回買うことになるが、最初に全てのりんごをL回ずつ買うことで、Nが小さい時の問題に帰着することができる.

ll mod = 1000000007;

class KitayutaMart {
public:
	ll calc(ll x){
		ll res = 0;
		while(x){
			res += x;
			x >>= 1;
		}
		return res;
	}
	ll my2pow(int x){
		ll res = 1, t = 2;
		while(x){
			if(x&1) res = (res*t)%mod;
			x >>= 1;
			t = (t*t)%mod;
		}
		return res;
	}
	int lastPrice( int N, int K ) {
		ll M = N-calc(K);
		ll L = max(0LL, (M+K-1)/K);
		N -= L*K;
		ll lb = 0, ub = K;
		while(ub-lb>1){
			ll md = (lb+ub+1)/2;
			if(calc(md)<N) lb = md;
			else ub = md;
		}
		return ub*my2pow(L)%mod;
	}
};