TopCoder SRM 569 Div1 Medium TheJediTest

問題

n階立ての建物があって、i階目にはstudents[i]人の人がいる。

Jediは一人でK人の人を倒すことができる。
x人の人が一つの階にいるとき、x/K(切り上げ）人のJediが必要である。

それぞれのstudentsを、動かさないか、上下の隣り合う階に移すことができるとき、
建物の全てのstudentsを倒すのに、最小で何人のJediが要るか求めよ。

制約条件

n≦20
students[i]≦1億
1≦K≦1億

方針

それぞれの階と階との間で、移動するstudentsは一方の向きだけであるとしてよい。
（相殺できるから）

studentsの移動の向きを2^n-1通り決め付けて試す。
移動の向きが決まっているとき、
一番下の階から見ていけば、最適解は貪欲に決定できる。

（Kの倍数になるように調整して移動する。できない場合は、
決めた向きにしたがって、Kの余りで出来るだけ多い人数を移動させる）

O(n)の貪欲法でも解けるっぽい。

ソースコード

class TheJediTest {
	public:
	int minimumSupervisors(vector <int> students, int K) {
		int n = students.size();
		int ans = -1;
		
		vi old = students;
		
		rep(bit, 1 << n - 1){
			vector<ll> v;
			rep(i, n) v.pb(students[i]);
			
			rep(i, n - 1){
				if(bit & 1 << i){
					int tmp = min((K - v[i] % K) % K, (ll)old[i + 1]);
					v[i] += tmp;
					v[i + 1] -= tmp;
				}
				else{
					int tmp = min(v[i] % K, (ll)old[i]);
					v[i] -= tmp;
					v[i + 1] += tmp;
				}
			}
			ll s = 0;
			rep(i, n) s += (v[i] + K - 1) / K;
			if(ans < 0 || ans > s) ans = s;
		}
		return ans;
	}
};