Google Code Jam 2014 Round1B - pes

先のARCで運を使い果たしたので震えながら参加。

A : The Repeater

アルファベットの登場順を崩すような操作はできない
なので与えられた文字列で、アルファベットの登場順が違うのがあったら勝てない
勝てるんだったら文字ごとに適当に個数を揃えてやれば良い

こういうのを美しく書けるようになりたい人生でした

#include <iostream>
#include <vector>
#include <string>
#include <cstdio>
#include <algorithm>

using namespace std;

string conv(const string& s, vector<int>& v){
    int cnt = 1;
    string res;
    res += s[0];
    char c = s[0];
    for(int i=1;i<s.size();i++){
        if(c == s[i]) cnt++;
        else {
            v.push_back(cnt);
            cnt = 1;
            c = s[i];
            res += c;
        }
    }
    v.push_back(cnt);
    return res;
}

int main(){
    int T; cin >> T;
    for(int test=1;test<=T;test++){
        int N; cin >> N;
        vector< vector<int> > v(N);
        bool won = true;
        string s, t;
        cin >> s;
        t = conv(s, v[0]);
        for(int i=1;i<N;i++){
            cin >> s;
            string u = conv(s, v[i]);
            if(u != t) won = false;
        }
        if(!won){
            printf("Case #%d: Fegla Won\n", test);
            continue;
        }
        int res = 0;
        for(int i=0;i<v[0].size();i++){
            int add = 1000000;
            for(int j=1;j<=100;j++){
                int sum = 0;
                for(int k=0;k<v.size();k++){
                    sum += abs(v[k][i]-j);
                }
                add = min(add, sum);
            }
            res += add;
        }
        printf("Case #%d: %d\n", test, res);
    }
}

B : New Lottery Game

あっ、このlargeやばいやつだ。と思ってまずはsmallを通した。

largeは挑戦者が多いのに全く分からず、悲しい気持ちになってた。
先にC提出した後も分からなすぎて、暗殺教室9巻を読んでた程の体たらく
終了20分前くらいに、桁DPというワードが脳内に浮上したのでギリギリ通せた。
5重ループを書きながら、俺は何をしてるんだ…という気持ちになってた。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

int solveSmall(int A, int B, int K){
    int res = 0;
    for(int i=0;i<A;i++){
        for(int j=0;j<B;j++){
            if((i&j) < K) res++;
        }
    }
    return res;
}

long long solveLarge(int A, int B, int K){
    long long dp[2][2][2][2];
    memset(dp, 0, sizeof(dp));
    dp[0][1][1][1] = 1;
    for(int i=30;i>=0;i--){
        int cur = i%2, next = 1-cur;
        memset(dp[next], 0, sizeof(dp[next]));
        for(int smallA=0;smallA<2;smallA++){
            for(int smallB=0;smallB<2;smallB++){
                for(int smallK=0;smallK<2;smallK++){
                    if(dp[cur][smallA][smallB][smallK] == 0) continue;
                    for(int a=0;a<2;a++){
                        if(smallA && !(A&(1<<i)) && a == 1) continue;
                        int nA = smallA ? ((A>>i)&1) == a : 0;
                        for(int b=0;b<2;b++){
                            if(smallB && !(B&(1<<i)) && b == 1) continue;
                            int nB = smallB ? ((B>>i)&1) == b : 0;
                            if(smallK && !(K&(1<<i)) && a == 1 && b == 1) continue;
                            int nK = smallK ? ((K>>i)&1) == (a&b) : 0;
                            dp[next][nA][nB][nK] += dp[cur][smallA][smallB][smallK];
                        }
                    }
                }
            }
        }
    }
    return dp[1][0][0][0];
}

int main(){
    int T; cin >> T;
    for(int test=1;test<=T;test++){
        int A, B, K; cin >> A >> B >> K;
        printf("Case #%d: %lld\n", test, solveLarge(A, B, K));
    }
}

C : The Bored Traveling Salesman

悲しい気持ちでBから逃げてきたので、精神を安定させるためにまずsmallを通した。

largeは…ある順で辿った時に、そこから残りを全部辿れるか判定できれば行けそう。
- validな奴を貪欲に辿っていくというパターン
各土地に往路チケットで行けるのは高々1回という仕様が地味に面倒
途中まで辿った段階で復路チケットを持ってる土地のリスト(A)と、往復使いきった土地のリスト(B)を持っておき、Aに属する土地から、Bに属する土地を通らずに全ての土地に行けるかを判定した。
smallの解答と一致してそうに見えたので提出。通った。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <stack>
#include <queue>

using namespace std;

typedef vector< vector<int> > Graph;

bool isValid(const Graph& g, const vector<int>& order){
    stack<int> st;
    st.push(order[0]);
    for(int i=1;i<order.size();i++){
        while(true){
            if(st.empty()) return false;
            int pos = st.top();
            bool ok = false;
            for(int j=0;j<g[pos].size();j++){
                if(g[pos][j] == order[i]) ok = true;
            }
            if(ok){ st.push(order[i]); break; }
            else st.pop();
        }
    }

    int n = g.size();
    vector<int> visit(n, 0);
    for(int i=0;i<order.size();i++) visit[order[i]] = 1;
    queue<int> qu;
    while(!st.empty()){ qu.push(st.top()); st.pop(); }
    while(!qu.empty()){
        int p = qu.front(); qu.pop();
        for(int i=0;i<g[p].size();i++){
            if(visit[g[p][i]]) continue;
            visit[g[p][i]] = 1;
            qu.push(g[p][i]);
        }
    }
    for(int i=0;i<n;i++)
        if(visit[i]==0) return false;
    return true;
}

int main(){
    int T; cin >> T;
    for(int test=1;test<=T;test++){
        int N, M; cin >> N >> M;
        Graph g(N);
        vector<string> vs(N);
        vector<int> state(N, 0);
        for(int i=0;i<N;i++) cin >> vs[i];
        for(int i=0;i<M;i++){
            int a, b; cin >> a >> b;
            g[a-1].push_back(b-1);
            g[b-1].push_back(a-1);
        }
        string res;
        int idx = 0;
        for(int i=0;i<N;i++)
            if(vs[idx] > vs[i]) idx = i;
        res = vs[idx];
        vector<int> order; order.push_back(idx);
        vector<int> visit(N, 0);
        visit[idx] = 2;
        for(int i=0;i<g[idx].size();i++) visit[g[idx][i]] = 1;
        for(int i=1;i<N;i++){
            idx = -1;
            order.push_back(0);
            for(int j=0;j<N;j++){
                if(visit[j]!=1) continue;
                order.back() = j;
                if(isValid(g, order) && (idx==-1 || vs[idx] > vs[j])) idx = j;
            }
            order.back() = idx;
            res += vs[idx];
            visit[idx] = 2;
            for(int i=0;i<g[idx].size();i++) visit[g[idx][i]] = max(1, visit[g[idx][i]]);
        }
        printf("Case #%d: %s\n", test, res.c_str());
    }
}

Rank 105 : /oo/oo/oo/ Score 100, Penalty 2:17:30

small全部通れば通過くらいかと思ってましたが、通過ラインはそれより上でした。
こわい(´・ω・｀)