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

TopCoder SRM 521 DIV2

Programming Algorithm TopCoder

Rating: 1087(緑)→1143(緑)
レーティング的にはDIV1が段々と見えてきていて嬉しい。この調子でがんばろう。
System Testが荒れたので人権のある順位になったが、荒れる意味がわからない。
回全体としては不評だった。難易度設定がおかしい。

679.96 Point

250: RedAndGreen

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

class RedAndGreen {
public:
	int minPaints(string row) {
		vector<int> greens(row.size()), reds(row.size());
		for (int i = 0; i < row.size(); ++i) {
			if (i != 0)
				greens[i] = greens[i - 1];

			if (row[i] == 'G')
				greens[i]++;
		}
		for (int i = row.size() - 1; 0 <= i; --i) {
			if (i != row.size() - 1)
				reds[i] = reds[i + 1];

			if (row[i] == 'R')
				reds[i]++;
		}

		int minimum = reds[0];
		for (int i = 0; i < row.size() - 1; ++i) {
			minimum = min(minimum, greens[i] + reds[i + 1]);
		}
		minimum = min(minimum, greens.back());
		return minimum;
	}
};

212.20 Point

若干書き始めで混乱してしまったのでこの点数になってしまった。
もっと低いかと思ったが全般的にいろんな事がはやくなってきているのでこんなもんだった。

500: MissingParentheses

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <numeric>
using namespace std;

class MissingParentheses {
public:
	int countCorrections(string par) {
		if (par.empty())
			return 0;
		vector<bool> paired(par.size(), false);
		for (int i = 0; i < par.size(); ++i) {
			if (paired[i])
				continue;
			if (par[i] == '(') {
				for (int j = i + 1, nest = 1; j < par.size(); ++j) {
					if (par[j] == '(')
						nest++;
					if (par[j] == ')')
						nest--;
					if (nest == 0) {
						paired[i] = paired[j] = true;
						break;
					}
					if (nest < 0)
						break;

				}
			}
		}
		int res = paired.size() - accumulate(paired.begin(), paired.end(), 0);
		return res;
	}
};

467.76 Point

たしかに簡単すぎると思う。

最後のaccumulateはaccumulate(paired.begin(), paired.end(), paired.size(), minus());とも書けるらしいが、STLマニュアルを引く時間がもったいなかったのでこうなりました。

1000:

long longに釣られた。