Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-03-09

過去問マラソン(#14):SRM154(続き)

| 13:32 | 過去問マラソン(#14):SRM154(続き) - naoya_t@topcoder を含むブックマーク はてなブックマーク - 過去問マラソン(#14):SRM154(続き) - naoya_t@topcoder 過去問マラソン(#14):SRM154(続き) - naoya_t@topcoder のブックマークコメント

Medium(500): ContestScore

  • 一見難しくなさそうなんだけど
  • まんまと罠にひっかかりました
初回投稿:
  • 290.96 (28'52'')
#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++)

class ContestScore {

 public:
  vector <string> sortResults(vector <string> data) {
	int n=sz(data);//0-50
    vector<vector<double> > scores(n,vector<double>());
    vector<string> groupnames(n);
    int judges = 0;
    rep(i,n){
      istringstream ss(data[i]);
      ss >> groupnames[i];
      if (judges) {
        rep(j,judges) { double tmp; ss >> tmp; scores[i].pb(tmp); }
      } else {
        while (!ss.eof()) { double tmp; ss >> tmp; scores[i].pb(tmp); judges++; }
      }
    }

    vector<vector<int> > ranks(n,vector<int>(judges) );
    rep(j,judges){
      vector<pair<double,int> > jscores(n);
      rep(i,n) jscores[i] = make_pair(-scores[i][j], i);
      sort(all(jscores));

      int lastrank = 1, rankcnt = 1; double lastscore = jscores[0].first;
      vector<int> jranks(n);
      rep(i,n) {
        if (jscores[i].first == lastscore) {
          jranks[ jscores[i].second ] = lastrank;
        } else {
          jranks[ jscores[i].second ] = rankcnt; lastrank = rankcnt;
        }
        rankcnt++; lastscore = jscores[i].first;
      }
      rep(i,n) ranks[i][j] = jranks[i];
    }

    vector<int> ranksum(n,0); vector<double> scoresum(n,0);
    vector<pair<int,pair<double,string> > > thescore(n);
    
    rep(i,n) {
      rep(j,judges) {
        ranksum[i] += ranks[i][j];
        scoresum[i] += scores[i][j];
      }
      thescore[i] = make_pair(ranksum[i],make_pair(-scoresum[i],groupnames[i]));
    }
    sort(all(thescore));

    vector<string> ans;
    rep(i,n) {
      stringstream ss;
      ss << thescore[i].second.second << " " << thescore[i].first << " " << -thescore[i].second.first;
      bool point=false;
      tr(ss.str(),it){
        if (*it == '.') {point=true;break;}
      }
      if (!point) ss << ".0";
      ans.pb(ss.str());
    }
    return ans;
  }
};
  • failed system test
  • 小数点以下第一位が0のときに「.0」を表示するようにしたつもりだったけど、サーバでは効いてなかった。(なぜだろう)
  • その箇所を
      char buf[256];
      sprintf(buf, "%s %d %3.1f",
              thescore[i].second.second.c_str(),
              thescore[i].first,
              -thescore[i].second.first);
      ans.pb(buf);
  • 別の問題が発生
FAILED (0.446 msec)
	Expected: { "A 22 594.8","AA 34 483.7","AAA 34 466.2","AAAA 46 395.1","AAAAA 46 395.1","AAAAAA 48 387.6","AAAAAAA 48 387.6","AAAAAAAA 49 371.5","AAAAAAAAA 52 304.3","AAAAAAAAAA 54 348.6", }
	Received: { "A 22 594.8","AA 34 483.7","AAA 34 466.2","AAAA 46 395.1","AAAAA 46 395.1","AAAAAAA 48 387.6","AAAAAA 48 387.6","AAAAAAAA 49 371.5","AAAAAAAAA 52 304.3","AAAAAAAAAA 54 348.6", }
  • なにこれ
  • rank合計もscore合計も同じ、で文字列比較でAAAAAA<AAAAAAAになるのが期待されるところ</li>
  • sortを比較関数渡し型にしてみた
  • score合計のところで異常。
    • 同じ数字に見えて 1.13687e-13 の差がある
    • なるほどそういうことか
    • スコアを全部10倍にして整数で保存するぞ!結果出力時に0.1掛けすればよいさ
最終投稿
#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++)

typedef pair<int,pair<int,string> > score_t;
#define make_score(R,S,N) make_pair(R,make_pair(S,N))
#define car first
#define cdr second
#define caar first.first
#define cdar first.second
#define cadr second.first
#define cddr second.second

bool cmp(score_t s1, score_t s2) {
  if (s1.car < s2.car) return true;
  if (s1.car > s2.car) return false;
  
  if (s1.cadr > s2.cadr) return true;
  if (s1.cadr < s2.cadr) return false;

  return s1.cddr < s2.cddr;
}

class ContestScore {

 public:
  vector <string> sortResults(vector <string> data) {
    int n=sz(data);//0-50
    if (n==0) return vector<string>();
    
    vector<vector<int> > scores(n,vector<int>());
    vector<string> groupnames(n);

    rep(i,n){
      istringstream ss(data[i]);
      ss >> groupnames[i];
      while (!ss.eof()) {
        double tmp; ss >> tmp;
        scores[i].pb((int)(tmp*10 + 0.5));
      }
    }
    int judges = sz(scores[0]);

    vector<vector<int> > ranks(n,vector<int>(judges) );
    rep(j,judges){
      vector<pair<int,int> > jscores(n);
      rep(i,n) jscores[i] = make_pair(-scores[i][j], i);
      sort(all(jscores));

      int lastrank = 1, rankcnt = 1; int lastscore = jscores[0].first;
      vector<int> jranks(n);
      rep(i,n) {
        if (jscores[i].first == lastscore) {
          jranks[ jscores[i].second ] = lastrank;
        } else {
          jranks[ jscores[i].second ] = rankcnt; lastrank = rankcnt;
        }
        rankcnt++; lastscore = jscores[i].first;
      }
      rep(i,n) ranks[i][j] = jranks[i];
    }

    vector<int> ranksum(n,0); vector<int> scoresum(n,0);
    vector<score_t> thescore(n);
    
    rep(i,n) {
      rep(j,judges) {
        ranksum[i] += ranks[i][j];
        scoresum[i] += scores[i][j];
      }
      thescore[i] = make_pair(ranksum[i],make_pair(scoresum[i],groupnames[i]));
    }
    sort(all(thescore),cmp);

    vector<string> ans;
    rep(i,n) {
      char buf[256];
      sprintf(buf, "%s %d %3.1f",
              thescore[i].cddr.c_str(),
              thescore[i].car,
              0.1 * thescore[i].cadr);
      ans.pb(buf);
    }
    return ans;
  }
};
  • passed system test
  • ふぅ
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100309

2010-02-08

過去問マラソン(#13):SRM154

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

Easy(350): CheatCode

  • 配点350点て何
  • 文字と必要打鍵数のペア、の配列をchainと仮に呼び
  • 後だけでなく前に余計な文字を打つのもアリだとsample caseで気づき
  • 途中に関係ない文字が入る場合はNG、ということにsample caseで気づき
  • ていうか問題ちゃんと読んだほうが結果的に早いのでは?
  • 149.37pt (50'25'') 時間かかりすぎ
  • passed system test
#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e)  ((s).find(e)!=(s).end())
#define cons(x,y) make_pair((x),(y))

typedef vector<pair<char,int> > chain;

class CheatCode {
  chain trans(string code) {
    chain co;
    int l=sz(code);
    char lastc=-1; int cn=0;
    rep(j,l){
      if (code[j]==lastc) cn++;
      else {
        if (lastc>0) co.pb(cons(lastc,cn));
        lastc=code[j]; cn=1;
      }
    }
    co.pb(cons(lastc,cn));
    return co;
  } 

  chain kp,code;

  bool accept(pair<char,int> c, pair<char,int> k) {
    if (c.first != k.first) return false;
    if (c.second > k.second) return false;
    return true;
  }
  bool match1(int ix,int kx) {
    if (ix == sz(code)) return true;
    if (sz(code)-ix > sz(kp)-kx) return false;
    if (!accept(code[ix],kp[kx])) return false;
 // for (int k=kx+1; k<=sz(kp); k++)
 //   if (match1(ix+1,k)) return true;
    if (match1(ix+1,kx+1)) return true;
    return false;
  }
  bool match() {
    int kpl = sz(kp), codel = sz(code);
    if (kpl<codel) return false;
    for(int kx=0; kx<=kpl-codel; kx++) {
      if (match1(0,kx)) return true;
    }
    return false;
  }
 public:
  vector<int> matches(string keyPresses, vector<string> codes) {
    kp = trans(keyPresses);
    vector<int> matched;
    rep(i,sz(codes)){
      code = trans(codes[i]);
      if (match()) matched.pb(i);
    }
    return matched;
  }
};

Medium(500)

Hard(1000)

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100208

2010-02-05

過去問マラソン(#12):SRM153(続き)

| 14:22 | 過去問マラソン(#12):SRM153(続き) - naoya_t@topcoder を含むブックマーク はてなブックマーク - 過去問マラソン(#12):SRM153(続き) - naoya_t@topcoder 過去問マラソン(#12):SRM153(続き) - naoya_t@topcoder のブックマークコメント

ちょっとブランクが空いたが気を取り直して。オフィスの環境テストを兼ねて過去問にトライ。

無刻印のHHKB Professional 2で初めて書くC++。打ちやすい。矢印キーが無い事が不慣れなので指慣らしに時々過去問でも解くか。

Medium(450): Collision

  • 今日も問題が頭に入ってこない...
  • 要は実装するだけ?
  • 211.83 (41'45'') インストール作業の裏でやっているとはいえ時間かけすぎ
  • passed system test
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++)

class Collision {
  vector<int> az; int iz, azn, tz;

  double memory(int i,int used,double nocol){ // have memory.
    if(i==azn) return nocol;
    int a = az[i];
    if (used+a > iz) return 0;
    long double r = 1.0;
    for(int j=0,l=iz,re=iz-used; j<a; j++,l--,re--){
      r = r * re / l;
    }
    return memory(i+1,used+a,nocol*r);
  }
  double no_memory(){
    long double r = 1.0;
    for(int i=0,l=iz;i<tz;i++,l--) {
      r = r * l / iz;
    }
    return (double)r;
  }

 public:
  double probability(vector<int> assignments, int ids) {
    az.assign(all(assignments)); azn=sz(az); iz = ids;

    int total = 0; tr(az,it) total += *it; if (total > iz) return 0.0;
    tz = total;

    double r1 = memory(0,0,1), r2 = no_memory();
    return abs(r1 - r2);
  }
};
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100205

2010-01-17

過去問マラソン(#11):SRM153

| 12:05 | 過去問マラソン(#11):SRM153 - naoya_t@topcoder を含むブックマーク はてなブックマーク - 過去問マラソン(#11):SRM153 - naoya_t@topcoder 過去問マラソン(#11):SRM153 - naoya_t@topcoder のブックマークコメント

戦闘用ローカルマシンにgitを入れたので、SRM152までのコードを昨日gitでcommit&pushしたつもりだったがディレクトリごと消えていた。git操作ミスか?

過去問マラソン的にはここに全部書いてるからまあいいけど、gitスキル的にやばい…

  • *.cppファイルを自分で一括消去してるっぽい。…重複排除しようと思ってgit rmを使ったのを思い出した

TimeMachineが最後にバックアップした1/11の分(※USB足りないのでTimeMachine用1TBHDDは普段は繋いでない)まで覚えててくれました。SRM150の分まで入ってる。TimeMachine++

Easy(250): Inventory

  • 問題読んでも全然頭に入ってこないよー
  • とりあえずコード書いたけどSample Caseの最後のやつが合わない
  • なるほど。有理数演算しないと駄目か。
  • 前に書いたはずのFractionクラスのコードを引っ張り出す
  • これでどうだ
    • 30%ルールに引っかかるお
    • いろいろ削って最小限にしないとダメか
    • テンプレートとか駄目なのかなあ
  • 削った。submit
  • failed system test
    • なに!
    • sales[i]==0 || daysAvailable[i]==0 ってdaysAvailableだけ見ればいいか
    • submit#2
    • failed system test (again)
    • あ、わかった。Fraction<int>では精度が足りない。long longにしよう
    • submit#3
    • passed system test
#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)

typedef long long T;

T gcd(T m, T n)
{
  if (m == 0 || n == 0) return 0;
  if (m == 1 || n == 1) return 1;
  if (m == n) return m;
  while (1) {
    if (m == 0) return n;
    if (n == 0) return m;
    if (m > n) m %= n; else n %= m;
  }
}

class Fraction {
  T numer, denom;

public:
  Fraction(){ init(0,1); }
  Fraction(T n, T d=1){ init(n,d); }
  Fraction(const Fraction& other){ init(other); }

  Fraction& init(T n, T d); // impl.below
  Fraction& init(const Fraction& other); // impl.below

  double value() {
    if (numer == 0) return 0;
    if (denom == 1) return (double)numer;
    return (double)numer / denom;
  }

  Fraction& operator+=(const Fraction& other); // impl.below
  Fraction& operator/=(T n){ return init(numer, denom*n); }
};

Fraction& Fraction::init(T n, T d)
{
  if (d < 0) n=-n, d=-d;
  if (n==0) {
    numer = 0, denom = 1;
  } else {
    T g = gcd(n,d);
    numer = n / g, denom = d / g;
  }
  return *this;
}
Fraction& Fraction::init(const Fraction& other){
  numer = other.numer, denom = other.denom;
  return *this;
}
Fraction& Fraction::operator+=(const Fraction& other)
{
  T g = gcd(denom, other.denom), l=denom/g*other.denom;// l=denomm*other.denom/gcd
  T n = numer*(other.denom/g) + other.numer*(denom/g);
  return init(n,l);
}

//
class Inventory {
 public:
  int monthlyOrder(vector <int> sales, vector <int> daysAvailable) {
    int n=sz(sales), d=0;
    Fraction sum;
    rep(i,n) {
      //if (sales[i]==0 || daysAvailable[i]==0) continue;
      if (daysAvailable[i]==0) continue;

      Fraction expected(sales[i]*30, daysAvailable[i]);
      sum += expected;
      d++;
    }
    sum /= d;
    return (int)ceil( sum.value() );
  }
};

Medium(450):

Easyで時間かけすぎたので後で

Hard(1000):

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100117

2010-01-15

過去問マラソン(#10):SRM152

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

過去問マラソン10回目。

  • (いまさらですが)listとかstackとかも使うようになった
  • (いまさらですが)vector<char>とstringの相互変換とか
  • (いまさらですが)assignが使いこなせるようになった
  • cpprefがすごく便利なのでボウズラボに足を向けて寝られない

Easy(250): LeaguePicks

  • 問題文の意味がいまいち分からない
  • だが解く
    • Sample Caseが通るように修正していく感じ
    • 不安なのでテストケースを追加
  • 218.14pt (11'11'')
    • passed system test
  • 問題読めてないのに通るのはあまり楽しくない
#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()

class LeaguePicks {
 public:
  vector <int> returnPicks(int position, int friends, int picks) {
    vector<int> res;
    for(int q=0;;){
      int next = q+position;
      if (next>picks) break;
      res.pb(next);
      q+=friends;

      next = q+(friends+1-position);
      if (next>picks) break;
      res.pb(next);
      q+=friends;
    }
    return res;
  }
};

Medium(500): QuiningTopCoder

  • Unefungeな言語で書かれたプログラムソースが与えられ、これがQuineになってるかを調べる。
  • とりあえずエミュレータ書いて
  • 80000サイクルでQuineな出力が得られない場合はTIMEOUT判定
    • 環境(IP,D,stack)をメモ化してみたりとか
  • 1投目: failed
    • 環境とっとくなら出力文字列も保存しないと駄目だ
  • 2投目: failed
    • ":"1文字のコードでメモ化が破綻する。メモ化やめてみてもいい?...別に80000サイクル回してもTLEにならないっぽいし
  • 3投目: passed
#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()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e)  ((s).find(e)!=(s).end())

// BEGIN CUT HERE
void dump_stack(stack<int> st){
  int n = st.size();
  vector<int> vec(n);
  rep(i,n) {
    vec[i] = st.top(); st.pop();
  }
  reverse(all(vec));
  rep(i,n) st.push(vec[i]);
  cout << vec << endl;
}
// END CUT HERE

class UnefungeEmulator {
 private:
  string code; int N;
  int IP, D, cycles;
  stack<int> st;
  stringstream output;
  bool error; string errormsg;

  //set<pair<pair<int,string>,pair<int,stack<int> > > > known;
  
 public:
  UnefungeEmulator(string source) {
    code = source; N = source.size();
    IP = 0;
    D = 1;
    cycles = 0;
    error = false; errormsg = "";
    //known.clear();
  }

  void push(int x) {
    if (x < -1000000000 || 1000000000 < x) {
      error = true;
      errormsg = "OVERFLOW";
      return;
    }
    st.push(x);
  }
  int pop(){
    if (st.empty()) return 0;
    int x = st.top(); st.pop();
    return x;
  }

  void run(){
    while (1) {
      if (error) break;

      string ostr = output.str();
      if (ostr.length() > 0) {
        if (ostr.length() == code.length()) {
          if (ostr == code) break; // QUINE
          else {
            error = true;
            errormsg  = "MISMATCH";
            break;
          }
        }
        if (ostr != code.substr(0,ostr.length())) {
          error = true;
          errormsg  = "MISMATCH";
          break;
        }
      }

      /*
      pair<pair<int,string>,pair<int,stack<int> > > key =
          make_pair(make_pair(IP,ostr), make_pair(D, st) );
      if (found(known,key)) {
        cycles = 80001;
        return;
      }
      known.insert(key);
      */
      
      int D_for_this_cycle = D;
      cycles++; if (cycles > 80000) break;

      switch (code[IP]){
        case '0': case '1': case '2': case '3': case '4':
        case '5': case '6': case '7': case '8': case '9':
          {
            push( code[IP] - '0' );
          }
          break;
        case '$':
          {
            pop();
          }
          break;
        case ':':
          {
            int x = pop();
            push(x); push(x);
          }
          break;
        case 'W':
          {
            int a = pop(), b = pop();
            push(a); push(b);
          }
          break;
        case ',':
          {
            int x = pop();
            char p = code[ abs(x) % N ];
            output << p;
          }
          break;
        case '+':
          {
            int a = pop(), b = pop();
            push( a + b );
          }
          break;
        case '-':
          {
            int a = pop(), b = pop();
            push( a - b );
          }
          break;
        case '#':
          {
            D_for_this_cycle *= 2;
          }
          break;
        case 'R':
          {
            D_for_this_cycle = D = -D;
          }
          break;
        case 'S':
          {
            int x = pop();
            push( x > 0 ? 1 : -1 );
          }
          break;
        case '_':
          {
            int x = pop();
            D_for_this_cycle = D = x % N; // ここの D_for_this_cycle = を忘れてて結果が合わず延々と悩んだ
          }
          break;
        case 'J': // jump
          {
            int x = pop();
            IP = abs(x) % N;
            continue;
          }
          break;
        case '@': // stops the program
          return;
        default: // illegal
          printf("ILLEGAL OP %c\n", code[IP]);
          break;
      }
      IP = (3 * N + IP + D_for_this_cycle) % N;
    }
    // next
  }

  string result(){
    if (cycles > 80000) return "TIMEOUT";
    
    stringstream msg;
    if (error) {
      msg << errormsg;
    } else if (output.str() == code) {
      msg << "QUINES";
    } else {
      msg << "BADEND";
    }
    msg << " " << (cycles - 1);
    return msg.str();
  }
  
};

class QuiningTopCoder {
 public:
  string testCode(string source) {
    UnefungeEmulator emulator(source);
    emulator.run();
    return emulator.result();
  }
};

Hard(1000):

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100115