kmjp's blog

競技プログラミング参加記です

AtCoder ARC #219 : G - Traveling Door-to-Door Salesman (Stairs)

これは思いつけても不思議ではないけど、最後詰め切るのに手間取りそう。
https://atcoder.jp/contests/arc219/tasks/arc219_g

問題

基本的な設定はC問題と同じ。
AtCoder ARC #219 : C - Traveling Door-to-Door Salesman (Elevator) - kmjp's blog

ただし、上下移動もコストが1かかるという追加条件が加わる。

解法

移動経路を考えると、通過したマスについて、次数が偶数であってかつ次数が正の場合はそれらが連結していなければならないことになる。
よって行番号の小さい順に以下の状態を求めて行こう。

dp(n,L,R,C) := n行目まで考えたとき、以下の状態の場合における、そこまでの移動経路の総コストの最小値

  • L : (n,1)の次数が0/正の奇数/正の偶数のいずれか
  • R : (n,W)の次数が0/正の奇数/正の偶数のいずれか
  • C : L,Rがともに非0の場合、両者は連結しているか

n行目の次に訪問すべきマスがある行をm行目とすると、移動の仕方は以下を総当たりする必要がある。

  • (n,1)-(m,1)の間のパスは0/1/2の何本か
  • (n,W)-(m,W)の間のパスは0/1/2の何本か
  • m行目にある訪問すべきマスを、以下のいずれかで全部訪問する
    • (m,1)-(m,W)を片道で移動する
    • (m,1)-(m,W)を往復で移動する
    • (m,1)から各マスを訪問し、(m,1)に戻る
    • (m,W)から各マスを訪問し、(m,W)に戻る
    • (m,1)から一部のマスを訪問し(m,1)に戻り、まだ(m,W)から残りのマスを訪問し(m,H)に戻る
ll H,W;
int N;
map<int,vector<int>> V;

ll from[3][3][2];
ll to[3][3][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	cin>>N;
	FOR(i,N) {
		cin>>y>>x;
		V[y-1].push_back(x-1);
	}
	W--;
	FOR(i,3) FOR(j,3) FOR(x,2) from[i][j][x]=1LL<<60;
	from[2][0][0]=0;
	int pre=0;
	int d1,d2,c;
	int p1,p2,q;
	FORR2(y,v,V) {
		ll up=y-pre;
		pre=y;
		
		sort(ALL(v));
		
		ll cross=W;
		ll Lside=2*v.back();
		ll Rside=2*(W-v[0]);
		ll split=2*W;
		v.push_back(0);
		v.push_back(W);
		sort(ALL(v));
		FOR(i,v.size()-1) split=min(split,2*(W-(v[i+1]-v[i])));
		
		FOR(d1,3) FOR(d2,3) FOR(c,2) to[d1][d2][c]=1LL<<60;
		
		//横断
		FOR(d1,3) FOR(d2,3) FOR(c,2) {
			ll cur=from[d1][d2][c];
			if(cur>=1LL<<60) continue;
			assert(!((d1==0||d2==0)&&c));
			FOR(p1,3) FOR(p2,3) FOR(q,3) {
				// 下記の点の次数は偶数
				if((d1+p1)%2) continue;
				if((d2+p2)%2) continue;
				
				//どちらかは必須
				if(p1+p2==0) continue;
				// 非連結な側は辺が必須
				if(c==0) {
					if(d1&&p1==0) continue;
					if(d2&&p2==0) continue;
				}

				int nd1=p1+q;
				if(nd1) nd1=(nd1-1)%2+1;
				int nd2=p2+q;
				if(nd2) nd2=(nd2-1)%2+1;
				
				if(q) {
					//横断する
					chmin(to[nd1][nd2][1],cur+up*(p1+p2)+cross*q);
				}
				else {
					if(nd2==0) {
						chmin(to[nd1][nd2][0],cur+up*(p1+p2)+Lside);
						chmin(to[nd1][2][0],cur+up*(p1+p2)+split);
					}
					else if(nd1==0) {
						chmin(to[nd1][nd2][0],cur+up*(p1+p2)+Rside);
						chmin(to[2][nd2][0],cur+up*(p1+p2)+split);
					}
					else chmin(to[nd1][nd2][c],cur+up*(p1+p2)+split);
				}
			}
		}
		
		swap(from,to);
	}
	ll ret=min({from[2][2][1],from[2][0][0],from[0][2][0]});
	cout<<ret<<endl;
}

まとめ

一時期連結状態を持つ数え上げがyukicoderに頻発してたのになぁ。