Google Code Jam 2014 Round1A

　本番は風邪ひいてて出れなかったけど、次の1Bに向けて練習で解いてみた。

Aは20分くらい、Bは25分くらいで解けた。Cは難しそうだから読んでない。Round 1は突破できそうかなという手応え。

簡単な解説とソースコードをはっておく。

A. Charging Chaos

問題: https://code.google.com/codejam/contest/2984486/dashboard#s=p0

解法: すべてのデバイスが充電できるとする。このときデバイス[0]はコンセント[0], コンセント[1], ..., コンセント[N]のいずれかとマッチングするはずである。デバイス[0]とコンセント[0]がマッチしたとする。すると、どのスイッチを押し方は一意に決定することが出来る。同様にコンセント[i]がデバイス[0]とマッチしたと考えるとスイッチの押し方は一意にきまる。
よってデバイス[0]がどのコンセントにマッチしたかをループし、スイッチの押し方を求め、完全マッチするかどうか調べればよい。完全マッチする場合は押す必要のあるスイッチの個数を更新する。L=40なので64bit整数の各ビットでスイッチを表現すればよい。

ソースコード:

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 int INF = 1e6;

long long readLong() {
    string s;
    cin >> s;
    long long ret = 0;

    REP (i, s.length()) ret = 2 * ret + s[i] - '0';
    return ret;
}

void solve() {
    int n, l;
    cin >> n >> l;

    vector<long long> a(n), b(n), c(n);
    REP (i, n) a[i] = readLong();
    REP (i, n) b[i] = readLong();
    sort(a.begin(), a.end());

    int ret = INF;
    REP (i, n) {
        long long x = a[0] ^ b[i];
        REP (j, n) c[j] = b[j] ^ x;
        sort(c.begin(), c.end());
        if (a == c)
            ret = min(ret, __builtin_popcountll(x));
    }

    if (ret == INF)
        cout << "NOT POSSIBLE" << endl;
    else
        cout << ret << 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. Full Binary Tree

問題: https://code.google.com/codejam/contest/2984486/dashboard#s=p1

解法: ルートを固定すると、1回のDFSで自分の子の数、それぞれの子を採用したときにえられる完全二分木のサイズを調べる事が出来る。子が1つ以下の場合は、自分以下の部分木で構築出来る完全二分木のサイズは1となる（自身のノードのみからなる木）。もし子が2つ以上の場合は、もっとも大きなサイズの部分木を作れるノードを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++)

const int INF = 1e6;
int N;

vector<int> edges[1000];

int dfs(int v, int par = -1) {
    int lch = 0;
    int rch = 0;

    REP (i, edges[v].size()) {
        int w = edges[v][i];
        if (w == par) 
            continue;

        int cnt = dfs(w, v);
        if (cnt > lch) swap(lch, cnt);
        if (cnt > rch) swap(rch, cnt);
    }

    if (!lch || !rch)   // this node only
        return 1;

    return 1 + lch + rch;   // has two children
}

void init() {
    REP (i, 1000) edges[i].clear();
}

void solve() {
    cin >> N;
    REP(i, N-1) {
        int v, w;
        cin >> v >> w;
        --v, --w;
        edges[v].push_back(w);
        edges[w].push_back(v);
    }

    int ret = N-1;
    REP (k, N) ret = min(ret, N-dfs(k));
    cout << ret << 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 << ": ";
        init();
        solve();
    }

    return 0;
}