TopCoder 2014 Open Algorithm Round 1B
こんにちはtatsyです。
本日はTCO2014のAlgoRound 1Bを解説します。
Easy (200点)
問題
メールが良い行と悪い行から構成されている。良い行の場合にはG点を加算し、悪い行の場合にはB点を減算する時、メールを上から読んでいって途中で点数が負になったら、そのメールをスパムだと扱う。もし途中で一度も負にならなければ、そのメールはスパムではない。与えられたメールがスパムかどうかを判定せよ。
解法
とても簡単な問題です。メールの行の良し悪しを表す配列を見ていって、問題に書かれている通りにシミュレーションすればいいだけです。
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include <utility>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <climits>
using namespace std;
typedef long long lint;
typedef pair<lint,lint> pll;
#define REP(i,n) for(lint i=0; i<n; i++)
#define REPP(i,s,e) for(lint i=s; i<=e; i++)
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
class SpamChecker {
public:
string spamCheck(string judge, int good, int bad) {
int n = judge.size();
int pt = 0;
REP(i,n) {
pt += judge[i] == 'o' ? good : -bad;
if(pt < 0) return "SPAM";
}
return "NOT SPAM";
}
};
Medium (600点)
問題
今草原に羊と狼がいて、羊を守るためにフェンスを作りたい。フェンスはグリッド状だと仮定された草原の枠線上をまっすぐに上の端から下の端まで、あるいは左の端から右の端まで作られる。このとき、羊と狼を分離するために必要なフェンスは最低いくつ必要か？
解法
まず問題の条件を確認すると、草原の一辺の長さが高々16であることが分かる。なので、縦方向のフェンスの立て方は最大2^15のパターンを全部しらべて、その各々に対して横方向のフェンスの立て方を最適にすることを考える。
与えられた縦方向のフェンスの立て方について、横方向にグリッドを眺めていき、各行に羊と狼が同居していないかどうかを調べます。
もし同居していればその場合は不正になるので、適当に大きな値を返して答えにならないようにします。
もし同居していなければ、前の行の同じ区分において、存在していたのは狼なのか羊なのかを保存しておいて、もし新しい行でのそれが前の状態でのそれと異なればそこにはフェンスを立てなくてはなりません。
注意すべきことは何もいない部分をどう扱うかというところで、もし前の行に何もいない時には、それより前の最新状態を保持するようにしておく必要があります。
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include <utility>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <climits>
using namespace std;
typedef long long lint;
typedef pair<lint,lint> pll;
#define REP(i,n) for(int i=0; i<n; i++)
#define REPP(i,s,e) for(int i=s; i<=e; i++)
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
const int INF = 1<<20;
class WolvesAndSheep {
public:
int n, m;
vector<string> field;
int calc(vector<int> row) {
vector<char> prev(row.size(), '.');
int ncol = 0;
for(int c=0; c<m; c++) {
vector<char> here(row.size(), '.');
int lo = 0;
for(int k=0; k<row.size(); k++) {
int hi = row[k];
char p = '.';
for(int r=lo; r<hi; r++) {
if(field[r][c] != '.') {
if(p != '.' && p != field[r][c]) return INF;
p = field[r][c];
}
}
here[k] = p;
lo = hi;
}
bool isNeed = false;
for(int k=0; k<row.size(); k++) {
if(prev[k] != '.' && here[k] != '.' && prev[k] != here[k]) {
isNeed = true;
}
}
if(isNeed) {
ncol++;
prev.swap(here);
} else {
for(int k=0; k<row.size(); k++) {
if(here[k] != '.') {
prev[k] = here[k];
}
}
}
}
return ncol;
}
int getmin(vector <string> fld) {
this->field = fld;
this->n = fld.size();
this->m = fld[0].size();
int ans = INF;
for(int mask=0; mask<(1<<(n-1)); mask++) {
vector<int> row;
for(int k=0; k<n-1; k++) {
if((mask & (1<<k)) != 0) {
row.push_back(k+1);
}
}
row.push_back(n);
int ncol = calc(row);
ans = min(ans, (int)row.size() + ncol - 1);
}
return ans;
}
};
まとめ
今回はMediumが解けそうで解けず、楽勝のEasyだけを解いて終了。予選は突破できたけどあまり納得いかない感じです。
次もがんばります。