SRM526 Div1 Easy - DucksAlignment

問題

h*wのグリッドのいくつかのマスにアヒルがいる
(ただし各行[列]にいるアヒルはたかだか1匹)
アヒルはコスト1で上下左右に1マス動かせる
全てのアヒルを連続する1行[列]に整列させるためにかかるコストの最小値を求める

1 <= h,w <= 50

解法

①まず全てのアヒルを上下移動のみでi行目にまとめる
②その後アヒル同士をヨコ方向で連結するのは、真ん中(偶数匹なら真ん中2匹のうちどっちか)のアヒルに寄せるのが一番コストが小さくなる(典型だから証明略)
③これらのコストの和で答えを更新
この流れを全ての行と列についてやればいい

実装

ph[i]: i行目にいるアヒルのj座標(いなければ-1)

行と列それぞれで試すためにほぼ同じコードが2個連続してるのが美しくないとは思うんだけど・・
黒と白(0と1)ならまとめた方がコスパいいこと多いけどタテとヨコは微妙だよね？🧐

class DucksAlignment {
public:
	int minimumTime(vector<string> s) {
		int h = s.size(), w = s[0].size(), res = inf;
		int ph[50], pw[50];
		memset(ph,-1,sizeof(ph)), memset(pw,-1,sizeof(pw));
		rep(i,h) rep(j,w) if (s[i][j]=='o') ph[i] = j, pw[j] = i;
		rep(i,h) {
			vector<int> p;
			int t = 0;
			rep(j,w) if (pw[j]!=-1) t += abs(pw[j]-i), p.push_back(j);
			sort(all(p));
			int k = p.size();
			reps(j,k/2+1,k) t += p[j]-p[j-1]-1, p[j] = p[j-1]+1;
			for(int j=k/2-1; j>=0; j--) t += p[j+1]-p[j]-1, p[j] = p[j+1]-1;
			chmin(res, t);
		}
		rep(i,w) {
			vector<int> p;
			int t = 0;
			rep(j,h) if (ph[j]!=-1) t += abs(ph[j]-i), p.push_back(j);
			sort(all(p));
			int k = p.size();
			reps(j,k/2+1,k) t += p[j]-p[j-1]-1, p[j] = p[j-1]+1;
			for(int j=k/2-1; j>=0; j--) t += p[j+1]-p[j]-1, p[j] = p[j+1]-1;
			chmin(res, t);
		}
		return res;
	}
};