SRM 526 250pt : DucksAlignment

TopCoder

問題概要

H*W(H,W<50)のボードのいくつかに人がいる。同じ列(行)にはたかだか一人しかいない。各人は移動して一列に隙間なく並ぶ。移動(マンハッタン距離)の総コストの最小値を求める問題。

考えたこと

  • どっか1マスに集めるときの最小値を求める問題？どこに集まるか全探索するだけじゃん。
  • サンプル合わない。誤読していた。一列に集まるのか。じゃあどの列に集まるか全探索だ。
  • サンプル合わない。隙間なく並ぶのか。さてどうしよう。
  • 最後に転置とればよいので横に並ぶと仮定してよい。
  • 基本は全探索なので、どの行に集まるのか全探索することを考えよう。
  • で、隙間なく並ぶので一番左の人がどこにいくのかも全探索しよう。
  • このとき、初期位置と並んだ後でx座標の順序は保存される気がする…。
    • 詳しい証明はしてないけどマンハッタン距離だから大丈夫だろう…。
  • サンプルちょっとだけ通らない。ああソートしてなかった。
  • 修正。サンプル通ったし時間も遅かったのでよく確かめずにさっさと提出した。

本番中提出したコード

計算量O((W*H)^2)。多分もう少し落とせるはず。

#include <string>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cstdio>
using namespace std;

const int INF = 1<<29;
const int MAX_W = 50;

bool on[MAX_W];

char buf[MAX_W][MAX_W+1];

struct DucksAlignment {

	int minimumTime(vector <string> grid) {
		int H = grid.size(), W = grid[0].length();

		int ans = INF;

		for(int loop=0; loop<2; loop++){
			for(int i=0; i<H; i++){
				int tmp = 0;
				vector<int> xs;
				for(int y=0; y<H; y++){
					for(int x=0; x<W; x++)if(grid[y][x] == 'o'){
						tmp += abs(y - i);
						xs.push_back(x);
					}
				}

				sort(xs.begin(), xs.end());

				for(int k=0; k+(int)xs.size() <= W; k++){
					int tmp2 = 0;
					for(int j=0; j<(int)xs.size(); j++){
						tmp2 += abs(xs[j] - (k+j));
					}
					ans = min(tmp+tmp2, ans);
				}

			}

			if(loop == 1)break;

			for(int i=0; i<H; i++){
				for(int j=0; j<W; j++){
					buf[j][i] = grid[i][j];
				}
			}

			swap(W, H);

			grid = vector<string>(H);

			for(int i=0; i<H; i++){
				grid[i] = string(buf[i]);
			}

		}

		return ans;
	}

};