naoya_t@hatenablog

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

Google Code Jam 2014 - Round 1B

Round 1Aで通過してしまって1Bは参加資格がないので、Practice落ちした問題を見てみました。

規定の2時間半でどこまで行けるか見たいので一応時間を計りながらね。
場所を転々としながら、A(small+large), B(small), C(small) までで通算1時間41分。これで46点確保。
A-largeで1回WAしてるので、1時間45分相当、ということでこれは732位ぐらい?連続でやって同じように落ち着いて考えられるかは分からないから単純比較は出来ないけれど、一応R2進出ラインは越えられて安堵。

A. The Repeater

文字列を { (文字1, 個数1), (文字2, 個数2), ..., (文字L, 個数L) } みたいに分解して、すべての文字列について

  • Lがすべて等しく
  • 文字_i の部分がすべて同じ

である場合のみOmarはFeglaに勝てる。

文字列は高々100個、文字列の長さは高々100だし、先頭から1文字ずつ、何文字に合わせるか総当りで調べたらいいじゃん、ということで。

最初個数_i の平均値±1文字しか見てなくて、smallは通ったけどlargeでWA。
合わせる文字数を1〜100文字すべて調べたら通った。

small: 0:30
large: 0:39 (+1 wrong answer)

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

using namespace std;
#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);var++)

typedef pair<char,int> CI;

vector<CI> conv(string& s){
  vector<CI> st;
  int len=s.size(), cnt=0;
  char lastc = 0;
  rep(i,len) {
    if (s[i] == lastc) {
      ++cnt;
    } else {
      if (cnt) st.pb(CI(lastc, cnt));
      lastc = s[i];
      cnt = 1;
    }
  }
  st.pb(CI(lastc, cnt));
  return st;
}

int diff(int avg, vector<int>& e){
  int N = sz(e), d = 0;
  rep(n,N) d += abs(e[n] - avg);
  return d;
}

int sub(vector<int>& e){
  int num_move = 99999;
  for (int i=1; i<=100; ++i) {
    num_move = min(num_move, diff(i, e));
  }
  return num_move;
}

int solve(vector<vector<CI> > st) {
  int N = sz(st), lc = sz(st[0]);
  int num_move = 0;
  rep(i,lc) {
    vector<int> e(N);
    rep(n,N) {
      e[n] = st[n][i].second;
    }
    num_move += sub(e);
  }
  return num_move;
}

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

    vector<vector<CI> > st;
    rep(i,N) {
      string s; cin >> s;
      st.pb(conv(s));
    }

    bool solvable = false;
    int num_move = 999, lc=sz(st[0]);

    vector<char> cs(lc);
    rep(i,lc) cs[i] = st[0][i].first;

    for(int n=1; n<N; ++n){
      if (sz(st[n]) != sz(st[0])) goto answer;
      rep(i,lc) if (st[n][i].first != cs[i]) goto answer;
    }

    solvable = true;
    num_move = solve(st);

 answer:
    cout << "Case #" << (1+_t) << ": ";
    if (solvable) {
      cout << num_move << endl;
    } else {
      cout << "Fegla Won" << endl;
    }
  }
}

B. New Lottery Game

smallは、1000x1000だし全部調べたらいいよね
largeどうするの?bitごとに計算できる?→ノートでごにょごにょ考えてて時間切れ

small: 0:50

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;
#define sz(a)  int((a).size())
#define rep(var,n)  for(int var=0;var<(n);var++)

typedef pair<int,int> II;

int solve(int A, int B, int K) {
  set<II> s;
  rep(a,A) rep(b,B) {
    int ab = a & b;
    if (ab < K) {
      s.insert(II(a,b));
    }
  }
  return sz(s);
}

int main(){
  int _T; cin>>_T; // 1-100
  rep(_t,_T){
    int a, b, k; cin >> a >> b >> k; // 1-1000 or 1-1e9
    cout << "Case #" << (1+_t) << ": " << solve(a,b,k) << endl;
  }
}

C. The Bored Traveling Salesman

smallは8都市しかないし、next_permutation()で順列組み合わせ全部調べても間に合うよね…
largeはそれじゃ無理だけど。

small: 1:41

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <map>

using namespace std;
#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++)

typedef pair<int,int> II;

int N, M;
vector<vector<bool> > rs;

bool possible(vector<int>& e) {
  stack<int> path; path.push(e[0]);

  for(int j=1; j<N; ++j) {
    int to = e[j];

    bool reachable = false;
    while (!path.empty()) {
      int cur = path.top();
      if (rs[cur][to]) {
        reachable = true;
        path.push(to);
        break;
      } else {
        path.pop();
      }
    }
    if (!reachable) return false;
  }

  return true;
}

int main(){
  int _T; cin>>_T; // 1-100
  rep(_t,_T){
    cin >> N >> M; // N<=8 or 50
    vector<pair<string,int> > zips_(N);
    rep(n,N) {
      string s; cin >> s;
      zips_[n] = make_pair(s,n);
    }
    sort(all(zips_));

    vector<string> zips(N);
    map<int,int> trans;
    rep(n,N){
      zips[n] = zips_[n].first;
      trans[zips_[n].second] = n;
    }

    vector<II> flights(M);
    rs.assign(N, vector<bool>(N, false));
    rep(m,M) {
      int i, j; cin >> i >> j;
      --i; --j;
      int ti = trans[i], tj = trans[j];
      flights[m] = II(ti, tj);
      rs[ti][tj] = rs[tj][ti] = true;
    }

    vector<int> e(N); rep(i,N) e[i]=i;
    do {
      if (possible(e)) break;
    } while (next_permutation(all(e)));

 answer:
    cout << "Case #" << (1+_t) << ": ";
    tr(it,e) cout << zips[*it];
    cout << endl;
  }
}