naoya_t@hatenablog

いわゆるチラシノウラであります

Google Code Jam 2014 - Round 1A

まさかとは思いましたが1Aで通過です

A-small + B-small + C-どこがsmallやねん で62点、265位でした。

Large全部捨てました。
「Largeを取らずに通過」62点勢は9人でした。そのうちLargeを1度も開かずに通った3人に入ってしまいましたw

終わってからLarge問題を考えてみたらそんなに難しい話ではなく、あと1時間あれば満点、ってところでした。

この後 Round 1B, 1C があって、Round 2は日本時間5/31(土)23:00〜です。
開催スケジュール
Round 2で上位1000人に入るとTシャツGETできます。
Tシャツほしいですw

以下、インクルードしてるヘッダとかマクロとかは以下の通りです:

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

Problem A. Charging Chaos

Smallだけ通すつもりで、切り替えパターン全部(10ビットなので1024通り)試しました。
当然通ります。

ll readbin(string& s) {
  ll x = 0;
  int n = s.size();
  rep(i, n) {
    x <<= 1LL;
    x += (s[i] - '0');
  }
  return x;
}

int main(){
  int _T; cin>>_T; // 1-100
  rep(_t,_T){
    int N, L; cin >> N >> L; // num, bits

    int best = L+1;

    vector<long long> initial(N), required(N);
    rep(i, N) {
      string s; cin >> s;
      initial[i] = readbin(s);
    }
    rep(i, N) {
      string s; cin >> s;
      required[i] = readbin(s);
    }

    ll P = 1LL << L;
    for (ll p=0; p<P; ++p) {
      rep(i,N) initial[i] ^= p;
      set<ll> s(all(initial));
      int c=0;
      rep(i,N) {
        if (found(s,required[i])) ++c;
      }
      if (c==N) {
        int bc = __builtin_popcountll(p);
        if (bc < best) best = bc;
      }
      rep(i,N) initial[i] ^= p;
    }

 answer:
    cout << "Case #" << (1+_t) << ": ";
    if (best <= L)
      cout << best << endl;
    else
      cout << "NOT POSSIBLE" << endl;
  }
  return 0;
}
再考

N=150件しかないし、1対1で対応してるわけだから、
N^2=150x150のマトリックスに initial[i] ^ required[j] を求めて。XORね。
このマトリックスには高々N^2通りの数(long longだけど)しか入っていないはずで、答えはこの22500通りのどれかか、不可能かのいずれか。
可能な場合、N^2通りのうちジャストN件が同じ数のはず。(XORだし、同じ行に同じ数は2度来ないはず)
ということは、マトリックス中にちょうどN個だけ現れる数のみを候補として、popcountが一番小さいやつを使えばいい。

PracticeデータでAC。

ll readbin(string& s) {
  ll x = 0;
  int n = s.size();
  rep(i, n) {
    x <<= 1LL;
    x += (s[i] - '0');
  }
  return x;
}

int main(){
  int _T; cin>>_T; // 1-100
  rep(_t,_T){
    int N, L; cin >> N >> L; // num, bits

    vector<long long> initial(N), required(N);
    rep(i, N) {
      string s; cin >> s;
      initial[i] = readbin(s);
    }
    rep(i, N) {
      string s; cin >> s;
      required[i] = readbin(s);
    }

    map<ll,int> cnt;
    rep(i,N) rep(j,N){
      ll m = initial[i] ^ required[j];
      cnt[m]++;
    }

    set<ll> cand;
    tr(it,cnt){
      if (it->second == N) cand.insert(it->first);
    }

    int best = L+1;
    tr(it, cand){
      int bc = __builtin_popcountll(*it);
      if (bc < best) best = bc;
    }

 answer:
    cout << "Case #" << (1+_t) << ": ";
    if (best <= L)
      cout << best << endl;
    else
      cout << "NOT POSSIBLE" << endl;
  }
  return 0;
}

Problem B. Full Binary Tree

これもSmallだけ通すつもりで、
15ノードそれぞれをrootにして、ノード消去パターン全部(32768通りx15)試しました。
当然通ります。

vector<vector<bool> > m;
vector<bool> vs(15), pt(15);
int N;

bool sub(int rt){
  int c=0;
  vs[rt] = true;
  rep(n,N) {
    if(n==rt)continue;
    if(!pt[n])continue;
    if (!m[rt][n]) continue;
    if(vs[n])continue;

    ++c; if(c>2) return false;
    if(!sub(n)) return false;
  }
  return (c==0 || c==2);
}

bool ok(int rt){
  vs.assign(N, false);

  if (!sub(rt)) {
    return false;
  }

  rep(i,N) {
    if (!pt[i]) continue;
    if (!vs[i]) {
      return false;
    }
  }
  return true;
}

