AtCoder ARC #219 : C - Traveling Door-to-Door Salesman (Elevator)

これはまぁ普通に解けた。
https://atcoder.jp/contests/arc219/tasks/arc219_c

問題

H*Wグリッドで表されるアパートがある。
今左下隅(1,1)のマスにおり、隣接マスをたどって指定したNマスを１回以上通過し、元の位置に戻りたい。

• 横移動は１マスあたりコスト１で可能。
• 縦移動は、1列またはW列にいるとき、コスト0で可能。

条件を満たす最小コストを求めよ。

解法

まず縦移動を１列目でしか行わない場合を求めておく。
縦移動をW列目で１回以上行う場合、指定マスのある行におけるたどり方は以下のいずれかである。

• 1列目からW列目、またはその反対に一気に移動する。
• 一部の指定マスは１列目から到達して戻り、残りはW列目から到達して戻る。

前者を行えるのは２回以上偶数回である。
よって後者のコストをソートしておき、コストの多い行ごとに２行ずつ前者に振り替えた場合のコストを求めればよい。

ll H,W;
int N;
map<int,vector<int>> V;

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].push_back(x-1);
	}
	W--;
	ll ret=0;
	vector<ll> X;
	ll sum=0;
	FORR2(a,b,V) {
		vector<int> C=b;
		sort(ALL(C));
		ret+=C.back()*2;
		
		ll mi=min(1LL*C.back(),W-C[0])*2;
		FOR(i,C.size()-1) mi=min(mi,(W-(C[i+1]-C[i]))*2);
		X.push_back(mi);
		sum+=mi;
	}
	//1回以上横断
	sort(ALL(X));
	while(X.size()>=2) {
		sum+=2*W;
		sum-=X.back();
		X.pop_back();
		sum-=X.back();
		X.pop_back();
		ret=min(ret,sum);
	}
	
	cout<<ret<<endl;
	
}

まとめ

似たような問題考えたことあったのでこちらはすんなりだった。