今更ながらTopCoder SRM507 Div1参加日記

TopCoderのSRM507に参加してきました。

Easy
Passed System Test 182.37

サイコロがある。
６つ以上の要素を持った色の配列が与えられるので、隣接する面が同じ色にならないように塗り分けられればYES、無理ならばNOを出力せよ。
要素は重複して与えられることもある。

解答
違う色が6色与えられればYES、サイコロの性質を考えれば分かることだが、同じ色でも反対側に塗れば問題ないため、同じ色は2回までなら違う色としてカウントしても良い。

提出コード

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <time.h>
using namespace std;

#define REP(i,s,e) for (int i = int(s); i != int(e); i++)
#define rep(i,e) REP(i,0,e)
#define foreach(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
#define MIN 1<<31
#define MAX 1<<30

class CubeStickers {
public:
   string isPossible( vector <string> sticker ) {
   int n = (int)sticker.size();
   map<string,int> colors;
   map<string,int>::iterator iter;
   rep(i,n){
if( (iter = colors.find(sticker[i])) != colors.end()) iter->second = 2; else colors.insert(pair<string,int>(sticker[i], 1));
   }
   int ans = 0;
   for(iter = colors.begin();iter != colors.end();iter++) ans += iter->second;
   return (ans > 5)? "YES":"NO";

   }
};

Medium
Challenge Succeeded 0

Ns個の1*1*1立方体と、Nb個のL*L*L立方体がある。
これらをまとめて一つの大きい立方体の中に入れたい。
最小になるような立方体の体積を求めよ。

L*L*Lの立方体をひたすら縦に積み上げていく方法(一次元解法)と、ひたすら三次元に拡大していく方法(三次元解法)を試したのですが、あっけなくChallenge Succeded。

修正して提出したコード(りんごさんのコードの丸パクリ)

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <time.h>

using namespace std;>

#define REP(i,s,e) for (int i = int(s); i != int(e); i++)
#define rep(i,e) REP(i,0,e)
#define foreach(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
#define ll long long
#define INF 1<<30

class CubePacking {
public:
   int getMinimumVolume( int Ns, int Nb, int L ) {
   ll D=L,ss=Ns,bb=Nb,tmp,c,minimum=D*D*D*bb+ss,ans=INT_MAX,M=INT_MAX;
   for(ll a=L;a*a*a<=M;a++) for(ll b=L;a*b*b<=M;b++){
   tmp = (a/D) * (b/D);
   c=((bb+tmp-1)/tmp)*D;
   ll vol=a*b*c;
   ll in=a*b;
   if(minimum>vol) c+=((minimum-vol)+in-1)/in;
   ans=min(a*b*c,ans);
   }
   return (int)ans;
  }
};