2009-05-23
SRM234 Div1 Medium: WeirdRocks
Algorithm Tutorials: How To Find a Solution (by Dumitru) より。
Backtrackingで解く例（その３）。650点問題。
- とりあえず書いてみた
- 問題文の４つのTest Caseは全部通る
- 302.04points (42'45''), Failed System Test
- 最大ケース（8行10列）で落ちる...というか帰って来ないし
#define rep_(var,n) for(int var=-1;var<(n);var++)
string join(vector<string> strs, const string &delim="")
{
int n=strs.size(); if (n==0) return "";
stringstream ss;
ss << strs[0];
for(int i=1;i<n;i++) { ss << delim << strs[i]; }
return ss.str();
}
class WeirdRooks {
public:
string describe(vector<int> cols) {
set<pair<int,int> > ans;
int R=sz(cols); //1-8
int W=*max_element(all(cols));
int M=0; rep(i,R) M+=cols[i];
set<pair<int,vector<int> > > pat;
int k=0;
vector<int> m(W,-1);
rep_(i0,cols[0]){
if(i0>=0){
k++; m[i0]=0;
}
if(R>=2) rep_(i1,cols[1]){
if(i1>=0){
if(m[i1]>=0) continue;
k++; m[i1]=1;
}
if(R>=3) rep_(i2,cols[2]){
if(i2>=0){
if(m[i2]>=0) continue;
k++; m[i2]=2;
}
if(R>=4) rep_(i3,cols[3]){
if(i3>=0){
if(m[i3]>=0) continue;
k++; m[i3]=3;
}
if(R>=5) rep_(i4,cols[4]){
if(i4>=0){
if(m[i4]>=0) continue;
k++; m[i4]=4;
}
if(R>=6) rep_(i5,cols[5]){
if(i5>=0){
if(m[i5]>=0) continue;
k++; m[i5]=5;
}
if(R>=7) rep_(i6,cols[6]){
if(i6>=0){
if(m[i6]>=0) continue;
k++; m[i6]=6;
}
if(R==8) rep_(i7,cols[7]){
if(i7>=0){
if(m[i7]>=0) continue;
k++; m[i7]=7;
}
if(R==8) pat.insert(make_pair(k,m));
if(i7>=0){ k--; m[i7]=-1; }
}//7
if(R==7) pat.insert(make_pair(k,m));
if(i6>=0){ k--; m[i6]=-1; }
}//6
if (R==6) pat.insert(make_pair(k,m));
if(i5>=0){ k--; m[i5]=-1; }
}//5
if (R==5) pat.insert(make_pair(k,m));
if(i4>=0){ k--; m[i4]=-1; }
}//4
if (R==4) pat.insert(make_pair(k,m));
if(i3>=0){ k--; m[i3]=-1; }
}//3
if (R==3) pat.insert(make_pair(k,m));
if(i2>=0){ k--; m[i2]=-1; }
}//2
if (R==2) pat.insert(make_pair(k,m));
if(i1>=0){ k--; m[i1]=-1; }
}//1
if (R==1) pat.insert(make_pair(k,m));
if(i0>=0){ k--; m[i0]=-1; }
}//0
tr(pat,it){
int k=it->first;
vector<int> m=it->second;
vector<vector<bool> > sp(R,vector<bool>(W,false));
rep(r,R) rep(c,cols[r]) sp[r][c]=true;
rep(c,W){
if(m[c]>=0) { // (c,m[i])
int r=m[c];
for(int j=0;j<=c;j++) sp[r][j]=false;
for(int j=0;j<=r;j++) sp[j][c]=false;
}
}
int sc=0;
rep(r,R) rep(c,cols[r]) if(sp[r][c])sc++;
ans.insert(make_pair(k,sc));
}
vector<string> vs;
tr(ans,it){
char buf[6]; sprintf(buf,"%d,%d",it->first,it->second); vs.pb(buf);
}
return join(vs," ");
}
};
- なんとかしたい。とりあえずパターンをlong longにしてみる
class WeirdRooks {
public:
string describe(vector<int> cols) {
set<pair<int,int> > ans;
int R=sz(cols); //1-8
int W=*max_element(all(cols));
int M=0; rep(i,R) M+=cols[i];
set<ll> pat;
int k=0;
ll m=0LL;
vector<ll> m_(8,0LL);
rep_(i0,cols[0]){
if(i0>=0){
m_[0] = m;
m |= (1LL << (4*i0));
}
if(R>=2) rep_(i1,cols[1]){
if(i1>=0){
if(m & (15LL <<(4*i1))) continue;
m_[1] = m;
m |= (2LL << (4*i1));
}
if(R>=3) rep_(i2,cols[2]){
if(i2>=0){
if(m & (15LL <<(4*i2))) continue;
m_[2] = m;
m |= (3LL << (4*i2));
}
if(R>=4) rep_(i3,cols[3]){
if(i3>=0){
if(m & (15LL <<(4*i3))) continue;
m_[3] = m;
m |= (4LL << (4*i3));
}
if(R>=5) rep_(i4,cols[4]){
if(i4>=0){
if(m & (15LL <<(4*i4))) continue;
m_[4] = m;
m |= (5LL << (4*i4));
}
if(R>=6) rep_(i5,cols[5]){
if(i5>=0){
if(m & (15LL <<(4*i5))) continue;
m_[5] = m;
m |= (6LL << (4*i5));
}
if(R>=7) rep_(i6,cols[6]){
if(i6>=0){
if(m & (15LL <<(4*i6))) continue;
m_[6] = m;
m |= (7LL << (4*i6));
}
if(R==8) rep_(i7,cols[7]){
if(i7>=0){
if(m & (15LL <<(4*i7))) continue;
m_[7] = m;
m |= (8LL << (4*i7));
}
if(R==8) pat.insert(m);
if(i7>=0) m=m_[7];
}//7
if(R==7) pat.insert(m);
if(i6>=0) m=m_[6];
}//6
if (R==6) pat.insert(m);
if(i5>=0) m=m_[5];
}//5
if (R==5) pat.insert(m);
if(i4>=0) m=m_[4];
}//4
if (R==4) pat.insert(m);
if(i3>=0) m=m_[3];
}//3
if (R==3) pat.insert(m);
if(i2>=0) m=m_[2];
}//2
if (R==2) pat.insert(m);
if(i1>=0) m=m_[1];
}//1
if (R==1) pat.insert(m);
if(i0>=0) m=m_[0];
}//0
// cout << "pat.size = " << sz(pat) << endl;
{
vector<int> m(W,-1);
vector<vector<bool> > sp(R,vector<bool>(W,false));
int k=0;
tr(pat,it){
rep(i,W) m[i]=(((*it) >> (4*i)) & 15)-1;
rep(r,R) rep(c,cols[r]) sp[r][c]=true;
k=0;
rep(c,W){
if(m[c]>=0) { // (c,m[i])
k++;
int r=m[c];
for(int j=0;j<=c;j++) sp[r][j]=false;
for(int j=0;j<=r;j++) sp[j][c]=false;
}
}
int sc=0;
rep(r,R) rep(c,cols[r]) if(sp[r][c])sc++;
ans.insert(make_pair(k,sc));
}
}
vector<string> vs;
tr(ans,it){
char buf[6]; sprintf(buf,"%d,%d",it->first,it->second); vs.pb(buf);
}
return join(vs," ");
}
};
最大ケースでも帰ってくるようになったが１分前後かかる。12975561パターンあるのでこんなのでは駄目かと。（とりあえずここまで）
SRM234 Div1 Easy: FractionSplit
- gcd()は自前
- 232.51points (7'54''), Passed system test
- intで足りるのかとか心配したけど大丈夫だったようだ
int gcd(int m, int 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 FractionSplit {
public:
vector<string> getSum(int n, int d) {
vs ans;
for(int x=2;n>0;x++){
// n/d >= 1/x : nx >= d
int nr = n*x - d;
if (nr >= 0){
// n/d - 1/x = (nx-d)/xd
char buf[128];
sprintf(buf,"1/%d",x);
ans.pb(buf);
if(nr==0) break;
int dr = x*d;
int g = gcd(nr,dr);
n = nr / g; d = dr / g;
}
}
return ans;
}
};
コメント
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20090523