Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-12-24

来年の為に

23:57 | 来年の為に - naoya_t@topcoder を含むブックマーク はてなブックマーク - 来年の為に - naoya_t@topcoder 来年の為に - naoya_t@topcoder のブックマークコメント

今年はSRM皆勤したけどほとんど練習出来なかった。Easyがsubmitできないなんて色々終わってるので過去問で練習したい。

  • Practice Roomにある過去問はSRM144から
  • 毎日1回分解いてたら1年で終わる量
  • やった事のある問題も当然あるけど何度でもやる。というか前より速くなってるべき

というわけでSRM144から。方針はDIV1の

  • Easyは必須
  • Mediumも解く
  • Hardも問題は読む

という感じで始めたい。

過去問マラソン(#1):SRM144

| 23:57 | 過去問マラソン(#1):SRM144 - naoya_t@topcoder を含むブックマーク はてなブックマーク - 過去問マラソン(#1):SRM144 - naoya_t@topcoder 過去問マラソン(#1):SRM144 - naoya_t@topcoder のブックマークコメント

得点配分が今と違う感じ

Easy(300): BinaryCode

  • 前にやった記憶あり
  • こういうのすぐにコーディングすると空中分解するタイプ
  • とりあえず解けるんだけどchar[]で解いてるしここはSTL使ってなんとかしたい。で
  • を今頃知った。
  • 入力長が1,2の場合が例外的なので気をつけて
    • pの両側に門番(0)をつけた方が条件分岐なくて良いので楽。最後のpに非0が来たら"NONE"
#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()

class BinaryCode {
 public:
  string guess(string m,int p0){
    int n=sz(m);
    vector<char> q(all(m)), p(n+2);
    rep(i,n) q[i]-='0'; p[0]=0, p[1]=p0;//, p[n+1]=0;
    FOR(i,1,n+1) p[i+1]=q[i-1]-p[i]-p[i-1];
    if (p[n+1]!=0) return "NONE";
    
    FOR(i,1,n) { if(p[i]<0||1<p[i]) return "NONE"; else p[i]+='0'; }
    return string(p.begin()+1, p.end()-1);
  }
  vector <string> decode(string message) {
    vs ans;
    ans.pb( guess(message,0) );
    ans.pb( guess(message,1) );
    return ans;
  }
};

Medium(550): Lottery

  • 前にも見たかも
  • 文字列パース。というかsplit
  • sortedはDP
  • わりとすんなり書けた(と言っても25'16'')
  • system test一発OK
typedef long long ll;
typedef vector<string> vs;
#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 FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define found(s,e)  ((s).find(e)!=(s).end())
typedef pair<int,int> i_i;

// 自作split
vector<string> split(string str, string delim) {
  // 略
}
vector<string> split(string str, int delim=' ') {
  // 略
}

bool atob(string s){ return s[0]=='T'; }

ll pow(int x,int y){ // x^y
  ll ans=1LL; rep(i,y) ans *= (ll)x; return ans;
}
ll fac(int x,int y){ // x!/(x-y)!
  ll ans=1LL; rep(i,y) ans *= (ll)(x--); return ans;
}
class Lottery {
  map<i_i,ll> m1, m2;
  ll sub_sorted_unique(int choices,int blanks){ // 1 2 3 ...
    if (blanks==0) return 1;
    i_i key=cons(choices,blanks);
    if(found(m1,key)) return m1[key];
    ll sum=0LL;
    rep(i,choices){
      sum += sub_sorted_unique(choices-i-1,blanks-1);
    }
    m1[key]=sum;
    return sum;
  }
  ll sub_sorted(int choices,int blanks){ // 1 1 2 ...
    if (blanks==0) return 1;
    i_i key=cons(choices,blanks);
    if(found(m2,key)) return m2[key];
    ll sum=0LL;
    rep(i,choices){
      sum += sub_sorted(choices-i,blanks-1);
    }
    m2[key]=sum;
    return sum;
  }
  ll num(string name, int choices, int blanks, bool sorted, bool unique) {
    // number of valid lottery tickets for that game...
    // choices: 10-100 ... [1..choices]
    // blanks: 1-8
    ll cnt = 0LL;

    if (sorted) {
      if (unique) {
        // 1 2 3 4 5
        cnt = sub_sorted_unique(choices,blanks);
      } else {
        // 1 1 2 3 3
        cnt = sub_sorted(choices,blanks);
      }
    } else {
      if (unique) {
        // 3 2 1 5 4
        cnt = fac(choices,blanks);
      } else {
        // 3 3 1 2 1
        cnt = pow(choices,blanks); // 1e2 ^ 8 = 1e16
      }
    }
/*   
    printf("name:%s choices:%d blanks:%d sorted:%s unique:%s => %lld\n",
           name.c_str(), choices, blanks, sorted?"YES":"NO", unique?"YES":"NO",
           cnt);
*/
    return cnt;
  }
 public:
  vector <string> sortByOdds(vector<string> rules) {
    m1.clear(); m2.clear();
    
    vector<pair<ll,string> > res;
    tr(rules,st){
      vs a1 = split(*st,": ");
      string name = a1[0];
      vs a2 = split(a1[1],' ');
      int choices = atoi(a2[0].c_str()), blanks = atoi(a2[1].c_str());
      bool sorted = atob(a2[2]), unique = atob(a2[3]);

      res.pb(cons(num(name,choices,blanks,sorted,unique),name));
    }
    sort(all(res));// reverse(all(res));
    vs ans;
    tr(res,it) ans.pb(it->second);
    return ans;
  }
};

Hard(1100): PenLift

  • プロッタ懐かしい
  • とか言ってる場合じゃなくて
  • とりあえずグラフに変換
    • 同じ向きの繋がった(or 重なった)線分を検出し、union-findしといて後でまとめる
    • 線分を交差点で区切り、nodeとarcを抽出
    • union-findして島分割
    • n回重ね書きするのでarcの本数を各n倍にする
    • それぞれの島が何筆書きになるか、で行ける
      • (ここまでで3時間半。sample case#5がちゃんと解けてない!intersection判定にバグあり?)
    • 結局4時間半かかって解けた
    • system test一発OK
    • 以下駄コード
      • cons,car,cdr,caar,cadr,cdar,cddrとかまあ気にしないで
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<string> vs;
#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 FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

typedef pair<int,int> i_i;
typedef pair<ll,ll> ll_ll;
typedef pair<double,double> d_d;
typedef pair<int,pair<int,int> > i_ii;
#define cons(x,y) make_pair((x),(y))
#define car(x) ((x).first)
#define cdr(x) ((x).second)
#define caar(x) (x).first.first
#define cdar(x) (x).first.second
#define cadr(x) (x).second.first
#define cddr(x) (x).second.second

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;
}

vector<int> map_atoi(vector<string> nums)
{
  vector<int> vals(nums.size());
  for (int i=nums.size()-1; i>=0; i--) vals[i] = atoi(nums[i].c_str());
  return vals;
}

typedef pair<int,int> point;
typedef pair<point,point> segment;

vector<segment> segments;
vector<bool> deleted;
vector<int> dirs;

int dir(const segment& s){
  point p1 = car(s), p2 = cdr(s);
  if (p1==p2) return -1;
  if (car(p1)==car(p2)) // x1=x2
    return (p2.second > p1.second)?1:3;
  else
    return (p2.first > p1.first)?0:2;
}
segment rev(const segment& s){
  return cons(cdr(s),car(s));
}

segment joint(int i, int j){
  segment s1 = segments[i], s2 = segments[j];
  int dir = dirs[i]; // assume dirs[i]=dirs[j]
  if (dir==0) { // horizontal
    int y = cdar(s1);
    int x0 = min( caar(s1),caar(s2) ),
        x1 = max( cadr(s1),cadr(s2) );
    return cons(cons(x0,y),cons(x1,y));
  } else {
    int x = caar(s1);
    int y0 = min( cdar(s1),cdar(s2) ),
        y1 = max( cddr(s1),cddr(s2) );
    return cons(cons(x,y0),cons(x,y1));
  }
}

point cross(int i, int j){
  segment s1 = segments[i], s2 = segments[j];
  int d1 = dirs[i], d2 = dirs[j];
  if (d1==1 && d2==0) return cross(j,i);
  int y=cdar(s1);
  if (cdar(s2) <= y && y <= cddr(s2)) {
    FOR(x,caar(s1),cadr(s1)) {
      // x,y
      if(x==caar(s2)) return cons(x,y);
    }
  }
  return cons(INT_MAX,INT_MAX);
}

bool oddp(int n){
  return (n & 1)? true : false;
}

class UnionFind {
  vector<int> data;
 public:  
  UnionFind(int size) : data(size, -1) { }
  
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};

class PenLift {
 public:
  int numTimes(vector<string> segs, int n) {
    int N = sz(segs);
    segments.resize(N);
    deleted.resize(N);
    dirs.resize(N);
    
	rep(i,N){ // segment_id
      vector<int> t = map_atoi(split(segs[i]));
      segment s = cons(cons(t[0],t[1]), cons(t[2],t[3]));
      if (dir(s) >= 2) s = rev(s);
      segments[i] = s; deleted[i] = false;
      dirs[i] = dir(s);
    }
    
    // joint
    UnionFind uf0(N); set<int> jointed;
    FOR(i,0,N-2){
      FOR(j,i+1,N-1){
        if (dirs[i]==dirs[j]) {
          if (dirs[i]==0) { // h
            int yi = cdar(segments[i]), yj = cdar(segments[j]);
            if (yi != yj) continue;
            int x0 = caar(segments[i]), x1 = cadr(segments[i]),
                x2 = caar(segments[j]), x3 = cadr(segments[j]);
            if (x0>x2) { swap(x0,x2); swap(x1,x3); } // x0 <= x2
            if (x2 <= x1) {
              uf0.unionSet(i,j);
              jointed.insert(i); jointed.insert(j);
            }
          } else { // v
            int xi = caar(segments[i]), xj = caar(segments[j]);
            if (xi != xj) continue;
            int y0 = cdar(segments[i]), y1 = cddr(segments[i]),
                y2 = cdar(segments[j]), y3 = cddr(segments[j]);
            if (y0>y2) { swap(y0,y2); swap(y1,y3); } // y0 <= y2
            if (y2 <= y1) {
              uf0.unionSet(i,j);
              jointed.insert(i); jointed.insert(j);
            }
          }
        }
      }
    }
    map<int,set<int> > joint_isle;
    tr(jointed,it){
      int root = uf0.root(*it);
      if (!found(joint_isle,root)) {
        set<int> s;
        joint_isle[root] = s;
      }
      //if (*it != root)
      joint_isle[root].insert(*it);
    }

    tr(joint_isle,it) {
      int root=it->first;
      if (dirs[root] == 0) { // horizontal
        int y = cdar(segments[root]);
        int xmin = INT_MAX, xmax = INT_MIN;
        tr(it->second,jt) {
          segment s = segments[*jt];
          int x0 = caar(s), x1 = cadr(s);
          if (x0 > x1) swap(x0,x1);
          xmin = min(xmin,x0);
          xmax = max(xmax,x1);
          deleted[*jt] = true;
        }
        segments[root] = cons(cons(xmin,y),cons(xmax,y));
        deleted[root] = false;
      } else { // vertical
        int x = caar(segments[root]);
        int ymin = INT_MAX, ymax = INT_MIN;
        tr(it->second,jt) {
          segment s = segments[*jt];
          int y0 = cdar(s), y1 = cddr(s);
          if (y0 > y1) swap(y0,y1);
          ymin = min(ymin,y0);
          ymax = max(ymax,y1);
          deleted[*jt] = true;
        }
        segments[root] = cons(cons(x,ymin),cons(x,ymax));
        deleted[root] = false;
      }
    }
    // cross
    vector<set<point> > seps(N,set<point>());
    FOR(i,0,N-2){
      if (deleted[i]) continue;
      
      FOR(j,i+1,N-1){
        if (deleted[j]) continue;
        
        if (dirs[i]!=dirs[j]) {

          point nx = cross(i,j);
          if (car(nx)==INT_MAX) continue;
          seps[i].insert(nx);
          seps[j].insert(nx);
        }
      }
    }

    rep(segment_id,N) {
      int sepsz = sz(seps[segment_id]);
      if (sepsz > 0) {
        deleted[segment_id] = true;
        
        if (dirs[segment_id]==0) { // horizontal
          int y = cdar(segments[segment_id]);
          set<int> xs;
          xs.insert(caar(segments[segment_id]));
          xs.insert(cadr(segments[segment_id]));
          tr(seps[segment_id],it) xs.insert(it->first);
          vector<int> xsv(all(xs));
          sort(all(xsv));
          rep(k,sz(xsv)-1) {
            segment sk = cons(cons(xsv[k],y),cons(xsv[k+1],y));
            segments.pb(sk); deleted.pb(false);
          }
        } else { // vertical
          int x = caar(segments[segment_id]);
          set<int> ys;
          ys.insert(cdar(segments[segment_id]));
          ys.insert(cddr(segments[segment_id]));
          tr(seps[segment_id],it) ys.insert(it->second);
          vector<int> ysv(all(ys));
          sort(all(ysv));

          rep(k,sz(ysv)-1) {
            segment sk = cons(cons(x,ysv[k]),cons(x,ysv[k+1]));

            segments.pb(sk); deleted.pb(false);
          }
        }
      }
    }

    // 両端登録
    map<point,set<int> > nodes; // points[point] = { segment_ids }

    rep(segment_id,sz(segments)){
      if (deleted[segment_id]) continue;
      vector<point> n(2);
      n[0]=car(segments[segment_id]);
      n[1]=cdr(segments[segment_id]);

      rep(node_id,2) {
        if(found(nodes,n[node_id])) {
          nodes[n[node_id]].insert(segment_id);
        } else {
          set<int> s; s.insert(segment_id);
          nodes[n[node_id]] = s;
        }
      }
    }

    UnionFind uf(sz(segments));

    tr(nodes,nt){
      set<int> arcs = nt->second;
      vector<int> av(all(arcs)); FOR(i,1,sz(av)-1) uf.unionSet(av[0],av[i]);
    }

    map<int,int> isles;
    rep(i,sz(segments)) {
      if (deleted[i]) continue;
      int root = uf.root(i);
      if (!found(isles,root)) isles[root] = 0;
    }

    // again
    tr(nodes,nt){
      point node = nt->first;
      set<int> arcs = nt->second;
      vector<int> av(all(arcs));
      int root = uf.root(av[0]);
      if (oddp(sz(arcs)*n)) isles[root]++;
    }
    tr(isles,it) { it->second /= 2; }

    int ans = sz(isles)-1;
    tr(isles,it) {
      if (it->second == 0) continue;
      ans += it->second - 1;
    }
   
    return ans;
  }
};
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20091224