TopCoder SRM 517 DIV2
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っていう長れは情オリの本選でも見た。本当に解けるようにならないとヤバい、ヤバいよー><