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-10-21

SRM 558 div2 easy Stamp

| 11:01

問題を見た時に、きっとDPで解くんだろうなと思いつつ、結局提出出来なかった。苦手な感じの問題なので、メモを残す。→問題

方針

スタンプを左から押していくDPを考える。DP用の配列として、dp[i][j]を用意。dp[i][j]には、「色iのスタンプをjに押した場合の最小コスト」を保存。ここで、「色iのスタンプをjに押す」とは、色iのスタンプを右端がj番目のマス目に来るように押す事と理解する。

スタンプの長さをLとすると、色iのスタンプをjに押すことが出来るのは、

  • j-L番目に別の色のスタンプを押している場合
  • j-L番目に同じ色のスタンプを押している場合
  • j-L+1番目に同じ色のスタンプを押している場合
  • (途中省略)
  • j-1番目に同じ色のスタンプを押している場合

のどれかなので、dp[i][j]にはこれらの中の最小コスト+pushCostを入れれば良い。

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

int d[100];
int n;
int dp[3][100];
int cost, push;


class Stamp{
public:
  bool check(int c, int pos, int L);
  int do_dp(int L);
  int getMinimumCost(string desiredColor, int stampCost, int pushCost);



};

void debug(){
  for(int i = 0; i < 3; ++i){
    copy(dp[i], dp[i]+n, ostream_iterator<int>(cout, "\t")); cout << endl;
  }
  cout << endl;
}

bool Stamp::check(int c, int pos, int L){
  for(int i = 0; i < L; ++i){
    if(d[pos-i]==c || d[pos-i]==-1) continue;
    else return false;
  }
  return true;
}
int Stamp::do_dp(int L){
  for(int i = 0; i < 3; ++i){
    fill(dp[i], dp[i]+n, 1<<30);
    if(check(i, L-1, L)) dp[i][L-1]=push;
  }
  for(int i = L; i < n; ++i){
    for(int j = 0; j < 3; ++j){
      if(!check(j, i, L)) continue;
      for(int k = 0; k < 3; ++k){
	dp[j][i] = min(dp[k][i-L]+push, dp[j][i]);
      }
      for(int k = 1; k < L; ++k){
	dp[j][i] = min(dp[j][i-k]+push, dp[j][i]);
      }
      // cout << L << endl;
      // debug();
    }
  }
  return min(dp[0][n-1], min(dp[1][n-1], dp[2][n-1]));
}
int Stamp::getMinimumCost(string desiredColor, int stampCost, int pushCost){
  n = desiredColor.size();
  cost = stampCost;
  push = pushCost;
  for(int i = 0; i < n; ++i){
    if(desiredColor[i]=='R')d[i]=0;
    if(desiredColor[i]=='G')d[i]=1;
    if(desiredColor[i]=='B')d[i]=2;
    if(desiredColor[i]=='*')d[i]=-1;
  }
  int ret=INT_MAX;
  for(int i = 1; i<=n; ++i){
    int p = do_dp(i);
    if(p>0)ret=min(stampCost*i+p, ret);
  }
  return ret;
}

2012-10-13

SRM 557

| 15:54

midに時間掛かり過ぎ。殆ど、時間ギリまで使ってしまった。アルゴリズムは単純なので、こういうのをスムーズに提出出来るようにならないとなかなか上に行けない。


easy

#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 GreatFairyWar{
public:
  int minHP(vector <int> dps, vector <int> hp){
    int ret=0;
    size_t n = dps.size();
    for(size_t i = 0; i < n; ++i){
      for(size_t j = i; j < n; ++j){
	ret+=dps[j]*hp[i];
      }
    }
    return ret;
  }



};



// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor


mid IncubatorEasy

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

size_t n;
bool magical[100], proc[100], visit[100];
vector<string> graph;


class IncubatorEasy{
public:
  void dfs(int pos, bool is_proc);
  int count_valid(int flag);
  int maxMagicalGirls(vector <string> love);
};

void IncubatorEasy::dfs(int pos, bool is_proc){
  if(is_proc){
    proc[pos]=true;
  }
  if(visit[pos]) return;
  visit[pos]=true;
  for(size_t i = 0; i < n; ++i){
    if(graph[pos][i]=='Y'){
      dfs(i, true);
    }
  }
}
int IncubatorEasy::count_valid(int flag){
  fill(proc, proc+n, false);
  fill(visit, visit+n, false);
  for(size_t i = 0; i < n; ++i){
    magical[i] = flag & 1<<i;
    if(magical[i]) dfs(i, false);
  }
  int ret=0;
  for(size_t i = 0; i < n; ++i){
    if(magical[i] && !proc[i]){
      ret++;
    }
  }
  // copy(magical, magical+n, ostream_iterator<bool>(cout, ","));
  // cout << ":" << ret << endl;
  return ret;
}
int IncubatorEasy::maxMagicalGirls(vector <string> love){
  n = love.size();
  graph = love;
  int flag=0;
  int ret=0;
  while(flag < 1<<n){
    ret=max(ret, count_valid(flag++));
  }
  return ret;
}

