TopCoder SRM 589 Div1
今回のSRMはEasyでなかなかのChallenge祭りになっていました。
僕も何とか参加して100点稼ぎました。肝心の解答の方は他の人にChallengeされてしまいましたが、レートが上がったので良しとします。
今回の問題はEasyが貪欲法、Mediumがグラフの問題です。それでは、さっそく解説します。
Easy (250点)
この問題は与えられた文字列をある方法にしたがって変更して回文になるようにするというものです。
ある方法とは文字列中にある特定の文字を別の文字に全て変更するというものです。
ポイントは回文になるためには、各文字が多くとも1回しか変更されないということです。
ですから両端からひっくり返した位置にある文字を比較していって、もし違う文字が出てきたら、どちらかの文字を変更します。
このとき文字列中の出現回数が小さいほうの文字を変更するのが最適です。
気をつけないといけないのが、一度変更した文字をもう一度変更するのをカウントしないようにすることです。
これに気付いていない人がたくさんいたせいで「aabbbbbc」みたいな文字列でChallengeできました。
アルゴリズムの方針としては
- 文字列S中の各文字の出現回数をmapで調べる
- 両端から対応する文字を比較して、違う文字だったら出現回数の少ない方を変更
- 重複で数えるのを防ぐため、変更した文字の出現回数を0にする
- 変更されない方の出現回数はいじらない (これが重要)
という感じで解けます。方針はあっていたのですが、文字を変更していくときの変更の仕方が間違っていてChallengeされてしまいました。なんという凡ミス！
以下が正解のコードです。
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#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;
#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 dump(a) cerr << #a << " = " << (a) << endl
#define dump2(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
typedef pair<int,int> P;
typedef long long LI;
class GooseTattarrattatDiv1 {
public:
int getmin(string S) {
string org = S;
int n = S.length();
map<char,int> mp;
for(int i=0; i<n; i++) {
mp[S[i]]++;
}
int ans = 0;
char ch1, ch2;
for(int i=0; i<n/2; i++) {
if(S[i] != S[n-i-1]) {
if(mp[S[i]] < mp[S[n-i-1]]) {
ch1 = S[n-i-1];
ch2 = S[i];
ans += mp[S[i]];
mp[S[i]] = 0;
} else {
ch1 = S[i];
ch2 = S[n-i-1];
ans += mp[S[n-i-1]];
mp[S[n-i-1]] = 0;
}
for(int j=0; j<n; j++) {
if(S[j] == ch2) S[j] = ch1;
}
}
}
return ans;
}
}
Medium (450点)
この問題は赤、緑、青の3色からなる歯車に関する問題です。
歯車による構造を作るとき、同じ色の歯車は同じ方向に回るようにしたいというのがこの問題の目標です。
歯車の色のリストと現在どの歯車同士がかみ合っているかの情報が与えられたときに、最小何個の歯車を外せば目標を達成できるかを答えます。
ポイントは同じ色の歯車は初期状態でかみ合っていることがないということです。
この場合、目標を達成するためには赤、緑、青のうち特定の2色だけを外せば十分なのです。
では、仮に赤と緑だけを外すことにし、青は外さないことにしましょう。
もし複数の青が初期状態で違う方向に回っていれば2つの青い歯車の間には赤と緑の歯車が偶数個存在することになります。
この時、同じ色が初期状態でかみ合っていることはないわけですから、「赤、緑、赤、緑、・・・、赤、緑」というように交互に並んでいるはずです。
このような場合には、赤か緑のうちどれか1つを外せばよいことになりますが、これは「赤と青」あるいは「緑と青」の組み合わせでの二部マッチングを考える問題になります。
どういうことかというと、上のような場合で赤と青が異なる方向に回るのであれば、緑と青は同じ方向に回ります。
つまり緑と青の間のかみ合わせを解除しなくてはなりません。これは緑と青の歯車の間での最小点カバーを考える問題になるからです。
また仮に間にある赤と緑の歯車のうち同色で同じ方向に回ってしまうようなものがあるのならば、その間には必ず青の歯車が存在します。
こうして考えていくと、赤と緑、緑と青、青と赤という2色の組み合わせで二部グラフを作って、そのグラフでの最小点カバーを解きます。
得られる3つの値のうち最も少ない値が求める答えとなる、というわけです。
以下が正解のコードです。
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#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 pair<int,int> P;
typedef long long LI;
struct edge {
int to, cap, rev;
};
const int INF = 1 << 30;
const int MAX_V = 55;
vector<edge> G[MAX_V];
bool used[MAX_V];
class GearsDiv1 {
public:
int n;
vector<int> C;
vector<string> path;
void add_edge(int from, int to, int cap) {
edge e1 = { to, cap, (int)G[to].size() };
edge e2 = { from, 0, (int)G[from].size() };
G[from].push_back(e1);
G[to].push_back(e2);
}
int dfs(int v, int t, int f) {
if(v == t) return f;
used[v] = true;
for(int i=0; i<G[v].size(); i++) {
edge& e = G[v][i];
if(!used[e.to] && e.cap > 0) {
int d = dfs(e.to, t, min(f, e.cap));
if(d > 0) {
e.cap -= d;
G[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
int maxflow(int s, int t) {
int flow = 0;
for(;;) {
memset(used, 0, sizeof(used));
int f = dfs(s, t, INF);
if(f == 0) break;
flow += f;
}
return flow;
}
int solve(int c1, int c2) {
int S = n;
int T = n + 1;
int V = n + 2;
for(int i=0; i<V; i++) G[i].clear();
for(int i=0; i<n; i++) {
if(C[i] == c1) {
add_edge(S, i, 1);
}
if(C[i] == c2) {
add_edge(i, T, 1);
}
}
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(path[i][j] == 'Y' && C[i] == c1 && C[j] == c2) {
add_edge(i, j, 1);
}
}
}
int cost = maxflow(S, T);
return cost;
}
int getmin(string color, vector <string> graph) {
this->n = color.size();
this->path = graph;
C = vector<int>(n);
for(int i=0; i<n; i++) {
if(color[i] == 'R') C[i] = 0;
if(color[i] == 'G') C[i] = 1;
if(color[i] == 'B') C[i] = 2;
}
int mi = INF;
mi = min(mi, solve(0, 1));
mi = min(mi, solve(1, 2));
mi = min(mi, solve(2, 0));
return mi;
}
}
実装自体はそれほど難しくないと思います。ただ、どうして特定の二色の間での最小点カバーになるのかを考えるのは結構一苦労でした。
まとめ
今回はテストケースが弱かったことに気づけたので良かったですが、この問題を落とすのはよくないですね。
しかも落ちるケースが分かっていたのに、凡ミスで落ちるというのが特によくないです。
精進あるのみですね。最後までお読みいただきありがとうございました。