SRM554 Div1

今回も結果が良くないのに、challengeのお陰で、ratingが上がりました。

Easy

解法

このソースのように場合分けする。
赤と青のレンガの高さが同じ時は、積める個数を数える。
違うときは、赤が1個多い時と、青が1個多い時を区別して数える。

ソース

class TheBrickTowerEasyDivOne{
public:
	int find(int rc, int rh, int bc, int bh) {
		int t = min(rc,bc);
		if(rh==bh){
			if(rc==bc)return (2*t);
			else return (2*t+1);
		}else {
			if(rc==bc)return (3*t);
			else return (3*t+1);
		}
 	}
};

Medium

本番では、ソートしてから、最小値を動かすだけだったので、落ちました。

解法

最小値がどこかにあって、そこを中心にして、外側に単調増加するときに距離が最小となる。
前から見ていって、前の塔より小さければ追加して、大きければ追加しないことを繰り返す。追加出来無かった塔は、最小値の塔よりも右側にあるから、ソートして追加する。
これで、最初の条件を満たして、辞書順で最小のものを作れます。
実際の実装では、追加したりする代わりに、スワップしました。

ソース

class TheBrickTowerMediumDivOne{
public:
	vector <int> find(vector <int> s) {
		int n = s.size();
		if(n==1){
			vector<int> a;
			a.push_back(0);
			return a;
		}
		vector<pair<int,int> > ps(n);
		for(int i = 0; i < n; i++){
			ps[i].first = s[i];
			ps[i].second = i;
		}
		int mn = 50;
		for(int i = 0; i < n; i++){
			mn = min(mn,s[i]);
		}
		bool dec = mn!=s[0];
		for(int i = 1; i < n;){
			if(mn==ps[i].first){
				i++;
				dec = false;
				continue;
			}
			if(dec){
				if(ps[i-1].first<ps[i].first){
					for(int j = i;; j++){
						swap(ps[j],ps[j+1]);
						if(ps[j].first==mn)break;
					}
				}else i++;
			}else {
				vector<pair<int,int> >::iterator it;
				for(it = ps.begin(); *it!=ps[i]; ++it);
				sort(it,ps.end());
				break;
			}
		}
		vector<int> ans(n);
		for(int i = 0; i < n; i++){
			ans[i] = ps[i].second;
		}
		return ans;
	}
};

Rating 1347 -> 1425