読者です 読者をやめる 読者になる 読者になる

naoya_t@hatenablog

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

Google Code Jam 2014 - Round 1C

Google Code Jam Programming Contest

観戦してるだけってのも何だし、問題文は読めるのでカフェで解いてみた。
※Small/Largeデータがダウンロード出来るのは終戦後(20:30)Practice落ちしてから。

19:20開始
A) small 20:33 AC (8pt), large 20:33 AC (12pt)
B) small 20:35 AC (10pt)
C) small 20:50 AC (15pt)
ここまでで45点(1時間半でno WAなので458位相当)取れてるので、ここで参加しててもR2進出は出来たと思う。

A. Part Elf

約分(Smallでは不要)して、分母が2^nであることを確認して、
分子を2進数で見たときの桁数から最小世代を割り出す。
みたいなことを、GCCのビルトイン関数オンパレードでw

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
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(c,i)  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())

vector<string> split(string str, int delim=' ')
{
  vector<string> result;

  const char *s = str.c_str();
  if (delim == ' ') {
    for (const char *p=s; *p; p++) {
      if (*p == delim) s++;
      else break;
    }
    if (!*s) return result;

    for (const char *p=s; *p; p++) {
      if (*p == delim) {
        if (s < p) {
          string a(s,p-s);
          result.push_back(a);
        }
        s = p + 1;
      }
    }
    if (*s) result.push_back(s);
  } else {
    for (const char *p=s; *p; p++) {
      if (*p == delim) {
        string a(s,p-s);
        result.push_back(a);
        s = p + 1;
        if (*s == '\0') result.push_back("");
      }
    }
    if (*s) result.push_back(s);
  }

  return result;
}

ll gcd(ll m, ll n){
  while(m) swap(m, n%=m);
  return n;
}

int two(ll n){
  int g=0;
  while (n > 1LL) {
    if ((n & 1LL) == 0) {
      n >>= 1LL; ++g;
    } else {
      if (n > 1) return -1;
    }
  }
  return g;
}

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

    string s; cin >> s;
    vector<string> fs = split(s, '/'); // P/Q, 1e3, 1e12
    ll p = strtoll(fs[0].c_str(), NULL, 10);
    ll q = strtoll(fs[1].c_str(), NULL, 10);
    ll g = gcd(p, q);
    p /= g; q /= g;

    // ffs: 2進で表した場合に小さい方から何桁目に初めて1が現れるか
    // clz: 左側にゼロをいくつ埋めるか
    int q_ffs = __builtin_ffsll(q);
    int q_clz = __builtin_clzll(q), qk = 64 - q_clz;
    int p_clz = __builtin_clzll(p), pk = 64 - p_clz;

    if (q_ffs != qk) {
      cout << "impossible" << endl;
      continue;
    }
    int gen = (qk-1) - (pk-1); // ←ここ __builtin_clzll(p) - __builtin_clzll(q) でよくね?
    cout << gen << endl;
  }
}

B. Reordering Traing Cars

brute force.
next_permutation() で 10! 通り全部ためしちゃえばいいじゃん

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>
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(c,i)  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())

string press(string& s){
  vector<char> tmp;
  int l=sz(s);
  char last = s[0];
  tmp.pb(last);
  for(int i=1; i<l; ++i){
    if (s[i] == last) {
      continue;
    } else {
      last = s[i];
      tmp.pb(last);
    }
  }
  return string(all(tmp));
}

bool isvalid(string s) {
  int l=sz(s);
  vector<int> v(26, -1);
  rep(i,l){
    int c = s[i]-'a';
    if (v[c] == -1 || v[c] == i-1) {
      v[c] = i;
    } else {
      return false;
    }
  }
  return true;
}

int main(){
  int _T; cin>>_T; // 1-100
  rep(_t,_T){
    int N; cin >> N; // 1-10, 1-100
    vector<string> s(N);
    rep(i,N) {
      string tmp; cin >> tmp;
      s[i] = press(tmp);
    }

    vector<int> iota(N); rep(i,N) iota[i] = i;

    ll cnt = 0;
    do {
      stringstream ss;
      rep(i,N){
        ss << s[ iota[i] ];
      }
      if (isvalid(ss.str())) ++cnt;
    } while (next_permutation(all(iota)));

    cnt %= 1000000007LL;

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

C. Enclosure

brute force.
spotの配置を全部試しても2^20通りだし。

#include <iostream>
#include <vector>
#include <algorithm>
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(c,i)  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())

int n, m, k, nm;

int enclose(int p){
  vector<int> vmin(m,nm), vmax(m,-1);// for some x
  vector<int> hmin(n,nm), hmax(n,-1);// for some y

  // vector<vector<bool> > spot(n, vector<bool>(m, false));

  for (int i=0,mask=1; i<nm; ++i,mask<<=1) {
    if (!(p & mask)) continue;
    int y=i/m, x=i%m;
    // spot[y][x] = true;
    if (y < vmin[x]) vmin[x] = y;
    if (y > vmax[x]) vmax[x] = y;
    if (x < hmin[y]) hmin[y] = x;
    if (x > hmax[y]) hmax[y] = x;
  }

  vector<vector<bool> > stones(n, vector<bool>(m, false));
  rep(x,m){
    if (vmin[x] < nm) {
      stones[ vmin[x] ][x] = true;
      stones[ vmax[x] ][x] = true;
    }
  }
  rep(y,n){
    if (hmin[y] < nm) {
      stones[y][ hmin[y] ] = true;
      stones[y][ hmax[y] ] = true;
    }
  }
  int cnt = 0;
  rep(x,m) rep(y,n) {
    if (stones[y][x]) ++cnt;
  }
  /*
  printf("%x\n", p);
  rep(y,n) {
    rep(x,m) {
      if (stones[y][x]) {
        if (spot[y][x])
          printf(" *");
        else
          printf(" x");
      } else {
        if (spot[y][x])
          printf(" .");
        else
          printf("  ");
      }
    }
    printf("\n");
  }
  */
  return cnt;
}

int solve() {
  int P = 1 << nm; // 2^20 = 1048576
  int best = nm;
  rep(p, P) {
    if (__builtin_popcount(p) != k) continue;
    int st = enclose(p);
    if (st < best){
      best = st;
    }
  }
  return best;
}

int main(){
  int _T; cin>>_T; // 1-100
  rep(_t,_T){
    cin >> n >> m >> k; nm=n*m;
    cout << "Case #" << (1+_t) << ": " << solve() << endl;
  }
}