naoya_t@topcoder

Google Code Jam: Round 1C (2.5hrs)

19:25 |

• 9/13 18:00JST〜
• PRML hackathon #1の最中でしたが A,B を解いてみました
• watch onlyでデータセットはダウンロード出来ないのでただ解くだけ

A: All Your Base

• 21分
• 後で通してみる→通らない
• 111111... みたいな時に１進法になってたので直す→通った

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <algorithm>
#include <cmath>

//#include "cout.h"
using namespace std;

#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())

main()
{
  int T; cin >> T;

  string s;
  rep(t,T){
    cin >> s;
    int len=sz(s);
    map<int,int> chars;
    rep(i,len) chars[s[i]] = -1;

//  int base_min = sz(chars); /// ##OOPS##
    int base_min = max(sz(chars),2);

    vector<int> trans(len,-1);
    chars[s[0]] = 1;
    int n=0;
    long long result = 0LL;
    rep(i,len) {
      if (chars[s[i]] < 0) {
        chars[s[i]] = n++; if (n==1) n=2;
      }
      trans[i] = chars[s[i]];
      result = result * base_min + trans[i];
    }
    printf("Case #%d: %lld\n", 1+t, result);
  }
}

B: Center of Mass

• 27分
• 後で通してみる→通らない
• 合成した速度が 0 のときに divided by zero
• あと、方程式の誤差でNaNが出てたので式を変更→これで通った

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <algorithm>
#include <cmath>

//#include "cout.h"
using namespace std;

#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())

main()
{
  int T; cin >> T; // 1..100

  rep(t,T){
    int N; cin >> N; // 3..10(or 500)
    double x=0,y=0,z=0,vx=0,vy=0,vz=0;
    rep(n,N){
      int x_,y_,z_,vx_,vy_,vz_;
      cin >> x_ >> y_ >> z_ >> vx_ >> vy_ >> vz_;
      x += x_; y += y_; z += z_;
      vx += vx_; vy += vy_; vz += vz_;
    }
    x /= N; y /= N; z /= N;
    vx /= N; vy /= N; vz /= N;

    // (x + vx*t, y + vy*t, z + vz*t)
    // x2 + y2 + z2
    // (2 x vx + 2 y vy + 2 z vz) t
    // (vx2 + vy2 + vz2) t2

    // (x,y,z) + (vx,vy,vz)t = (x + vx.t, y + vy.t, z + vz.t)
    // distance = sqrt{ (x^2 + y^2 + z^2) + 2t(x.vx + y.vy + z.vz) + t^2(vx^2 + vy^2 + vz^2) }
    double c = x*x + y*y + z*z;
    double b = x*vx + y*vy + z*vz;
    double a = vx*vx + vy*vy + vz*vz;

    double tmin, dmin;
    if (a == 0) { //### a=0の分岐を追加
      // v = 0
      tmin = 0;
      dmin = sqrt(c);
    } else {
      // a t2 + 2 b t + c
      // 2(at + b) = 0, t = -b/a

      double t = -b/a;
      tmin = max(t, 0.0);

      //dmin = sqrt(tmin*tmin*a + tmin*b*2 + c); //###時々0をわずかながら下回りNaNになるので、下の式に変更
      dmin = sqrt( (x + vx*tmin) * (x + vx*tmin)
                 + (y + vy*tmin) * (y + vy*tmin)
                 + (z + vz*tmin) * (z + vz*tmin) );
    }
    printf("Case #%d: %10.8f %10.8f¥n", 1+t, dmin, tmin);
  }
}

C: Bribe the Prisoners

• 見てない
• とりあえず上の２問で50点。wrong answerを2回かましてペナルティ食らったと思うけど500番台で通過できるスコア（C解いてたらもうちょっと上か）
• あとで見る。（これが１時間ちょいで解ければフルスコア通過）
• 見てみた (2009/9/20)
  • これが一番簡単な気がした。毎回分断されていくので単純なDP。配点50って何
  • 29分

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <algorithm>
#include <cmath>

//#include "cout.h"
using namespace std;

#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 P, Q;
vector<int> qs;
map<pair<int,int>,int> m;

int sub(int left, int right)
{
  pair<int,int> k = make_pair(left,right);
  if (found(m,k)) {
    //printf("sub(%d, %d) == %d¥n", left, right, m[k]);
    return m[k];
  }

  int retmin = INT_MAX;
  tr(qs,it){
    if (*it < left || right < *it) continue;
    int ret = right - left; // 1-20なら19
    if (left < *it) ret += sub(left, *it - 1);
    if (*it < right) ret += sub(*it + 1, right);
    if (ret < retmin) retmin = ret;
  }
  if (retmin == INT_MAX) retmin = 0;
  
  m[k] = retmin;
  //printf("sub(%d, %d) := %d¥n", left, right, m[k]);
  return retmin;
}

main()
{
  int T; cin >> T; // 1..100

  rep(t,T){
    cin >> P >> Q;
    qs.resize(Q); rep(q,Q) cin >> qs[q];
    sort(all(qs));

    m.clear();
    printf("Case #%d: %d¥n", 1+t, sub(1,P));
  }
}

• largeも31.9秒... -O3でコンパイルして6.2秒
• というわけでめでたくフルスコア通過
  • A,Bの修正＆再投稿も含めた合計所要時間は1時間45分前後、途中WA×2でペナルティ8分とすると1時間53分前後。90番台か。