TopCoder SRM 526 過去問

SRM526 の Div2 Easy Medium を解きました。

Easy

ABC三種類の文字からなる文字列が存在する。
先頭からi文字目以降に何種類の文字があるかを格納したvectorを返す。

解法

ケツからみていくだけです。

提出コード

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <stack>
#include <deque>
#include <queue>
#include <functional>

using namespace std;

#define REP(i,s,e) for (int i = int(s); i != int(e); i++)
#define rep(i,e) REP(i,0,e)
#define foreach(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ALL(c) ((c).begin(), (c).end())
#define ll long long
#define VI vector<int>

class CheatingQuiz {

	public: vector<int> howMany(string answers) {
		int count = 0;
		bool abc[3];
		memset(abc,false,sizeof(abc));
		vector<int> ans;
		for(int i = answers.length()-1; i >= 0;i--){
			if(count == 3){
				ans.push_back(3);
				continue;
			}
			switch(answers[i]){
			case 'A':
				if(!abc[0]){
					abc[0] = true;
					count++;
				}
				break;

			case 'B':
				if(!abc[1]){
					abc[1] = true;
					count++;
				}
				break;

			case 'C':
				if(!abc[2]){
					abc[2] = true;
					count++;
				}
				break;
			}
			ans.push_back(count);
		}
		reverse( ans.begin(), ans.end() );
		return ans;
	}

};

Medium

n行m列の行列がある。
各行、各列ごとに最大１羽、アヒルが居る。 
アヒルを移動させて、縦でも横でもいいから整列させたい。
アヒルは、移動先が空いていればどこへでも移動が可能で、移動にかかる時間はハミルトン距離によって算出される。
整列するのにかかる最小の時間を求めよ。

解法

どういう整列のさせ方をするかが決まれば、その整列の実現にかかる最小の時間は一意に定まる。
よって、全通り試して最小の時間を返せばよい。
より具体的には、例えば横に並べる場合、最も左に居るアヒルを列の最も左に移動させ、そのアヒルの次に最も左に居るアヒルをその右へ移動させ。。。と整列させる。
縦に並べる場合も同じである。
この整列のさせ方が最小の時間を取ることは、図を書けば直ちに分かる。
実装では、二次元の構造体にアヒルの位置を記憶させ、vectorにしまったのち、xとyそれぞれに対してバブルソートを行わせる関数を実装して対処した。

提出コード

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <stack>
#include <deque>
#include <queue>
#include <functional>

using namespace std;

#define REP(i,s,e) for (int i = int(s); i < int(e); i++)
#define rep(i,e) REP(i,0,e)
#define foreach(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ALL(c) (c).begin(), (c).end()
#define ll long long
#define VI vector<int>
#define INF 1<<30

typedef struct pos{
	int x;
	int y;

	int hamiltone_distance(int _x, int _y){
		return (abs(x - _x) + abs(y - _y));
	}
};

void sort_column(vector<pos>& s){
	bool recursive = false;
	REP(i,1,s.size()){
		if(s[i-1].y > s[i].y){
			swap(s[i],s[i-1]);
			recursive = true;
		}
	}
	if(recursive) sort_column(s);
}

void sort_row(vector<pos>& s){
	bool recursive = false;
	REP(i,1,s.size()){
		if(s[i-1].x > s[i].x){
			swap(s[i],s[i-1]);
			recursive = true;
		}
	}
	if(recursive) sort_column(s);
}

class DucksAlignment {

	public: int minimumTime(vector<string> grid) {
		int ans = INF;
		int column = grid.size();
		int row = grid[0].length();
		vector<pos> ret;
		rep(i,column) rep(j,row){
			if(grid[i][j] == 'o'){
				pos tmp = {j,i};
				ret.push_back(tmp);
			}
		}
		int sum;
		sort_row(ret);
		rep(i,column) rep(j,row-ret.size()+1){
			sum = 0;
			rep(k,ret.size()) sum += ret[k].hamiltone_distance(j+k,i);
			ans = min(sum,ans);
		}
		swap(column,row);
		sort_column(ret);
		rep(i,column) rep(j,row-ret.size()+1){
			sum = 0;
			rep(k,ret.size()) sum += ret[k].hamiltone_distance(i,j+k);
			ans = min(sum,ans);
		}
		return ans;
	}
};