Round 1Bに参加した。
結果は、oooxoxで見事Round 1Cへの出場権を獲得した。
とりあえず復習したので、ソースをはっておく。
A. Getting the Digits
0-9の数字をアルファベットで書いたときに、Zは"ZERO"にしか出てこない。
よってZの数を数えれば、0の数がわかる。
0は消えたので、1-9のアルファベット表記を考える。Xは"SIX"にしか出てこない。
よってXの数を数えれば、6の数がわかる。
6は消えたので{1,2,3,4,5,7,8,9}のアルファベット表記を考える。Wは"TWO"にしか出てこない。よってWの数を数えれば、2の数がわかる。
....
という方針で解く。
using namespace std;
#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)
int freq[128];
int cnt[10];
tuple<string, char, int> vs[] = {
{"ZERO", 'Z', 0},
{"SIX", 'X', 6},
{"TWO", 'W', 2},
{"FOUR", 'U', 4},
{"THREE", 'R', 3},
{"FIVE", 'F', 5},
{"ONE", 'O', 1},
{"SEVEN", 'S', 7},
{"EIGHT", 'T', 8},
{"NINE", 'I', 9}
};
void solve() {
string s;
cin >> s;
memset(freq, 0, sizeof(freq));
memset(cnt, 0, sizeof(cnt));
for (auto &c: s)
freq[c]++;
for (auto &v : vs) {
string x;
char y;
int z;
tie(x,y,z) = v;
cnt[z] = freq[y];
for (auto &c: x)
freq[c] -= cnt[z];
}
for (int i = 0; i < 10; i++)
for (int j = 0; j < cnt[i]; j++)
cout << i;
cout << endl;
}
int main() {
ios_base::sync_with_stdio(0);
int T;
cin >> T;
REP (i, T) {
cerr << "Case #" << i+1 << ": " << endl;
cout << "Case #" << i+1 << ": ";
solve();
}
return 0;
}
B. Close Match
2つの数をA, Bとする。Aの桁数をnとする。
A > Bが確定ならば、Aの後続の?は0で埋め、Bの?は9で埋めればよい。
A < Bが確定ならば、Aの後続の?は9で 埋め、Bの?は0で埋めればよい。
k桁目の値(k=0,1,...,nでループ)が決まると、はじめて上記のいずれかが確定するとする。
すると、i < kまではA[i]とB[i]は完全一致でなければならない。
k桁目の値は全列挙。
k+1桁目以降は、0、または、9で埋めればよい。
using namespace std;
#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)
const long long oo = 1LL<<60;
long long diff;
string A, B;
string ra, rb;
void update(const string &a, const string &b) {
long long d = abs(stoll(a) - stoll(b));
if (make_tuple(d, a, b) < make_tuple(diff, ra, rb)) {
diff = d;
ra = a;
rb = b;
}
}
void doit(int k, int p, int q, int r, int s) {
string a = A;
string b = B;
int n = A.size();
REP (i, k) {
if (a[i] == '?' && b[i] == '?')
a[i] = b[i] = '0';
else if (a[i] == '?')
a[i] = b[i];
else if (b[i] == '?')
b[i] = a[i];
}
if (k < n && a[k] == '?') a[k] = '0' + p;
if (k < n && b[k] == '?') b[k] = '0' + q;
FOR (i, k, n) {
if (a[i] == '?') a[i] = r ? '9' : '0';
if (b[i] == '?') b[i] = s ? '9' : '0';
}
update(a, b);
}
void solve() {
cin >> A >> B;
diff = oo;
int n = B.length();
REP (k, n+1) REP (p, 10) REP (q, 10) REP (r, 2) REP (s, 2) {
doit(k, p, q, r, s);
}
cout << ra << " " << rb << endl;
}
int main() {
ios_base::sync_with_stdio(0);
int T;
cin >> T;
REP (i, T) {
cerr << "Case #" << i+1 << ": " << endl;
cout << "Case #" << i+1 << ": ";
solve();
}
return 0;
}
C. Technobabble
第一ワードと第二ワードをノードと考えてグラフを構築する。
第一ワードvと第二ワードwがtopicを構成するとき、枝(v, w)をはる。
すると、このグラフは二部グラフになることがわかる。
ある枝集合を選ぶと、すべてのノードが少なくとも1つの枝によってリンクされる
<=>
使わなかった枝はfakeとなる
と考えることができる。fakeの最大値が欲しいので、上記の条件を満たす最小の枝集合を選べばいい。これは最小辺カバーであり、
|最小辺カバー| = ノード数 - |最大マッチング|
という関係から、最大マッチングを求めれば計算できる。
using namespace std;
#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)
class BipartiteMatching {
int V;
vector<vector<int> >G;
vector<int> match;
vector<bool> used;
bool dfs(int v) {
used[v] = true;
for (int i = 0; i < (int)G[v].size(); i++) {
int u = G[v][i];
int w = match[u];
if (w < 0 || (!used[w] && dfs(w))) {
match[v] = u;
match[u] = v;
return true;
}
}
return false;
}
public:
BipartiteMatching(int v_size) : V(v_size), G(V), match(V), used(V) {}
void add_edge(int u, int v) {
G[u].push_back(v);
G[v].push_back(u);
}
int count() {
int ret = 0;
fill(match.begin(), match.end(), -1);
for (int v = 0; v < V; v++) {
if (match[v] < 0) {
fill(used.begin(), used.end(), false);
if (dfs(v))
++ret;
}
}
return ret;
}
};
int n;
string a[1000], b[1000];
map<string, int> s2id(string s[], int n) {
map<string, int> ret;
REP (i, n) {
if (!ret.count(s[i])) {
int l = ret.size();
ret[s[i]] = l;
}
}
return ret;
}
void solve() {
cin >> n;
REP (i, n) cin >> a[i] >> b[i];
auto aid = s2id(a, n);
auto bid = s2id(b, n);
int an = aid.size();
int bn = bid.size();
BipartiteMatching bm(an + bn);
REP (i, n) bm.add_edge(aid[a[i]], an + bid[b[i]]);
int edge_cover = an + bn - bm.count();
cout << n - edge_cover << endl;
}
int main() {
ios_base::sync_with_stdio(0);
int T;
cin >> T;
REP (i, T) {
cerr << "Case #" << i+1 << ": " << endl;
cout << "Case #" << i+1 << ": ";
solve();
}
return 0;
}
