WUPC 2019 : G - Teishoku

これは200ptの中でも簡単で、解いた人も多いね。
https://atcoder.jp/contests/wupc2019/tasks/wupc2019_g

問題

M人の学生が食堂で列を成しており、それぞれN種類の定食のいずれかを希望している。
食堂運営側としては、N種類の定食の提供順は任意にできる。
ただ、各学生は自身より後ろに並んでいる人が先に提供を受けると1人不満度が1上昇する。
最適な提供順により、総不満度を最小化せよ。

解法

先に前処理として、ある定食の前に別のある定食が提供された場合に増加する不満度を列挙しておく。
あとは単純なbitDPで、コストが最小となる提供順を順次求めていけばよい。

int N,M;
int A[202020];
ll mo[202020][15];
ll S[15][15];
ll dp[1<<15];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) cin>>A[i];
	for(i=M-1;i>=0;i--) {
		FOR(j,N) {
			mo[i][j]=mo[i+1][j];
			if(j!=A[i]) S[j][A[i]]+=mo[i+1][j];
		}
		mo[i][A[i]]++;
	}
	
	FOR(i,1<<N) dp[i]=1LL<<60;
	dp[0]=0;
	for(int mask=0;mask<1<<N;mask++) {
		FOR(i,N) if((mask&(1<<i))==0) {
			ll add=0;
			FOR(j,N) if((mask&(1<<j))==0) add+=S[i][j];
			dp[mask|(1<<i)]=min(dp[mask|(1<<i)],dp[mask]+add);
		}
	}
	
	cout<<dp[(1<<N)-1]<<endl;
}

まとめ

これBよりも簡単でない？