int main(){
  int _T; cin>>_T; // 1-100
  rep(_t,_T){
    cin >> N;
    int best = 99;

    m.assign(15, vector<bool>(15, false));

    rep(i, N-1) {
      int xi, yi; cin >> xi >> yi;
      --xi; --yi;
      m[xi][yi] = m[yi][xi] = true;
    }

    int P = 1 << N;
    for (int p=0; p<P; ++p) {
      rep(i,N) { pt[i] = true; vs[i] = false; }
      int pc=0;
      for (int i=0,m=1; m<=P; ++i,m<<=1) {
        if (p&m) { pt[i] = false; ++pc; }
      }
      rep(rt,N){
        if (ok(rt)) {
          if (pc < best) best = pc;
        }
      }
    }

 answer:
    cout << "Case #" << (1+_t) << ": " << best << endl;
  }
  return 0;
}
再考

どのノードをrootにするかは全ノードについて試すとして。
それぞれのノードが、子供を0ノードあるいは2ノード持つことができるとした場合の最大ノード数が分かれば、全ノード数からそれを引いたのが削除ノード数だし、その最小値を答えればいい。
で。これは再帰的に簡単に求まるよね。

PracticeデータでAC。

int N;
vector<vector<bool> > m;
vector<bool> visited;

int sub(int root) {
  visited[root] = true;
  set<int> children;
  rep(i,N){
    //if (i == root) continue;
    if (visited[i]) continue;
    if (m[root][i])
      children.insert(i);
  }
  int n = sz(children);
  if (n <= 1) return 1; // drop his child

  vector<int> score;

  tr(it,children) {
    int ch = *it;
    int sc = sub(ch);
    score.pb(sc);
  }
  sort(all(score), greater<int>());
  return 1 + score[0] + score[1];
}

int main(){
  int _T; cin>>_T; // 1-100
  rep(_t,_T){
    cout << "Case #" << (1+_t) << ": ";

    cin >> N;

    m.assign(N, vector<bool>(N, false));

    rep(i, N-1) {
      int xi, yi; cin >> xi >> yi;
      --xi; --yi;
      m[xi][yi] = m[yi][xi] = true;
    }

    int best = 0;

    rep(root, N) {
      visited.assign(N, false);
      int size = sub(root);
      if (size > best) best = size;
    }

    cout << (N - best) << endl;
  }

  return 0;
}

Problem C. Proper Shuffle

まだ随分時間あるけどLargeに行くか?
とりあえず問題Cを読んでからにしよう…

えっと。
なんで45点なのこれ…
ああ
N=1000て
組み合わせ1000! (=4.02e2567) 通りあるのか

でもテストケース120個のうち109個以上合ってればACなのね…

N=4の場合の全パターンを最初ノートに書いてて
めんどくさくなってプログラムで生成して
どゆこと?編集距離みたいなやつ?

いや、すべての数字について、どの位置にあるか確率出せるんじゃね?
GOODモデルはuniformだけど、BADモデルは偏ってるよね。
テストケースのデータから、モデルの尤もらしさを求めればいいのね。

ざっくりi.i.d仮定して、個々の数字がその位置にある確率、の積を求めて
それがuniformを仮定した場合とかけ離れてたらBAD、でよくね?

こういうのってlogsumexpみたいなやつだよね
小さい数字を掛けあわせていくとすぐにアンダーフローしちゃうから。

実際は、log(uniformの場合を1とした場合の比率) を求めておいてそれを足しあわせてる。
GOODの場合は(logでの)合計が log(1) = 0 周辺に分布するはず。BADならもっと大きくなるはず。
とりあえず適当に log(1.1) をthresholdにしたら通ってしまった。

1投目、全然処理が帰ってこないのでテストケース見たら全部N=1000とかじゃん
だったらN=1000の場合の確率をキャッシュしてしまおう

で2投目あっさりACでびびった

int K;

vector<double> prepare(int w){
  vector<double> at(K, 0);
  at[w] = 1.0;

  double g = (double)(K-1) / K;
  rep(pivot, K) {
    vector<double> nx(K, 0);
    double d = at[pivot]/K;
    rep(i,K) {
      if(i==pivot)continue;
      nx[i] = d + at[i] * g;
    }

    double u = 0;
    rep(i,K) u += at[i];
    nx[pivot] = u / K;

    rep(i,K) at[i] = nx[i];
  }

  vector<double> lat(K, 0);
  rep(i,K) lat[i] = log(at[i] * K);
  return lat;
}

int main(){
  int _T; cin>>_T; // 1-100

  vector<vector<double> > lats(1000, vector<double>(1000));

  K = 1000;
  rep(i, 1000) {
    vector<double> lat = prepare(i);
    lats[i].assign(all(lat));
  }

  rep(_t,_T){
    int N; cin >> N;

    K = N;

    vector<int> a(N), ra(N);
    rep(i,N) {
      cin >> a[i];
      ra[a[i]] = i;
    }

    double lsum = 0;
    if (K == 1000) {
      rep(i, K) {
        lsum += lats[i][ra[i]];
      }
    } else {
      rep(i, K) {
        vector<double> lat = prepare(i);
        lsum += lat[ra[i]];
      }
    }
    cout << lsum << endl;

    cout << "Case #" << (1+_t) << ": ";
    if (lsum > log(1.1))
      cout << "BAD" << endl;
    else
      cout << "GOOD" << endl;
  }
}