Hatena::Grouptopcoder

hotokuの日記@topcoder部 このページをアンテナに追加 RSSフィード

2013-01-23

NinjaTurtles

| 17:41

本番で落としたので、反省の為に晒しておく。

Shut the shut up and write some code. というのは本当にそうだなと。ちょっとサボってただけのつもりだったのに…。久し振りに参加してグングン落ちるレーティングを見て思う。

閑話休題。a-1 < floor(a) <= aを利用して、Nの取りうる範囲を求めてその間をしらみ潰す(下のコードは念の為に広めに取っている)。他の人のを見たらそんな面倒な事はせず[0, 4P]の範囲をしらみ潰している人も居た。

#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>


using namespace std;


class NinjaTurtles{
public:
  int countOpponents(int P, int K){
    for(int N = 3*K*(P-10)/(9+K); N <= 3*K*(P+10)/(9+K); ++N){
      if(3*(N/K) + N/3==P) return N;
    }
    return -1;
  }
};

2012-03-17

Codeforces round 112

| 16:48

  • A,B,C通過
    • 但し、Cは3回も出し直した。。。

SupercentralPoint

方針
  • 全組み合わせについて素直に調べる
コード
#include <iostream>
#include <vector>


using namespace std;


class p{
public:
  int x, y;
  int nb(p& a){
    if(a.x == this->x && a.y > this->y) return 1;
    if(a.x == this->x && a.y < this->y) return 2;
    if(a.x > this->x && a.y == this->y) return 3;
    if(a.x < this->x && a.y == this->y) return 4;
    return 0;
  }
};


int main(int argc, char *argv[]){
  int n;
  cin >> n;
  vector<p> ps(n);
  vector<vector<bool> > b(n, vector<bool>(4, false));
  for(int i = 0; i < n; i++){
    cin >> ps[i].x >> ps[i].y;
  }
  int ret = 0;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      int temp = ps[i].nb(ps[j]);
      if(temp){
	b[i][temp-1] = true;
      }
    }
    if(b[i][0] && b[i][1] && b[i][2] && b[i][3])
      ret++;
  }
  cout << ret << endl;
  return 0;
}


Burning Midnight Oil

「真夜中の燃料を燃やす」というタイトルがツボ

方針
  • 2分探索。2分探索を書いたのは初めてかもしれない。
コード
/*! if g++ -g b.cpp; then ./a.out < b.test; fi
 */

#include <iostream>

using namespace std;


typedef unsigned long long ull;

bool ok(ull n, int k, ull v){
  ull done, work;
  work = v;
  done = 0;
  while(work > 0){
    done += work;
    work /= k;
  }
  return done >= n;
}

int main(int argc, char *argv[]){
  ull n;
  int k;
  cin >> n >> k;

  if(n == 1){
    cout << 1 << endl;
    return 0;
  }

  ull m, M, mid;
  m = 0;
  M = n;
  while(M-m > 1){
    mid = (M+m) / 2; // notice!!
    if(ok(n, k, mid)){
      M = mid;
    }
    else{
      m = mid;
    }
  }
  cout << M << endl;
  return 0;
}


Another Probrem of Strings

3回も提出しなおした。結果、継ぎ接ぎだらけのコードに。。。codeforcesは毎回コーナーケースに泣かされる。。。

ポイント
  • '1' が出る場所を調べてposに入れる
  • pos[i] ... pos[i+k-1]の場所にある'1'を含む部分列の数は、「(pos[i]の左にある連続した'0'の数+1) x (pos[i+k-1]の右にある連続した'0'の数+1)」。

が基本方針だけど、

  • ('1'の数) < kの場合
  • k=0の場合
  • k=0でさらに('1'の数)=0の場合

等に引っ掛かったので通るまで修正したら継ぎ接ぎだらけのコードに。。。

/*! if g++ -g c.cpp; then ./a.out < c.test; fi
 */

#include <iostream>
#include <vector>
#include <string>


using namespace std;
typedef unsigned long long ull;
//typedef int64 ull;

ull f(ull n){
  return (n+1)*n/2;
}

int main(int argc, char *argv[]){
  ull k; string buf;
  cin >> k >> buf;
  vector<ull> pos(0);
  for(ull i = 0; i < buf.size(); i++){
    if(buf[i] == '1'){
      pos.push_back(i);
    }
  }
  if(pos.size() < k){
    cout << 0 << endl;
    return 0;
  }

  ull ret = 0;
  if(k==0){
    if(pos.size()==0){
    //if(false){
      ret = f(buf.size());
    }
    else{
      ret += f(pos[0]);
      for(ull i = 1; i < pos.size(); i++){
	ret += f(pos[i] - pos[i-1] - 1);
      }
      ret += f(buf.size() - pos.back() - 1);
    }
  }
  else{
    for(ull i = 0, j = k; j <= pos.size(); i++, j++){
      ull left, right;
      if(i == 0){
	left = pos[i] + 1;;
      }
      else{
	left = pos[i] - pos[i-1];
      }
      if(j == pos.size()){
	right = buf.size()-pos[j-1];
      }
      else{
	right = pos[j] - pos[j-1];
      }
      ret += left * right;
    }
  }
  cout << ret << endl;
  return 0;
}

2012-03-10

BinaryPolynomialDivTwo

| 18:26


#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>


using namespace std;


class BinaryPolynomialDivTwo{
public:
  vector<int> a_;
  int n;
  int value(int x){
    int ret = 0;
    vector<int> v(n+1, x);
    v[0] = 1;
    for(size_t i = 0; i <= n; ++i){
      ret += v[i] * a_[i];
    }
    return ret % 2;
  }
  int countRoots(vector <int> a){
    a_ = a;
    n = a_.size()-1;
    int ret = 0;
    if(!value(0)) ret++;
    if(!value(1)) ret++;
    return ret;
  }



};





RollingDiceDivTwo

| 18:27

#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>
#include <functional>
#include <numeric>


using namespace std;

int to_int(char c){
  return (int)(c - '0');
}


class RollingDiceDivTwo{
public:
  vector<vector<int> > v;
  int n, m;
  int minimumFaces(vector <string> rolls){
    n = rolls.size();
    m = rolls[0].size();
    v.resize(n);
    vector<int> ret(m, 0);
    for(int i = 0; i < n; i++){
      v[i].resize(m);
      for(int j = 0; j < m; j++){
	v[i][j] = to_int(rolls[i][j]);
      }
      sort(v[i].begin(), v[i].end());
      for(int j = 0; j < m; j++){
	ret[j] = max(ret[j], v[i][j]);
      }
      //copy(v[i].begin(), v[i].end(), ostream_iterator<int>(cout, ",")); cout << endl;
    }
    return accumulate(ret.begin(), ret.end(), 0);
  }



};

SeydibabaSeydibaba2013/02/17 05:56Perfect answer! That raelly gets to the heart of it!

bqytfbxbqytfbx2013/02/19 14:52UfgG5z <a href="http://nngcuhuhwcgq.com/">nngcuhuhwcgq</a>

yvngovyuwblyvngovyuwbl2013/02/19 20:14LtTSYx , [url=http://vsiqvhotsuzm.com/]vsiqvhotsuzm[/url], [link=http://tsbyavzuoqvn.com/]tsbyavzuoqvn[/link], http://ptflmplloqxi.com/