AOJ 2312: Magical Girl Sayaka-chan

解法

音程の最小値と最大値の間は、単調にすべきである。(単調で無かったらswapしてよりよい状態にできる)
音程をソートして、最小値から考えることにする。常に、左が右に追加していけばよいが、実はgreedyでよいことが分かる。floor(スコアの和/L)の部分はどうにもならないので、スコア%Lだけを考えれば良い。スコア%Lの和がL以上になると余計に答えが大きくなってしまうので、できるだけ超えないようにしなければならない。スコアの和は順次計算すればよく、mod Lでのスコアの値が大きい方に追加して、mod Lでのスコアを更新すればよい。

コード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

ll tk(vector<ll> &ss, int a, int b){ // [a,b]
	return ss[b+1]-ss[a];
}

int main(){
	ll n, m, l;
	cin>>n>>m>>l;
	vector<ll> v(n), s(m);
	for(ll &x: v){
		cin>>x;
		x--;
	}
	for(ll &x: s)
		cin>>x;

	vector<ll> ss(m+1, 0);
	for(int i = 0; i < m; i++){
		ss[i+1] = ss[i]+s[i];
	}	
	sort(v.begin(), v.end());
	ll res = 0;
	ll an, bn;
	an = bn = s[v[0]];
	for(int i = 1; i < n-1; i++){
		ll diff = tk(ss, v[i-1]+1, v[i]);
		an += diff;
		bn += diff;
		ll &cn = an%l>bn%l?an:bn;
		res += cn/l;
		cn = s[v[i]];
	}
	ll diff = tk(ss, v[n-2]+1, v[n-1]);
	an += diff;
	bn += diff;
	res += an/l + bn/l;

	cout<<res<<endl;

	return 0;
}