Hatena::Grouptopcoder

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

 | 

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/

 |