Hatena::Grouptopcoder

minus9dの記録

2014-04-29

Google Code Jam 2014 Round1A

| 18:18 | Google Code Jam 2014 Round1A - minus9dの記録 を含むブックマーク はてなブックマーク - Google Code Jam 2014 Round1A - minus9dの記録

Round1AはA-smallしか解けず2471位で敗退。

本番ではSmallを優先して解く戦略を取った。とりあえずA-smallをブルートフォースで解き、B-smallに集中するも、手も足も出ずそのまま時間切れ。AとBを両方解いても解答時間によっては敗退してしまうような難易度では勝ち目はまったくなかったと言える。

LayCurseさんのとても教育的な解説を読んで復習した。以下のコードは、Aを除いて、LayCurseさんのコードをほぼ丸々下敷きにしている。

A. Charging Chaos

コンセントと電化製品とのマッチングについて、ビットで制限を加えつつ総当り的なことをしないといけないと勘違いをしていた。しかし実際は、ある一つの組み合わせさえ決めればよいのであった。これは本番中に気づかなければいけない問題だった。

// 参考:http://rsujskf.s602.xrea.com/?googlecodejam_2014_1a_a

#include <cstdio>
#include <iostream>
#include <sstream>
#include <string>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <numeric>

using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define FOREACH(i, n) for (__typeof((n).begin()) i = (n).begin(); i != (n).end(); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair

const int INF = 10000;

void flip(char &ch){
    if (ch == '0') ch = '1';
    else ch = '0';
}

int main(void)
{
    int TEST_NUM;
    cin >> TEST_NUM;

    for(int test = 0; test < TEST_NUM; ++test){
        int N, L;
        cin >> N >> L;
        vector<string> init(N);
        vector<string> need(N);
        REP(i, N){
            cin >> init[i];
        }
        REP(i, N){
            cin >> need[i];
        }

        sort(ALL(need));

        // 最初のデバイスを、i番目のコンセントにつなぐとしたときに、何度スイッチを押す必要があるかを調べる
        int ret = INF;
        REP(i, N){
            vector<string> init_copy = init;
            int flip_cnt = 0;
            REP(l, L){
                if (init[0][l] != need[i][l]) {
                    REP(j, N){
                        flip(init_copy[j][l]);
                    }
                    ++flip_cnt;
                }
            }
            sort(ALL(init_copy));
            if (init_copy == need) {
                ret = min(ret, flip_cnt);
            }
        }

        cout << "Case #" << (test+1) << ": ";
        if (ret == INF) {
            cout << "NOT POSSIBLE";
        }
        else{
            cout << ret;
        }
        cout << endl;
    }

    return 0;
}

B. Full Binary Tree

ループしていることも考慮すると大変だぞ、と思いあれこれ考えるが、よく問題文を読むと、エッジの数はノードの数-1なのでループはありえないのであった。グラフに関する問題だというだけで必要以上に身構えてしまう悪い傾向がある。

LayCurseさんの解説コードではdpの要素は使っていなかったようなので、以下のコードではdpテーブルは省いてある。再帰関数にて親側のノードを誤って数えないようにする工夫が勉強になった。


// 参考:http://rsujskf.s602.xrea.com/?googlecodejam_2014_1a_b

#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<string>
#include<utility>
#include<iostream>
#include<cmath>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define INF 1000000000

int N;
int edge[1200][1200]; ///< エッジのリスト
int es[1200]; ///< 頂点が持つエッジの数

// now番目のノード以下、残せるノードの最大数を求める
// befは、i番目のノードの親。間違って親側に逆流することを防ぐ
int solve(int now, int bef){
    int i, j, k;

    // now番目のノードの子ノードのそれぞれが、何個のノードを残せるか
    vector<int> num;

    // now番目のノードが持つエッジでループ
    rep(k,es[now]){
        i = edge[now][k];
        if(i==bef) continue;
        num.push_back( solve(i, now) );
    }

    // now番目のノードの子の数が0個または1個の場合は、まったく子は残せないので1
    int ret = 1;

    // now番目のノードの子の数が2個以上の場合は、残せる子の数が多いもの上位2個を選ぶ
    if(num.size() >= 2){
        sort(num.rbegin(), num.rend());
        ret += num[0] + num[1];
    }

    return ret;
}

int main(){
    int i, j, k;
    int res, tmp;
    int T, cnt = 0;

    scanf("%d",&T);
    while(T--){
        fprintf(stderr,"rest %d\n",T);
        printf("Case #%d: ", ++cnt);

        scanf("%d",&N);
        rep(i,N) es[i] = 0;
        rep(i,N-1){
            scanf("%d%d",&j,&k);
            // 0 originに直す
            j--; k--;
            edge[j][es[j]++] = k;
            edge[k][es[k]++] = j;
        }

        // debug print
        // printf("\n");
        // rep(i, N){
        //     printf("es[%d] = %d\n", i, es[i]);
        //     rep(j, es[i]){
        //         printf("  edge ->%d\n", edge[i][j]);
        //     }
        // }

        res = INF;
        // 何番目を頂点にするかのループ
        // 一番良い結果を選ぶ
        rep(i,N){
            tmp = solve(i, -1);
            res = min(res, N-tmp);
        }

        printf("%d\n", res);
    }

    return 0;
}

C. Proper Shuffle

BAD法で生成したランダム配列はGOOD法で生成したランダム配列に比べて悪い癖があるはずで、それをシミュレーションによって明らかにすればよかった。

// 参考:http://rsujskf.s602.xrea.com/?googlecodejam_2014_1a_c

#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<string>
#include<utility>
#include<iostream>
#include<cmath>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

// Gper[i][j]: BAD法により、a[i] = jとなる確率のN倍
double Gper[1200][1200];

// サイズnのアレーをBAD法で生成するのをt回シミュレート 確率をGper[i][j]に記録
void test3(int n, int t){
    int i, j, k, loop;
    vector<int> p(n);

    // per[i][j]: BAD法のシミュレート後、アレーのi番目の数字がjである回数をカウント
    static int per[1200][1200] = {};

    // BAD法をt回シミュレート
    rep(loop,t){
        rep(i,n) p[i] = i;
        rep(i,n){
            k = rand() % n; // bad
            swap(p[i], p[k]);
        }

        rep(i,n) per[i][p[i]]++;
    }

    rep(i,n) rep(j,n) Gper[i][j] = (double)per[i][j] / t * n;
  // rep(i,n){ rep(j,n) printf("%f ",(double)per[i][j]/t*n); puts(""); }
}

int main(){
    int i,j,k;
    int T, cnt = 0;
    int N, p[2000], sum;
    double res;
 
    test3(1000, 1000000);
  
    scanf("%d",&T);
    while(T--){
        fprintf(stderr,"rest %d\n",T);
        printf("Case #%d: ", ++cnt);

        scanf("%d",&N);
        rep(i,N) scanf("%d",p+i);
        res = 1;
        rep(i,N) res *= Gper[i][p[i]];
        if(res <= 1) puts("GOOD"); else puts("BAD");
    }

    return 0;
}

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/minus9d/20140429
リンク元