Google Code Jam 2016 Round 1B

　https://code.google.com/codejam/contest/11254486/dashboard
　一完3500位台で無事に死にました……。Bを貪欲でいけると思い込んで落とすのは本当にダメ（探索を投げたほうがマシだった）。1Cは日曜でしたっけ。精進せねば……。
Problem A. Getting the Digits
　ZERO~NINEがごちゃまぜに書いてある紙から数字を復元する問題。適当に貪欲するとアルファベットが余った場合に死ぬのでGはEIGHTにしか使わないからGがある分だけEIGHTを引く、というのを繰り返すと復元できます。

int main(){
    ifstream ifs("A-large.in");
    ofstream ofs("op_a.txt");
    int test; ifs >> test;
    string zero = "ZERO", one = "ONE", two = "TWO", three = "THREE", four = "FOUR", five = "FIVE", six = "SIX", seven = "SEVEN", eight = "EIGHT", nine = "NINE";
    string pre = "GVSXFEZRONTWHUI";
    rep(casenum, test){
        string s; ifs >> s;
        map<char, int> nums;
        for(char a : pre) nums[a] = 0;
        for(char a : s) nums[a]++;
        vector<int> ans;
        while(nums['G']){
            for(char a : eight) nums[a]--;
            ans.push_back(8);
        }
        while(nums['X']){
            for(char a : six) nums[a]--;
            ans.push_back(6);
        }
        while(nums['S']){
            for(char a : seven) nums[a]--;
            ans.push_back(7);
        }
        while(nums['V']){
            for(char a : five) nums[a]--;
            ans.push_back(5);
        }
        while(nums['F']){
            for(char a : four) nums[a]--;
            ans.push_back(4);
        }
        while(nums['Z']){
            for(char a : zero) nums[a]--;
            ans.push_back(0);
        }
        while(nums['R']){
            for(char a : three) nums[a]--;
            ans.push_back(3);
        }
        while(nums['W']){
            for(char a : two) nums[a]--;
            ans.push_back(2);
        }
        while(nums['O']){
            for(char a : one) nums[a]--;
            ans.push_back(1);
        }
        while(nums['I']){
            for(char a : nine) nums[a]--;
            ans.push_back(9);
        }
        sort(ans.begin(), ans.end());
        ofs << "Case #" << casenum + 1 << ": " ;
        for(int k : ans) ofs << k;
        ofs << endl;
    }
    return 0;
}

汚いコードですね……。

Problem B. Close Match
　スコアボードの数字が ?7?9 6??2 のように何桁か隠されて与えられる。この二つの差が最小になるように、そのようなケースが複数ある場合は数字が小さくなるように？を埋めろ、という問題。
　本番では貪欲法で上から埋める解法を考えていたのですが、??0 099 → 100 99 のようなケースに対処するのが難しいことに気づけず死にました。なのでDFSで、A > B or A < B のときは片方を最小化or最大化して、A = Bのときはありえるパターン（最大3つくらいしかない）を全部試す、というのをして候補をいくつか割り出します。あとは小さいのを選べばOK。

