読者です 読者をやめる 読者になる 読者になる

TopCoder SRM 154 Div2

oox

@ichigo_o_reさん & @HETARE09さん と練習してました。
誤差落ち怖い...

300

本日の販売実績が "#{販売額} #{原価}" という文字列で複数与えられる。
『利益÷原価=利益率』とすると、本日の利益率は何%か。(小数点以下は切り捨てて、整数で答えよ)
ただし、原価の総額は0より大きい


このころのTopCoderは、文字列のパースをさせる問題がまだ存在していたようです。
stringstreamを惜しまず使わせていただきました。
0除算が起こらないようになっているのはeasyらしいところ。


450

ROT13という暗号化アルゴリズムを知っているだろうか。
シーザー暗号の一種で、暗号化の際にはアルファベットを13文字後ろにずらせばよい。

もっと使いやすくするために、UPPERCASEとlowercase、数字や空白などが混じっている時の操作も定義することにした。

UPPERCASEは、UPPERCASE内で13文字後ろにずらす
  • A-M → N-Z
  • N-Z → A-M
lowercaseは、lowercase内で13文字後ろにずらす
  • a-m → n-z
  • n-z → a-m
数字は、5つ後ろにずらす
  • 0-4 → 5-9
  • 5-9 → 0-4
空白は、そのままにする。
  • ' ' → ' '

文字列が与えられるので、暗号化せよ。


#include <cctype>


1000

『良い順位付け』のために、「『各項目における順位』を合計した値」を元に順位を決めることになった。
最終的な順位は、次のように決まる。

  1. 各項目における順位を求め、それを合計した値を比較する
  2. ↑でダブった場合は、各項目の得点(順位ではない)の合計値を比較する
  3. ↑もダブった場合は、名前を辞書順比較する

順位付けして、"#{名前} #{『各項目における順位』を合計した値} #{得点の合計}"という書式のStringの配列を返せ


3.の『ダブった場合は』のところで、得点の合計値(浮動小数点数)を == で比較してしまい、誤差落ち。
いわゆる EQ関数 に修正するだけで通ってしまいました(´;ω;`)ブワッ


300

struct ProfitCalculator {
	int percent(vector <string> items) {
		double a = 0.0;
		double b = 0.0;
		rep(i,items.size()) {
			istringstream is(items[i]);
			double fa, fb;
			is >> fa >> fb;
			a += fa;
			b += fb;
		}

		return (int)(100 * (a - b) / a);
	}
};

450

struct SuperRot {
	string decoder(string message) {
		const int N = message.length();
		stringstream ss;
		rep(i,N) {
			const char c = message[i];
			if(isdigit(c)) {
				int d = c - '0';
				ss << (d + 5) % 10;
			}
			else if(islower(c)) {
				int d = c - 'a';
				char nc = ((d + 13) % 26) + 'a';
				ss << nc;
			}
			else if(isupper(c)) {
				int d = c - 'A';
				char nc = ((d + 13) % 26) + 'A';
				ss << nc;
			}
			else {
				ss << c;
			}
		}

		return ss.str();
	}
};

1000

bool EQ(const double &a, const double &b) {
	return fabs(a - b) < EPS;
}

struct Node {
	string name;
	int rank;
	double score;
	vector<double> v;

	void calc() {
		score = accumulate(v.begin(), v.end(), 0.0);
	}

	bool operator <(const Node &c) const {
		if(rank != c.rank) return rank < c.rank;
		if(EQ(score, c.score) == false) return score > c.score;
		return name < c.name;
	}
};

struct ContestScore {
	vector <string> sortResults(vector <string> data) {
		const int N = data.size();
		if(N == 0) return vector<string>();
		vector<Node> v(N);
		rep(i,N) {
			istringstream is(data[i]);
			is >> v[i].name;
			double d;
			while(is >> d) v[i].v.push_back(d);
			v[i].rank = 0;
			v[i].calc();
		}

		const int L = v[0].v.size();
		rep(l, L) {
			vector<int> rv(N);
			rep(i,N) rv[i] = (int)((v[i].v[l] + EPS) * 10);
			sort(rv.rbegin(), rv.rend());
			rep(i,N) {
				v[i].rank += lower_bound(rv.begin(), rv.end(), (v[i].v[l] + EPS) * 10,
					greater<int>()) - rv.begin();
				v[i].rank++;
			}
		}

		sort(all(v));

		vector<string> ret;
		rep(i,N) {
			stringstream ss;
			char score_str[1024];
			sprintf(score_str, "%.1f", v[i].score);
			ss << v[i].name << " " << v[i].rank << " " << score_str;
			ret.push_back(ss.str());
		}

		return ret;
	}