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

TopCoder SRM 517 DIV2

Programming Algorithm TopCoder

Rating: 1061(緑)→962(緑)
レート共々爆死した。なんてことをしてしまったんだ。

あとでデバッグした結果をのせる。

250: MonochromaticBoard

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

class MonochromaticBoard {
public:
	int count(vector<string> board)
	{
		set<int> row;
		for (int i = 0; i < board.size(); ++i) {
			bool f = true;
			for (int j = 0; j < board[i].size(); ++j) {
				if (board[i][j] == 'W') {
					f = false;
					break;
				}
			}
			if (f) 
				row.insert(i);
		}
		if (row.size() == board.size())
			return row.size();
		set<int> col;
		for (int i = 0; i < board[0].size(); ++i) {
			bool f = true;
			for (int j = 0; j < board.size(); ++j) {
				if (board[j][i] == 'W') {
					f = false;
					break;
				}
			}
			if (f) 
				col.insert(i);
		}
		return row.size() + col.size();
	}
	vector<string> rotate(vector<string>& board)
	{
		vector<string> res(board[0].size());
		for (int i = 0; i < res.size(); ++i) {
			res.reserve(board.size());
			for (int j = 0; j < board.size(); ++j) {
				res[i] += board[j][i];
			}
		}
		return res;
	}
	int theMin(vector <string> board) {
		return min(count(board), count(rotate(board)));
	}
};

デバッグするのも面倒だったので1から書き直した。
でもやっぱりこれDIV2Easyのコード量じゃないしもっとサクッと書けないとダメだ…

500: CompositeSmash

EditorialでDP解法を読んだ。自分の思いついた場合分け解法はミスが無いか検証する事が困難なので、ここでDP解法をちゃっちゃと思いつけるかで変わってくると思う。
DP解法で書いてWAするのはデバッグが面倒だし基本線はあってると思うので省略

1000: CuttingGrass

DP本当に分からない・解けない。Editorialも読んだが釈然としなかった。だけどソート→DPっていう長れは情オリの本選でも見た。本当に解けるようにならないとヤバい、ヤバいよー><