const char q = '?';
string a, b;
int n;
typedef pair<string, string> ps;
vector<ps> ans;
void solve(int depth, string resa, string resb){
    if(depth == n){
        ans.push_back(ps(resa, resb));
        return;
    }
    char ca = a[depth], cb = b[depth];
    if(resa > resb){
        resa += (ca == q) ? '0' : ca;
        resb += (cb == q) ? '9' : cb;
        solve(depth + 1, resa, resb);
    }else if(resa < resb){
        resa += (ca == q) ? '9' : ca;
        resb += (cb == q) ? '0' : cb;
        solve(depth + 1, resa, resb);
    }else{
        if(ca == q && cb == q){
            string pa = resa + '0', pb = resb + '0', qa = resa + '1', qb = resa + '1';
            solve(depth + 1, pa, pb);
            solve(depth + 1, qa, pb);
            solve(depth + 1, pa, qb);
        }else if(ca == q){
            resb += cb;
            if(cb != '9'){
                char temp = cb + 1;
                string pa = resa + temp;
                solve(depth + 1, pa, resb);
            }
            if(cb != '0'){
                char temp = cb - 1;
                string qa = resa + temp;
                solve(depth + 1, qa, resb);
            }
            resa += cb;
            solve(depth + 1, resa, resb);
        }else if(cb == q){
            resa += ca;
            if(ca != '9'){
                char temp = ca + 1;
                string pb = resb + temp;
                solve(depth + 1, resa, pb);
            }
            if(ca != '0'){
                char temp = ca - 1;
                string qb = resb + temp;
                solve(depth + 1, resa, qb);
            }
            resb += ca;
            solve(depth + 1, resa, resb);
        }else{
            resa += ca;
            resb += cb;
            solve(depth + 1, resa, resb);
        }
    }
}
ll st_to_int(string s){
    int n = s.size();
    ll res = 0;
    ll keta = 1;
    for(int i = n - 1; i >= 0; --i){
        res += (s[i] - '0') * keta;
        keta *= 10;
    }
    return res;
}
ll abst(ll num){
    if(num > 0) return num;
    num *= -1;
    return num;
}
int main(){
    ifstream ifs("B-large-practice.in");
    ofstream ofs("op_b.txt");
    int test; ifs >> test;
    rep(casenum, test){
        ans.clear();
        ifs >> a >> b;
        n = a.size();
        solve(0, "", "");
        ll ms = LL_INF;
        ps res;
        for(auto k : ans){
            ll sa = abst(st_to_int(k.first) - st_to_int(k.second));
            if(sa < ms || (ms == sa && k < res)){
                res = k;
                ms = sa;
            }
        }
        ofs << "Case #" << casenum + 1 << ": ";;
        ofs << res.first << ' ' << res.second << endl;
    }
    return 0;
}

　コード長いなあ……。普通に場合分けがキツイ問題でした。

Problem C. Technobabble
HYDROCARBON COMBUSTION
QUAIL BEHAVIOR
QUAIL COMBUSTION
のような感じで文字列が与えられるのですが、これは学会の発表内容らしい。アホな学生が既出のFirst wordと　Second wordを組み合わせて自分のトピックにしているらしいのだが、そのような学生は最大で何人いるだろうか、という問題。
　本番では適当にsetかなんかを使ったのですがこれで最大化するのは無理ですね……。
　まず左の単語を左のノード、右の(ry　とする二部グラフを考えます。
　パクった学生が最大→オリジナルなトピックが最小　ということで、すべての頂点が E に含まれるいずれかの辺に接続しているような最小の枝集合Eを考えます。最小枝カバーというやつですね。これは（証明とかは理解していないのですが）最大マッチングの個数と、最大マッチングで使った辺につながっていない頂点の数を足すと求められます。これをトピック数から引けば答えになります。

template <int MAX_V>
struct bipartite{
    int V;
    vector<int> G[MAX_V];
    int match[MAX_V];
    bool used[MAX_V];
    
    void init(int v){
        V = v;
        memset(used, 0, sizeof(used));
        memset(match, -1, sizeof(match));
        rep(i, V) G[i].clear();
    }
    void add(int u, int v){
        G[u].push_back(v);
        G[v].push_back(u);
    }
    bool dfs(int v){
        used[v] = true;
        rep(i, G[v].size()){
            int u = G[v][i], w = match[u];
            if(w < 0 || !used[w] && dfs(w)){
                match[v] = u;
                match[u] = v;
                return true;
            }
        }
        return false;
    }
    int matching(){
        int res = 0;
        rep(v, V){
            if(match[v] < 0){
                memset(used, 0, sizeof(used));
                if(dfs(v)) res++;
            }
        }
        return res;
    }
    int unused_vertices(){
        int res = 0;
        rep(v, V) if(match[v] == -1) res++;
        return res;
    }
};
typedef pair<string, string> ps;
bipartite<2020> bp;
int main(){
    ifstream ifs("C-large-practice.in");
    ofstream ofs("op_c.txt");
    int test; ifs >> test;
    rep(casenum, test){
        int n; ifs >> n;
        map<string, int> table;
        vector<ps> words;
        rep(i, n){
            string a, b, c; ifs >> a >> c;
            b = "z"; b += c;
            words.push_back(ps(a, b));
            table[a] = table[b] = 0;
        }
        int vn = 0;//頂点の番号
        for(auto& x : table) x.second = vn++;
        bp.init(vn);
        for(ps x : words) bp.add(table[x.first], table[x.second]);
        int ans = n - (bp.matching() + bp.unused_vertices());
        ofs << "Case #" << casenum + 1 << ": " << ans << endl;
    }
    return 0;
}

　今回は本当にダメでしたねえ……。
　R1Cは無理だと思ったら即Small用の愚直解を書くくらいの感じでいきたいです。