2011 TCO Qualification Round 2 - BlackWhiteMagic

問題


http://community.topcoder.com/stat?c=problem_statement&pm=11418&rd=14530

・黒と白の石が並べられている配列が与えられる。
・その石をswapすることで、白白・・白黒黒・・黒としたい。
・ただし、swapできる距離1つごとに1回のswapしかできない。
・このとき、必要な最小の操作回数を求める。

解き方


・swapの距離によらず、各1回の操作で白と黒を入れ替えることができそう。
・白と黒が分かれるようにswapする。

→system failed

・問題文を見落としてしまった。
・まず問題文は白→黒の順と決まっていることと、白と黒の数は任意であること。
・問題文をきちんと読んで条件を整理する基本を徹底せねば。

コード


using namespace std;

#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class BlackWhiteMagic {

public: int count(string creatures) {
int n=creatures.size();
int w=0,ret=0;
FORE(i,0,n)if(creatures[i]=='W')w++;
FORE(i,0,w)if(creatures[i]=='B')ret++;

return ret;
}

};
このエントリーをはてなブックマークに追加