2012-09-08

SRM 555

| 10:25

最初に書いたeasyがテストケースに通らなくて、何で????てなって、慌てちゃって駄目だった。メンタル大事。

easy

system test failed.

    m = board[0].size();

の部分をboard[1]で提出してた…

全列挙

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

vector<vector<int> > c;
int n, m;

class XorBoardDivTwo{
public:
  void debug(){
    for(size_t i = 0; i < n; ++i){
      for(size_t j = 0; j < m; ++j){
	cout << c[i][j];
      }
      cout << endl;
    }
  }
  int num(vector<string> board, int r, int col){
    for(size_t i = 0; i < n; ++i){
      for(size_t j = 0; j < m; ++j){
	c[i][j] = board[i][j]-'0';
	if(r==i) c[i][j] = c[i][j]^1;
	if(col==j) c[i][j] = c[i][j]^1;
      }
    }
    int ret=0;
    for(size_t i = 0; i < n; ++i){
      for(size_t j = 0; j < m; ++j){
	ret+=c[i][j];
      }
    }
    // debug();
    // cout << ret << endl;
    return ret;
  }
  int theMax(vector <string> board){
    n = board.size();
    m = board[0].size();
    c.resize(n, vector<int>(m));
    int ret = -1;
    for(size_t i = 0; i < n; ++i){
      for(size_t j = 0; j < m; ++j){
	ret = max(ret, num(board, i, j));
      }
    }
    return ret;
  }



};



// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor



medium

幅優先探索。幅優先を書いたのは実は初めてだ。

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

queue<pair<string, int> > x;

string v[] = {"1",
	      "101",
	      "11001",
	      "1111101",
	      "1001110001",
	      "110000110101",
	      "11110100001001",
	      "10011000100101101",
	      "1011111010111100001",
	      "111011100110101100101",
	      "100101010000001011111001",
	      "10111010010000111011011101",
	      "1110100011010100101001010001",
	      "1001000110000100111001110010101",
	      "101101011110011000100000111101001",
	      "11100011010111111010100100110001101",
	      "10001110000110111100100110111111000001",
	      "1011000110100010101111000010111011000101",
	      "110111100000101101101011001110100111011001",
	      "100010101100011100100011000001001000100111101",
	      "10101101011110001110101111000101101011000110001",
	      "1101100011010111001001101011011100010111011110101",
	      "1000011110000110011110000011001001101110101011001001",
	      "101010010110100000010110001111110000101001010111101101",
	      "11010011110000100001101111001110110011001110110110100001",
	      "10000100010110010101000101100001010000000001010010000100101",
	      "1010010101101111101001011011100110010000000110011010010111001",
	      "110011101100101110001111001001111111010000100000000011110011101"};


class CuttingBitString{
public:
  int bfs(string s, int k){
    for(size_t i = 0; i < 28; ++i){
      if(v[i]==s){
	return k;
      }
      if(s.size() >= v[i].size() &&
	 s.substr(0, v[i].size())==v[i]){
	x.push(make_pair(s.substr(v[i].size(), 100), k+1));
      }
    }
    return -1;
  }

  int getmin(string S){
    x = queue<pair<string, int> >();
    x.push(make_pair(S, 1));
    int k=-1;
    while(x.size()){
      k = bfs(x.front().first, x.front().second);
      if(k>0) return k;
      x.pop();
    }
    return -1;
  }



};



// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor

MaVadoMaVado2012/11/15 04:57God, I feel like I suhold be takin notes! Great work

