yukicoder : No.596 郵便配達

実装的には★４位でもいい気がする。
https://yukicoder.me/problems/no/596

問題

[0,N)の1次元の数直線上に、M個の郵便局と多数の家がある。
郵便局の位置と、各郵便局に対応する郵便物の配達先の家(複数)の位置の一覧が与えられる。

数直線上を移動し、全郵便局の持つ郵便物を配達したい。
一旦郵便局を通過すると、その段階で全郵便物を預かることができる。
任意の位置で開始・終了できるとき、総移動量の最小値を求めよ。

解法

隣接する整数座標同士の移動回数は最大３回である。
４回移動、すなわち２往復以上する意味はない。

これらの移動回数の組み合わせは以下の通り。

0回
左1回
右1回
左1回右1回
左1回右2回
左2回右1回

各郵便局について、郵便局の位置と配達先座標の最小値最大値から、各隣接整数座標間において、少なくとも１回は左向き・右向きの移動を行う必要があるかどうかがわかる。
例えば郵便局が座標5、配達先の座標の最小値が2なら、(2,3),(3,4),(4,5)の座標間は左向きの移動を含まなけれなならない。
これについてはimos法の要領で数え上げれば、各座標間で左右への移動が必要かどうかO(N+(家の数))で求められる。

あとは以下の過去問の要領で座標の小さい順に、状態に対応した移動量の最小値を求めていこう。
座標間で左右移動が必要であれば、必要な移動を含む状態遷移しか取れないものとする。
yukicoder : No.541 3 x N グリッド上のサイクルの個数 - kmjp's blog
yukicoder : No.569 3 x N グリッドのパスの数 - kmjp's blog

以下注意点。

移動経路は閉路か単一のパスでなければならない。よってパスの始点・終点は最大1個までしか現れてはいけない。
- そこで始点・終点の有無も状態としてもとう。
郵便局と家の位置が同じ場合見逃しがちなので注意。
- 状態遷移として、最小の座標の家より後にパスが始まってはならず、最大の座標の家より前にパスが終わらないようにすると回避できる。

int N,M;
int L[7070707], R[7070707];

int add[7]={0,1,1,2,3,3,0};
int lef[7]={0,0,1,1,1,1,0};
int rig[7]={0,1,0,1,1,1,0};
// before, ->, <- , <-> , ->/<-/->, <-/->/<-, done
// 1-non 2-start 3-end
int mat[7][7]={
	{1,2,3,1,2,3,1},
	{0,1,0,3,1,0,3},
	{0,0,1,2,0,1,2},
	{0,2,3,1,0,0,1},
	{0,1,0,0,1,0,3},
	{0,0,1,0,0,1,2},
	{0,0,0,0,0,0,1},
};
int from[7][2][2];
int to[7][2][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	int miX=N,maX=0;
	
	FOR(i,M) {
		int X,miy,may;
		cin>>X>>x;
		miy=may=X;
		while(x--) {
			cin>>y;
			miy=min(miy,y);
			may=max(may,y);
		}
		L[miy]++;
		L[X]--;
		R[X]++;
		R[may]--;
		miX=min(miX,miy);
		maX=max(maX,may);
	}
	
	FOR(i,7) FOR(x,2) FOR(y,2) from[i][x][y]=1<<30;
	from[0][0][0]=0;
	FOR(i,N) {
		FOR(j,7) FOR(x,2) FOR(y,2) to[j][x][y]=1<<30;
		
		FOR(y,7) {
			if(L[i]&&lef[y]==0) continue;
			if(R[i]&&rig[y]==0) continue;
			FOR(x,7) if(mat[x][y]) {
				FOR(j,2) FOR(k,2) {
					int j2=j+(mat[x][y]==2);
					int k2=k+(mat[x][y]==3);
					if(j2<2 && k2<2) to[y][j2][k2]=min(to[y][j2][k2],from[x][j][k]+add[y]);
				}
			}
		}
		
		if(i>=miX) to[0][0][0]=1<<30;
		if(i+1<=maX) to[6][0][0]=to[6][1][1]=1<<30;
		
		L[i+1]+=L[i];
		R[i+1]+=R[i];
		swap(from,to);
	}
	
	cout<<min(from[6][0][0],from[6][1][1])<<endl;
}

まとめ

過去問に類題が出ていたのに…。