naoya_t@topcoder

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に出てても余裕で通過できたっぽい