TopCoderOpen 2022 Round2B : Hard ChargingACarFleet

またしょうもないミスで落とす…。
https://community.topcoder.com/stat?c=problem_statement&pm=17601

問題

N台の電気自動車をMか所の充電ステーションで充電したい。
各車、どこの充電ステーションで充電してもよいし、各車充電にかかる時間はステーションに依存いない。
1つの充電ステーションでは同時に1台しか充電できないし、一度充電し始めたら充電し終わるまで車を動かせない。

ここで、以下のパラメータが与えられる。

• 車iのパラメータ
  • 車のサイズS[i]
  • 充電にかかる時間C[i]
  • 充電未完の状態で、1時間1ごとにかかるペナルティP[i]
• 各充電ステーションjのパラメータ
  • ステーションが利用可能となる時刻T[i]
  • ステーションを利用可能な車のサイズの最大値SS[i]

最適な場所・順序で車を充電した場合、全車が充電し終わるまでにかかるペナルティの最小値を求めよ。
また、その時のステーションの利用の仕方の例を答えよ。

解法

Nが小さいのでBitDPで解く。
どの車をどのステーションに割り当てるか、O(3^N)のbitDPで総当たりしていけばよい。
同じステーションを複数台で使う場合、C[i]*P[i]の大きい順に先に使うようにするとよい。

ll from[1<<13];
vector<pair<int,ll>> C[1<<13];
vector<int> order[1<<13];

class ChargingACarFleet {
	public:
	vector<long long> charge(vector <int> chargingTime, vector <int> penalty, vector <int> carSize, vector <int> spotAvailable, vector <int> spotSize) {
		int N=chargingTime.size();
		int M=spotAvailable.size();
		
		int i,j,k,s;
		int mask;
		FOR(mask,1<<N) {
			C[mask].clear();
			from[mask]=1LL<<60;
			order[mask].clear();
			if(mask) {
				FOR(i,N) if(mask&(1<<i)) order[mask].push_back(i);
				FOR(i,N) FOR(j,order[mask].size()-1) {
					if(1LL*chargingTime[order[mask][j+1]]*penalty[order[mask][j]]<1LL*chargingTime[order[mask][j]]*penalty[order[mask][j+1]]) {
						swap(order[mask][j],order[mask][j+1]);
					}
				}
			}
		}
		from[0]=0;
		FOR(i,N) C[0].push_back({0,0});
		FOR(i,M) {
			int can=0;
			FOR(j,N) if(carSize[j]<=spotSize[i]) can|=1<<j;
			for(mask=(1<<N)-1;mask>=0;mask--) if(from[mask]<1LL<<60) {
				int cand=((1<<N)-1)^mask;
				for(int sm=cand;sm>=0;sm--) {
					sm&=cand;
					if(sm==0) break;
					if((sm&can)!=sm) continue;
					ll add=0;
					ll now=spotAvailable[i];
					FORR(c,order[sm]) {
						now+=chargingTime[c];
						add+=now*penalty[c];
					}
					if(from[mask|sm]>from[mask]+add) {
						from[mask|sm]=from[mask]+add;
						vector<pair<int,ll>> nex=C[mask];
						now=spotAvailable[i];
						FORR(c,order[sm]) {
							nex[c].first=i;
							nex[c].second=now;
							now+=chargingTime[c];
						}
						C[mask|sm]=nex;
					}
				}
				
			}
		}

		vector<ll> R(2*N+1);
		R[0]=from[(1<<N)-1];
		FOR(i,N) {
			R[i+1]=C[(1<<N)-1][i].first;
			R[i+N+1]=C[(1<<N)-1][i].second;
		}
		return R;
	}
}

まとめ

本番、ソート順を間違えるというしょうもないミスをした。