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番台か。

Google Code Jam: Round 1B (2.5hrs)

11:13 |

• 9/13 1:00am (JST)〜
• 1Aで落ちてたらいけないので、一応1amに待機していた
• 参加できない (watch only)
• でも問題は見れるので解くよ
• A と B まで解いて１時間弱

A: Decision Treee

もちろんschemeで解きました

• printfは自作のやつを使ってます。（ソース略）

;;;
;;; in Gauche 0.8.14
;;; http://practical-scheme.net/gauche/
;;;
(use srfi-1)

(define (read-int)
  (x->integer (read-line)))

(define (read-args-in-line)
  (let1 s (string-append "(" (read-line) ")")
    (read-from-string s)))

(define (read-sexp-in-lines l)
  (let loop ((i 0) (s ""))
    (if (= i l) (read-from-string s)
        (loop (+ i 1) (string-append s (read-line))))))

(define (tree-weight tr) (car tr)) ; [0.0 .. 1.0]
(define (tree-has-child? tr) (not (null? (cdr tr))))
(define (tree-feature tr) (if (tree-has-child? tr) (cadr tr) #f))
(define (tree-tree1 tr) (if (tree-has-child? tr) (caddr tr) #f))
(define (tree-tree2 tr) (if (tree-has-child? tr) (cadddr tr) #f))

(define (dive tr fht p)
  (let1 p* (* p (tree-weight tr))
    (if (tree-has-child? tr)
        (if (hash-table-get fht (tree-feature tr) #f)
            (dive (tree-tree1 tr) fht p*)
            (dive (tree-tree2 tr) fht p*))
        p*)))

(let1 N (read-int)
  (dotimes (testcase N)
    (format #t "Case #~d:¥n" (+ 1 testcase))
    
    (let* ([L (read-int)]
           [tr (read-sexp-in-lines L)]
           [number-of-animals (read-int)])
      (dotimes (i number-of-animals)
        (let* ([animal-n-features (read-args-in-line)]
               [animal (car animal-n-features)]
               [features (cddr animal-n-features)]
               [fht (make-hash-table 'eq?)])
          (for-each (cut hash-table-put! fht <> #t) features)
          (let1 c (dive tr fht 1.0)
            (printf "%9.7f¥n" c)
            ))))))

B: The Next Number

• next_permutation使いたいのでC++
• 一周回って戻ってきてたら繰り上がり、0を１つ挿入
  • 最初が0の場合は0でない最初の数字を最初に持ってくる操作が必要。最初これをnext_permutationのループで書いてたが最悪ケースで全然すすまない事に気づいたので書き直した

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

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; string s;

  cin >> T;
  getline(cin,s);

  char buf[256];
  
  rep(t,T){
    getline(cin,s);
    int len = sz(s);

    vector<int> d(len);
    rep(i,len) d[i] = s[i] - '0';
    vector<int> bup(all(d));
    
    next_permutation(all(d));
    if (d <= bup) {
      buf[len+1] = 0;
      buf[0] = '0'; rep(i,len) buf[1+i] = '0'+d[i];
      rep(i,len+1) {
        if (buf[i]>'0'){
          buf[0] = buf[i];
          for(int j=1;j<=i;j++) buf[j]='0';
          break;
        }
      }
      printf("Case #%d: %s\n", 1+t, buf);
    } else {
      buf[len] = 0;
      rep(i,len) buf[i] = '0'+d[i];
      printf("Case #%d: %s\n", 1+t, buf);
    }
  }
}

C: Square Math

• ネットワークを書くのに時間かかってた
• ２時間半には間に合わず
• 書きかけのコードを以下に晒します

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

class way;

class node {
 public:
  int id;
  int x, y, v;
  vector<way*> outlets;

  node(int id){
    this->x = -1;
    this->y = -1;
    this->v = -1;
    this->id = id;
  }
  node(int x, int y, int v, int id) {
    this->x = x;
    this->y = y;
    this->v = v;
    this->id = id;
  }
  void addOutlet(way* way) { outlets.pb(way); }
};

class way {
 public:
  node *from, *to;
  int ofs;
  char says[3];

  way(node *from,node *to,int pm,int ofs) {
    this->from = from;
    this->to = to;
    this->ofs = pm * ofs;
    from->addOutlet(this);
    says[2] = 0;
    says[1] = '0' + ofs;
    says[0] = "-=+"[pm+1];
  }
};

inline int mag(int ch)
{
  return (ch == '+')? 1 : -1;
}

vector<node*> nodes; int node_id = 0;
vector<way*> ways;

typedef pair<int,pair<string,pair<node*,int> > > stat;
inline stat make_stat(int score, string str, node *n, int val)
{
  return make_pair(-score,make_pair(str,make_pair(n,val)));
}
inline int stat_score(stat st) { return -st.first; }
inline string stat_str(stat st) { return st.second.first; }
inline node* stat_node(stat st) { return st.second.second.first; }
inline int stat_val(stat st) { return st.second.second.second; }

main()
{
  int T;
  cin >> T;
  
  rep(t,T){
    int W, Q;
    cin >> W >> Q;

    vector<string> asq;
    vector<int> nums(Q,0);

    node *root = new node(node_id++);
    vector<vector<node*> > nodefind(W,vector<node*>(W,(node*)NULL));

    // pass1
    rep(y,W){
      string s;
      cin >> s;
      asq.pb(s);
      rep(x,W){
        if (isdigit(s[x])) {
          node *a_node = new node(x,y,s[x]-'0',node_id++);
          nodefind[y][x] = a_node;
          way *a_way = new way(root,a_node,0,s[x]-'0');
          nodes.pb(a_node);
        }
      }
    }
    // pass2
    tr(nodes,it){
      node *me = *it;
      //n->x, n->y
      int x=me->x, y=me->y, v=me->v;
      // printf("  NODE %d at (%d,%d)¥n", v,x,y);
      // 上
      if (0<y) {
        int pm = mag(asq[y-1][x]);
        if (1<y) {
          //cout << "<nn>" << endl;
          node *nn = nodefind[y-2][x];
          way *wn = new way(me,nn,pm,nn->v);
          ways.pb(wn);
        }
        if (0<x) {
          //cout << "<nw>" << endl;
          node *nn = nodefind[y-1][x-1];
          way *wn = new way(me,nn,pm,nn->v);
          ways.pb(wn);
        }
        if (x<W-1) {
          //cout << "<ne>" << endl;
          node *nn = nodefind[y-1][x+1];
          way *wn = new way(me,nn,pm,nn->v);
          ways.pb(wn);
        }
        {
          //cout << "<ns!>" << endl;
          way *wn = new way(me,me,pm,v);
          ways.pb(wn);
        }
      }
      // 左
      if (0<x) {
        int pm = mag(asq[y][x-1]);
        if (0<y) {
          //cout << "<wn>" << endl;
          node *nn = nodefind[y-1][x-1];
          way *wn = new way(me,nn,pm,nn->v);
          ways.pb(wn);
        }
        if (1<x) {
          //cout << "<ww>" << endl;
          node *nn = nodefind[y][x-2];
          way *wn = new way(me,nn,pm,nn->v);
          ways.pb(wn);
        }
        {
          //cout << "<we!>" << endl;
          way *wn = new way(me,me,pm,v);
          ways.pb(wn);
        }
        if (y<W-1) {
          //cout << "<ws>" << endl;
          node *nn = nodefind[y+1][x-1];
          way *wn = new way(me,nn,pm,nn->v);
          ways.pb(wn);
        }
      }
      // 右
      if (x<W-1) {
        int pm = mag(asq[y][x+1]);
        if (0<y) {
          //cout << "<en>" << endl;
          node *nn = nodefind[y-1][x+1];
          way *wn = new way(me,nn,pm,nn->v);
          ways.pb(wn);
        }
        {
          //cout << "<ew!>" << endl;
          way *wn = new way(me,me,pm,v);
          ways.pb(wn);
        }
        if (x<W-2) {
          //cout << "<ee>" << endl;
          node *nn = nodefind[y][x+2];
          way *wn = new way(me,nn,pm,nn->v);
          ways.pb(wn);
        }
        if (y<W-1) {
          //cout << "<es>" << endl;
          node *nn = nodefind[y+1][x+1];
          way *wn = new way(me,nn,pm,nn->v);
          ways.pb(wn);
        }
      }
      // 下
      if (y<W-1) {
        int pm = mag(asq[y+1][x]);
        {
          //cout << "<sn!>" << endl;
          way *wn = new way(me,me,pm,v);
          ways.pb(wn);
        }
        if (0<x) {
          //cout << "<sw>" << endl;
          node *nn = nodefind[y+1][x-1];
          way *wn = new way(me,nn,pm,nn->v);
          ways.pb(wn);
        }
        if (x<W-1) {
          //cout << "<se>" << endl;
          node *nn = nodefind[y+1][x+1];
          way *wn = new way(me,nn,pm,nn->v);
          ways.pb(wn);
        }
        if (y<W-2) {
          //cout << "<ss>" << endl;
          node *nn = nodefind[y+2][x];
          way *wn = new way(me,nn,pm,nn->v);
          ways.pb(wn);
        }
      }
    }
    
    rep(q,Q) cin >> nums[q];

    cout << "square: " << asq;
    cout << "nums: " << nums << endl;
    /*
    cout << "nodes: " << sz(nodes) << endl;
    tr(nodes,it) {
      node *n = *it;
      printf("  : node#%d, value=%d at (%d,%d)¥n", n->id, n->v, n->x, n->y);
    }
    cout << "ways: " << sz(ways) << endl;
    tr(ways,it) {
      way *w = *it;
      printf("  : %s to node#%d¥n", w->says, w->to->id);
    }
    */
    //cout << "nums: " << nums << endl;
    printf("Case #%d:¥n", 1+t);
    tr(nums,nt) {
      int target = *nt;
      priority_queue<stat> pq;
    // pair<int,pair<string,pair<node*,int> > > > 
      pq.push( make_stat(target,"",root,0) );

      while (!pq.empty()) {
        stat s = pq.top(); pq.pop();
        int sc = stat_score(s), v = stat_val(s);
        node *n = stat_node(s);
        if (sc == 0) {
          //printf("now on node#%d, '%s', value=%d¥n", n->id, stat_str(s).c_str(), v);
          //continue;
          cout << stat_str(s) << endl;
          break;
        }
        tr(n->outlets,it){
          way *w = *it;
          int v_ = v + w->ofs;
          pq.push( make_stat(abs(v_-target), stat_str(s) + w->says, w->to, v_) );
        }
      }
    }
  }
}

試合後投稿

• practice roomが開いたらとりあえずsubmitしてみた
• Aはすんなり通過
• BはLargeが重くてひっかかったので書き直し＋再実行も含め５分ぐらい
• ２問分のコーディングに50分前後、投稿に５分前後かかったので180位相当。このRound 1Bに出てても余裕で通過できたっぽい