SRM diary(Sigmar)

SRM530 Div1 250 GogoXCake

SRM530, Div1 | 02:26 |

Problem Statement

解答方針

一番上の列の一番左のマスは、カッターの一番上の一番左に当てはめないとダメに決まっているので左上からGreedyにカッターに当てはめていくだけ

ソースコード

class GogoXCake {
public:
	void examine(vector <string> &cake, vector <string> &cutter, int r, int c) {
		int ch=cutter.size(), cw=cutter[0].size();
		bool ok=true;
		for(int i=0; i<ch; i++) {
			for(int j=0; j<cw; j++) {
				if(!(cutter[i][j]=='X' || cake[r+i][c+j]=='.')) ok=false;
			}
		}
		if(!ok) return;
		for(int i=0; i<ch; i++) {
			for(int j=0; j<cw; j++) {
				if(cutter[i][j]=='.') cake[r+i][c+j]='X';
			}
		}
	}

	string solve(vector <string> cake, vector <string> cutter) {
		int h=cake.size(), w=cake[0].size();
		int ch=cutter.size(), cw=cutter[0].size();
		
		for(int i=0; i+ch<=h; i++) {
			for(int j=0; j+cw<=w; j++) {
				examine(cake, cutter, i, j);
			}
		}
		for(int i=0; i<h; i++) {
			for(int j=0; j<w; j++) {
				if(cake[i][j]=='.') return "NO";
			}
		}
		return "YES";
	}
};

SRM530 Div1 500 GogoXMarisaKirisima

SRM530, Div1 | 02:26 |

Problem Statement

解答方針

とりあえず0からN-1への最短パスを調べる。（これより短いパスはないんだから、全部のエッジを使ってしまってもいいだろう。）

あとは今まで通ったノードを覚えておいて、その中に含まれるノードからノードへのパスを適当に探して新たなパスとして追加する。

これも最短のを取っておけばたぶん大丈夫だろう。

何か最短ばかり頭にあったのでダイクストラの変形を書いてしまった。

よく考えたらコストが全部1だからBFSで十分だった。何やってるんだ・・

提出したらTLE。

通ったパスを求めるための、親を記憶する変数dad[]の値がバグって無限ループしていた。ダイクストラとか詳細を覚えていないライブラリを変形するからだ・・・

直して通った。

Editorial見たら1行で書けるよ、と書いてあった。

そんな解もあるんだな・・・

ソースコード

vector <int> val, dad;
int maxn;
const int INF=1000000000;
int a[52][52];
int used[52][52];

int dijkstra(vector <int> &start, vector <int> &goal) {
	priority_queue <pair <int, int> > pq;
	pair <int, int> qt, qe;
	val.assign(maxn, -INF);
	dad.assign(maxn, -1);
	for(int i=0; i<maxn; i++) {
		if(!start[i]) continue;
		qe=make_pair(0, i);
		pq.push(qe);
		val[i]=0;
		dad[i]=i;
	}
	while(!pq.empty()) {
		qt=pq.top(); pq.pop();
		int &v=qt.second;
		if(val[v]>0) continue;
		val[v]=-val[v];
		for(int nv=0; nv<maxn; nv++) {
			if(used[v][nv]) continue;
			int p=val[v]+a[v][nv];
			if(!goal[nv] && p>=-val[nv]) continue;
			qe=make_pair(-p, nv);
			pq.push(qe);
			val[nv]=-p;
			dad[nv]=v;
			if(goal[nv]) return nv;
		}
	}
	return -1;
}

class GogoXMarisaKirisima {
public:
	int solve(vector <string> choices) {
		int res;
		int n=choices.size();
		memset(a, 0, sizeof(a));
		memset(used, 0, sizeof(used));
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				if(choices[i][j]=='Y') a[i][j]=1;
				else used[i][j]=1;
			}
		}
		maxn=n;

		vector <int> start(n);
		vector <int> goal(n);
		start[0]=1;
		goal[n-1]=1;

		res=0;
		int g;
		while((g=dijkstra(start, goal))>=0) {
			res++;
			do {
				used[dad[g]][g]=1;
				goal[dad[g]]=1;
				g=dad[g];
			} while(!start[g]);
			start=goal;
		}

		return res;
	}
};