2009-05-22
SRM148 Div1 Medium: MNS
Algorithm Tutorials: How To Find a Solution (by Dumitru) より。
Backtrackingで解く例（その２）。450点問題。
- C++のBacktrackingに慣れてきた
- 最初数字がぜんぜん合わないと思ったら３列目しかpermutationしてなかったorz
- Test Caseが４つ通ったので投げてみた
- 325.10points (19'13''), Passed system test
- わーい
class MNS {
public:
int combos(vector<int> ns) {
set<vector<int> > ans;
int sum=0;
rep(i,9) sum+=ns[i];
if(sum%3) return 0;
sort(all(ns));
int rowsum=sum/3;
for(int i=0;i<7;i++){
for(int j=i+1;j<8;j++){
for(int k=j+1;k<9;k++){
vector<int> as(3); as[0]=ns[i]; as[1]=ns[j]; as[2]=ns[k];
if (as[0]+as[1]+as[2] == rowsum) {
ns.erase(ns.begin()+k);
ns.erase(ns.begin()+j);
ns.erase(ns.begin()+i);
for(int u=0;u<4;u++){
for(int v=u+1;v<5;v++){
for(int w=v+1;w<6;w++){
vector<int> bs(3); bs[0]=ns[u]; bs[1]=ns[v]; bs[2]=ns[w];
if (bs[0]+bs[1]+bs[2] == rowsum) {
ns.erase(ns.begin()+w);
ns.erase(ns.begin()+v);
ns.erase(ns.begin()+u);
do {
do {
do {
if ( (as[0]+bs[0]+ns[0] == rowsum)
&& (as[1]+bs[1]+ns[1] == rowsum)
&& (as[2]+bs[2]+ns[2] == rowsum) ) {
int a_[9] = { as[0],as[1],as[2], bs[0],bs[1],bs[2], ns[0],ns[1],ns[2] };
vector<int> a(a_, a_+sizeof(a_)/sizeof(*a_));
ans.insert(a);
}
} while (next_permutation(all(ns)));
} while (next_permutation(all(bs)));
} while (next_permutation(all(as)));
ns.pb(bs[0]); ns.pb(bs[1]); ns.pb(bs[2]);
sort(all(ns));
}
}
}
}
ns.pb(as[0]); ns.pb(as[1]); ns.pb(as[2]);
sort(all(ns));
}
}
}
}
return sz(ans);
}
};
SRM148 Div1 Easy: CircleGame
- やるだけ
- なのにeraseで迷う
- 213.37 (12'12''), passed system test
- 遅いっす
class CircleGame {
public:
int cardsLeft(string deck) {
vector<int> dk;
rep(i,sz(deck)){
switch(deck[i]){
case 'K': break;
case 'A': dk.pb(1); break;
case 'T': dk.pb(10); break;
case 'J': dk.pb(11); break;
case 'Q': dk.pb(12); break;
default: dk.pb(deck[i]-'0'); break;
}
}
int l=sz(dk),ll=l+1;
while(l<ll){
rep(i,l){
if(dk[i]+dk[(i+1)%l]==13) {
if (i+1==l) {
dk.erase(dk.begin()+i);
dk.erase(dk.begin());
break;
} else {
dk.erase(dk.begin()+i+1);
dk.erase(dk.begin()+i);
break;
}
}
}
ll=l;
l=sz(dk);
}
return l;
}
};
SRM146 Div2 Hard: BridgeCrossing
Algorithm Tutorials: How To Find a Solution (by Dumitru) より。Backtrackingで解く例。
- backtrackingってC++でどう書けばよいのか
- call/ccとかじゃなくて
- ...
- とりあえず解いてみる
- 672.98points (22'12''), passed system test
class BridgeCrossing {
public:
int minTime(vector <int> times) {
int m=sz(times);
int fl=(1<<(m+1))-1;
int lt=1<<m;
vector<int> tm(lt);
rep(i,lt){
int t=0;
for(int j=0,k=1;j<m;j++,k<<=1){
if(i & k) t >?= times[j];
}
tm[i] = t;
}
priority_queue<ii> pq;
pq.push(make_pair(0,0));
vector<int> d(fl+1,INT_MAX); d[0]=0;
while(!pq.empty()){
ii t=pq.top(); pq.pop();
int sc=-t.first, z=t.second;
if(z==fl) return sc;
if(z & lt){
// あっちから
for(int i=1;i<lt;i++){
if((i&z) < i) continue;
int popc=__builtin_popcount(i);
if(popc==1 || popc==2){
int newz=z-lt-i;
int newsc=sc+tm[i];
if(d[newz]>newsc){ d[newz]=newsc; pq.push(make_pair(-newsc,newz)); }
}
}
} else {
// こっちから
for(int i=1;i<lt;i++){
if((i&z) > 0) continue;
int popc=__builtin_popcount(i);
if(popc==1 || popc==2){
int newz=z+lt+i;
int newsc=sc+tm[i];
if(d[newz]>newsc){ d[newz]=newsc; pq.push(make_pair(-newsc,newz)); }
}
}
}
}
return -1;
}
};
Test Case #0...PASSED (0.377 msec)
Test Case #1...PASSED (0.19 msec)
Test Case #2...PASSED (0.021 msec)
Test Case #3...PASSED (0.46 msec)
- Tutorialにあるように、行きは２人（そもそも１人しかいない場合はその１人の所要時間が答え）で、帰りは向こう岸にいる中で一番早いのを返せばよいのでもう少し簡略化可能
typedef pair<int,int> ii;
class BridgeCrossing {
public:
int minTime(vector <int> times) {
int m=sz(times);
if (m==1) return times[0]; // 1人ならそいつの所要時間が答え
sort(all(times));
int fl=(1<<(m+1))-1;
int lt=1<<m;
vector<int> tm(lt);
rep(i,lt){
int t=0;
for(int j=0,k=1;j<m;j++,k<<=1){
if(i & k) t >?= times[j];
}
tm[i] = t;
}
priority_queue<ii> pq;
pq.push(make_pair(0,0));
vector<int> d(fl+1,INT_MAX); d[0]=0;
while(!pq.empty()){
ii t=pq.top(); pq.pop();
int sc=-t.first, z=t.second;
if(z==fl) return sc;
if(z & lt){
// あっちから
for(int i=1;i<lt;i++){
if((i&z) < i) continue;
int popc=__builtin_popcount(i);
// いちばん速いやつを１人戻せばよい
if(popc==1){
int newz=z-lt-i;
int newsc=sc+tm[i];
if(d[newz]>newsc){ d[newz]=newsc; pq.push(make_pair(-newsc,newz)); }
break;
}
}
} else {
// こっちから
for(int i=1;i<lt;i++){
if((i&z) > 0) continue;
int popc=__builtin_popcount(i);
// こちらからは２人行ったほうがよい。というか１人で行く理由はない
if(popc==2){
int newz=z+lt+i;
int newsc=sc+tm[i];
if(d[newz]>newsc){ d[newz]=newsc; pq.push(make_pair(-newsc,newz)); }
}
}
}
}
return -1;
}
};
Test Case #0...PASSED (0.314 msec)
Test Case #1...PASSED (0.096 msec)
Test Case #2...PASSED (0.005 msec)
Test Case #3...PASSED (0.192 msec)
class BridgeCrossing {
int sub(vector<int> &here, vector<int> &there, int cur){
int l=sz(here);
priority_queue<int> pq;
for(int i=0;i<l-1;i++){
for(int j=i+1;j<l;j++){
int a=here[i], b=here[j];
// >(a,b)>
remove_(here,a); there.pb(a);
remove_(here,b); there.pb(b);
if(l==2) {
pq.push(-(cur+max(a,b)));
} else {
sort(all(there));
int c=there[0];
// <c<
remove_(there,c); here.pb(c);
sort(all(here)); sort(all(there));
pq.push(-sub(here,there,cur+max(a,b)+c));
// backtracking: >c>
remove_(here,c); there.pb(c);
}
// backtracking: <(a,b)<
remove_(there,a); here.pb(a);
remove_(there,b); here.pb(b);
sort(all(here)); sort(all(there));
}
}
return -pq.top();
}
public:
int minTime(vector <int> times) {
int m=sz(times);
if (m==1) return times[0];
vector<int> here(all(times)), there;
return sub(here,there,0);
}
};
Test Case #0...PASSED (0.376 msec)
Test Case #1...PASSED (1.717 msec)
Test Case #2...PASSED (0.004 msec)
Test Case #3...PASSED (26.03 msec)
- ああ、こういう風に変更を元に戻すコードを自分で書いて次に進むスタイルは見た事がある
- これがC++のバックトラッキングか（気づくの遅すぎ）
SRM232 Div1 Easy: WordFind
Algorithm Tutorials: How To Find a Solution (by Dumitru) より。Brute Forceで解く例（その４）。
- 223.81points →縦・横・斜めのうち最初に見つけたやつを返してたのでfailed system test
- 縦・横・斜めまでちゃんと調べてからソート。passed system test
- 問題文の例が通ったからと言って油断しないこと
class WordFind {
string str(int y, int x){
stringstream ss;
ss << y << " " << x;
return ss.str();
}
public:
vector <string> findWords(vector <string> grid, vector <string> wordList) {
int gw=sz(grid[0]),gh=sz(grid);
int n=sz(wordList);
vs ans(n,"");
rep(i,n){
vector<pair<int,int> > buf;
string w=wordList[i]; char w0=w[0]; int l=sz(w);
// yoko
for(int y=0;y<gh;y++){
for(int x=0;x<=gw-l;x++){
if(grid[y][x]!=w0) goto fail1;
for(int z=1;z<l;z++){
if(grid[y][x+z]!=w[z]) goto fail1;
}
buf.pb(make_pair(y,x));
goto cont1;
fail1:;
}
}
cont1:
// tate
for(int y=0;y<=gh-l;y++){
for(int x=0;x<gw;x++){
if(grid[y][x]!=w0) goto fail2;
for(int z=1;z<l;z++){
if(grid[y+z][x]!=w[z]) goto fail2;
}
buf.pb(make_pair(y,x));
goto cont2;
fail2:;
}
}
cont2:
// naname
for(int y=0;y<=gh-l;y++){
for(int x=0;x<=gw-l;x++){
if(grid[y][x]!=w0) goto fail3;
for(int z=1;z<l;z++){
if(grid[y+z][x+z]!=w[z]) goto fail3;
}
buf.pb(make_pair(y,x));
goto cont3;
fail3:;
}
}
cont3:
sort(all(buf));
if (sz(buf) > 0) ans[i] = str(buf[0].first, buf[0].second);
}
return ans;
}
};
SRM229 Div1 Easy: Cafeteria
Algorithm Tutorials: How To Find a Solution (by Dumitru) より。Brute Forceで解く例（その３）。
- 数があわないと思ったら、いちばん速いバス停を求めていたorz
- 直した
- 210.60points (12'47''), Passed System Test
- なんか遅いなあ＞自分
class Cafeteria {
string twelve(int min){
int h=min/60, m=min%60;
if (h>12) h-=12;
char buf[6];
sprintf(buf,"%02d:%02d",h,m);
return buf;
}
public:
string latestTime(vector <int> offset, vector <int> walkingTime, vector <int> drivingTime) {
int n=sz(offset);
int lim=60*14+30;
int latest=0;
rep(i,n){
int o=offset[i],// 0-9
wt=walkingTime[i],//1-30
dt=drivingTime[i];//1-300
int lastdep=lim-dt, lastdepo=lastdep%10, lastdep0 = lastdep-lastdepo;
int busdep= (o<=lastdepo)? (lastdep0+o) : (lastdep0-10+o);
int dep=busdep-wt;
latest >?= dep;
}
return twelve(latest);
}
};
SRM212 Div2 Hard: LargestCircle
Algorithm Tutorials: How To Find a Solution (by Dumitru) より。Brute Forceで解く例（その２）。
- とりうる中心＆半径について全て試してみた
- 普通にコンパイルするとTest Case #6で2.6秒かかったが、-O3 で161msec。余裕
- 718.97points (19'25''), Passed System Test
class LargestCircle {
int in(int x,int y,int r, int u,int v){
return (u-x)*(u-x) + (v-y)*(v-y) - r*r;
}
public:
int radius(vector<string> grid) {
int h=sz(grid), w=sz(grid[0]);
if (h==1 || w==1) return 0;
int R = 0;
for(int x=1;x<=w-1;x++){
int dxmax=min(x,w-x);
for(int y=1;y<=h-1;y++){
int dymax=min(y,h-y);
int rmax=min(dxmax,dymax);
for(int r=rmax;r>=1;r--){
bool ok=true;
for(int u=0;u<w;u++){
for(int v=0;v<h;v++){
if(grid[v][u]=='#'){
int a = in(x,y,r, u,v);
int b = in(x,y,r, u+1,v);
int c = in(x,y,r, u,v+1);
int d = in(x,y,r, u+1,v+1);
if ((a>=0 && b>=0 && c>=0 && d>=0) || (a<=0 && b<=0 && c<=0 && d<=0)) {
} else {
ok=false; goto out;
}
}
}
}
out:
if (ok) R>?=r; // ←コンパイル時にwarning出るね
}
}
}
return R;
}
};
- >?= なのか <?= なのかぱっと分からないので両方試したのは内緒。
- コンパイル時にwarning出るが構わない
LargestCircle.cpp: In member function ‘int LargestCircle::radius(std::vector<std::string, std::allocator<std::string> >)’:
LargestCircle.cpp:75: warning: minimum/maximum operators are deprecated
SRM197 Div1 Easy: GeneralChess
Algorithm Tutorials: How To Find a Solution (by Dumitru) より。Brute Forceで解く例。
- まあやるだけですが
- knightの動ける位置とかコピペで行けるようにしておくべきだ
- 197.98points (15'25'') 時間かけすぎ
- Passed System Test
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<string> vs;
typedef vector<long long> vll;
typedef pair<int,int> ii;
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n) for(int var=0;var<(n);var++)
#define found(s,e) ((s).find(e)!=(s).end())
// split(), map_atoi() は自作
int knight[8][2] = { {-2,-1}, {-2,1}, {-1,-2}, {-1,2}, {1,-2}, {1,2}, {2,-1}, {2,1} };
class GeneralChess {
public:
vector <string> attackPositions(vector <string> pieces) {
int n=sz(pieces);
map<ii,int> m;
rep(i,n){
vi xy = map_atoi(split(pieces[i],','));
rep(j,8){
ii xy_ = make_pair(xy[0] + knight[j][0],
xy[1] + knight[j][1]);
if (found(m,xy_)) m[xy_]++;
else m[xy_]=1;
}
}
vector<ii> v;
tr(m,it){
if(it->second==n) v.pb(it->first);
}
sort(all(v));
vector<string> ans;
tr(v,it){
char buf[14];
sprintf(buf,"%d,%d", it->first, it->second);
ans.pb(buf);
}
return ans;
}
};
コメント
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20090522