AtCoder ABC #232 (M-SOLUTIONS プロコンオープン2021) : G - Modulo Shortest Path

Gまではすんなり。
https://atcoder.jp/contests/abc232/tasks/abc232_g

問題

N頂点の有向グラフがある。
N要素の整数列が2つA,Bがある。
頂点i→jには、コスト(A[i]+B[j]) % Mの有向辺が張られているものとする。

頂点番号1の頂点からNの頂点に至るパスの総コストの最小値を求めよ。

解法

1～NのPermutation Pを、B[P[k]]が昇順となるように取ったとする。
iに対するkを、(A[i]+B[P[k]])%Mが最小となるkとする。
その場合、i→P[k+1]に至るコストは、(A[i]+B[P[k]])%M+(B[P[k+1]]-B[P[k]])となる。
これは言い換えると、一回A[i]のコストを払えば、以後Bの差分だけ払えば他の頂点に遷移できることを示す。

このアイデアをもとに2N頂点のグラフを作る。
元の頂点に対応する点をU[i]、追加する頂点をV[i]とする。

• 1回A[i]のコストを払うことを、U[i]→V[P[k]]で表現する。すなわち、U[i]→V[P[k]]のコストは(A[i]+B[P[k]])%Mである。
• V[i]→U[i]はコスト0で遷移できる。
• V[P[k]]→V[P[k+1]]のコストは、(B[P[k+1]]-B[P[k]])。

あとはこのグラフでダイクストラ法を行うだけ。

int N,M;
int A[202020],B[202020];
vector<pair<int,int>> Bs;
set<int> S;
ll dp[404040];

vector<pair<int,int>> E[404040];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>A[i];
	FOR(i,N) {
		cin>>B[i];
		Bs.push_back({B[i],i});
		Bs.push_back({B[i]+M,i});
	}
	sort(ALL(Bs));

	
	FOR(i,N) {
		x=Bs[i].second;
		y=Bs[i+1].second;
		E[N+x].push_back({N+y,Bs[i+1].first-Bs[i].first});
		E[N+i].push_back({i,0});
	}
	
	FOR(i,N) {
		int mi=M-A[i];
		int cur=lower_bound(ALL(Bs),make_pair(mi,-1))-Bs.begin();
		
		E[i].push_back({N+Bs[cur].second,(Bs[cur].first+A[i])%M});
	}
	
	FOR(i,2*N) dp[i]=1LL<<60;
	dp[0]=0;
	priority_queue<pair<ll,int>> Q;
	Q.push({0,0});
	while(Q.size()) {
		ll co=-Q.top().first;
		int cur=Q.top().second;
		Q.pop();
		if(dp[cur]!=co) continue;
		FORR2(e,c,E[cur]) if(dp[e]>co+c) {
			dp[e]=co+c;
			Q.push({-dp[e],e});
		}
	}
	cout<<dp[N-1]<<endl;
	
}

まとめ

これはさっと思いつけて良かった。