aceumolrumaceumolrum2012/11/16 11:148e7OP3 , [url=http://tiujxmzupahs.com/]tiujxmzupahs[/url], [link=http://qxybcgqfzxvc.com/]qxybcgqfzxvc[/link], http://vaskdacsjgum.com/

ujndyxhamujndyxham2012/11/17 11:54igiTue <a href="http://adlcoeifsfqs.com/">adlcoeifsfqs</a>

ndxwedtubndxwedtub2012/11/17 21:30onU0bu , [url=http://rhcyzrovgklm.com/]rhcyzrovgklm[/url], [link=http://fzggvjadkdvm.com/]fzggvjadkdvm[/link], http://sgafbvxrtbgo.com/

2012-09-02

SRM 554

| 11:17

今回は、easy, mediumをサクッと片付けられたので、初の3完か!と色めき立ったけど、結局出せず。部屋で誰も出せてなかったので、結構難しかったのかな。。。。

easy TheBrickTowerEasyDivTwo

1個ずつ積んで、高さをsetに突っ込む。酷いコピペコードだ。

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

set<int> s;

class TheBrickTowerEasyDivTwo{
public:
  int find(int redCount, int redHeight, int blueCount, int blueHeight){
    s.clear();
    {
      int nr=redCount;
      int nb=blueCount;
      bool red=true;
      int sum=0;
      while(nr>0 && nb>0){
	if(red){
	  nr--;
	  sum+=redHeight;
	}
	else{
	  nb--;
	  sum+=blueHeight;
	}
	red=!red;
	s.insert(sum);
      }
      if(red && nr>0){
	sum+=redHeight;
	s.insert(sum);
      }
      if(!red && nb>0){
	sum+=blueHeight;
	s.insert(sum);
      }
    }
    {
      int nr=redCount;
      int nb=blueCount;
      bool red=false;
      int sum=0;
      while(nr>0 && nb>0){
	if(red){
	  nr--;
	  sum+=redHeight;
	}
	else{
	  nb--;
	  sum+=blueHeight;
	}
	red=!red;
	s.insert(sum);
      }
      if(red && nr>0){
	sum+=redHeight;
	s.insert(sum);
      }
      if(!red && nb>0){
	sum+=blueHeight;
	s.insert(sum);
      }
    }
    return s.size();
  }



};



// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor

こんな感じで、再帰で書くのがシンプルに書けて良い感じらしい。

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

set<int> s;

class TheBrickTowerEasyDivTwo{
public:
  void red(int r, int b, int h){
    if(r==0) return;
    r--;
    h+=rh;
    s.insert(h);
    blue(r,b,h);
  }
  void blue(int r, int b, int h){
    if(b==0) return;
    b--;
    h+=bh;
    s.insert(h);
    red(r,b,h);
  }
  int find(int redCount, int redHeight, int blueCount, int blueHeight){
    s.clear();
    rh=redHeight;
    bh=blueHeight;
    red(redCount, blueCount, 0);
    blue(redCount, blueCount, 0);
    return s.size();
  }
};



// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor


medium TheBrickTowerMediumDivTwo

順列を全列挙して調べ挙げる。next_permutationというstl関数があるのを初めて知った。

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


vector<bool> flag;
vector<int> perm;
int n;
int m;
vector<int> ans;
vector<int> h;

class TheBrickTowerMediumDivTwo{
public:
  void check(){
    int sum = 0;
    for(int i = 0; i < n-1; i++){
      sum += max(h[perm[i]], h[perm[i+1]]);
    }
    if(sum < m){
      m = sum;
      ans = perm;
    }
  }
  void dfs(int depth){
    for(int j = 0; j < n; j++){
      if(depth == n){
	// copy(perm.begin(), perm.end(), ostream_iterator<int>(cout, ","));
	// cout << endl;
	check();
	return;
      }
      if(flag[j]){
	flag[j] = false;
	perm[depth] = j;
	dfs(depth+1);
	flag[j] = true;
      }
    }
  }
  vector <int> find(vector <int> heights){
    n = heights.size();
    flag.clear(); flag.resize(n, true);
    perm.clear(); perm.resize(n);
    h = heights;
    m = INT_MAX;
    dfs(0);
    return ans;
  }
};



// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor

LamlakLamlak2012/11/14 21:46Nunquam dormio пишет...Да ничего ужасного в них нет. Просто с ними редко приходится работать и синтаксис у программиста вылетает из головы. Если руку набить, то работать с ними становится легко и приятно.Собсвенно мне приходилось писать под платформу, на которой был только C компилятор(причём результат компиляции выполнялся на виртуальной машине). А хотелось с минимальными усилиями перенести туда кучу кода на C++. И для этой платформы я разрабатывал фрэймворк, использующий что-то вроде классов с наследовнием и виртуальными функциями. Вся система была достаточно сильно завязана на указатели на функции. Работать с ними было действительно легко, но почему-то хотелось лучшего.

MasatoshiMasatoshi2012/11/16 17:31Thanks for introducing a ltitle rationality into this debate.

mfejmkmkrtjmfejmkmkrtj2012/11/16 22:40SI7RT7 <a href="http://riltsdnktpce.com/">riltsdnktpce</a>

chfexptchfexpt2012/11/18 20:062Tx7XX <a href="http://xwgcvxszafet.com/">xwgcvxszafet</a>

ahnixgiahnixgi2012/11/19 09:20So7FuV , [url=http://xgdejbnsovrl.com/]xgdejbnsovrl[/url], [link=http://lqfpsssdaadf.com/]lqfpsssdaadf[/link], http://zwluvnuzugrz.com/