kojingharangの日記

GCJ2012 Round1B

14:37 |

• びーる＆深夜で過酷だったけど rank 844 でなんとか通過予定
• 問題 B が 1.5h あったのにできなかったのは問題であるなぁ

ツイートする

GCJ2012 Round1B A. Safety in Numbers

14:37 |

• S[i] が与えられる。0<=Y[i]<=1 として、各 i について F[i] = S[i]+(ΣS)*Y[i] が単独で最小にならないようにするための Y[i] の最小値を求める問題。

• Y[i] が決まると F[i] が決まって、i!=j な F[j] が F[i] 以下になればいいので
• Y[j] として最低必要な分を 1-Y[i] から補充していく。
• 全部補充できたら F[i] は単独で最小にならない。
• 各 i について Y[i] を 0～1 の間で二分探索する。

• max(0, A-w[j]) の和 < 1-Y[i] かどうかだけ判定したほうがスマートだった

int f(int i, double mid, VI& w, int N, int sum) {
	double A = w[i]+sum*mid;
	double rest = sum*(1-mid);
	int ok=1;
	REP(j, N) {
		if(i==j) continue;
		if(A>w[j]) {
			rest -= A-w[j];
			if(rest<0) {
				ok=0;
				break;
			}
		}
	}
	return ok;
}

int main() {
	int test_cases;
	cin>>test_cases;
	REP(ttt, test_cases) {
		int N;
		cin>>N;
		VI w(N);
		REP(i, N) cin>>w[i];
		int sum = accumulate(ALL(w), 0);
		
		cout<<"Case #"<<ttt+1<<": ";
		REP(i, N) {
			if(i!=0) cout<<" ";
			double lo = 0, hi = 1;
			REP(loop, 100) {
				double mid = (lo+hi)/2;
				//cout<<mid<<" "<<A<<" "<<ok<<endl;
				int ok = f(i, mid, w, N, sum);
				if(ok) lo=mid;
				else   hi=mid;
			}
			cout<<setprecision(8)<<hi*100;
		}
		cout<<endl;
	}
	return 0;
}

ツイートする

GCJ2012 Round1B B. Tide Goes In, Tide Goes Out

14:37 |

• カヤックが W x H セルの洞窟にいて水が毎秒10cmで下がる。水位と各セルの地面と天井の高さによって隣のセルに進めるかどうか決まる（詳細省略...）ゴールまで行く最短時間を求める問題。

• 右か下にしか進まないと思ってて、O(WH) の DP を書いた
• 水位が下がらなくても進める時間はカウントしない処理を入れる
• Small の実行結果を見ると INF になってるのがあっておかしい
• そうか左に進むこともあるのか
• BFS
• WA
• おわり

（あとで）

• なるほど Dijkstra か..
• deque を priority_queue に書き換える
• priority_queue は大きいのから出てくるので時間を負にして push
• AC
• 各セルの水位も保存してるけど、水位は時刻から決まるから不要だった。いろいろ無駄に複雑に書いてしまった

#define INF 100000000

int main() {
	int test_cases;
	cin>>test_cases;
	REP(ttt, test_cases) {
		int L, H, W;
		cin>>L>>H>>W;
		VVI ce(H, VI(W));
		VVI fl(H, VI(W));
		REP(y, H) REP(x, W) cin>>ce[y][x];
		REP(y, H) REP(x, W) cin>>fl[y][x];
		VVI ti(H, VI(W, INF));
		VVI he(H, VI(W));
		VVI st(H, VI(W, 1));
		st[0][0] = 0;
		ti[0][0] = 0;
		he[0][0] = L;
		VVI vis(H, VI(W));
		priority_queue <pair <int, pair <int, int> > > q;
		//deque<PII> q;
		q.push(MP(0, MP(0,0))); // x, y
		int ok=0;
		while(q.size()) {
			int x = q.top().second.first;
			int y = q.top().second.second;
			//cout<<"pop "<<q.top().first<<"  "<<x<<" "<<y<<endl;
			q.pop();
			if(ti[y][x]==INF) continue;
			if(x==W-1 && y==H-1) {ok=1;break;}
			if(vis[y][x]) continue;
			vis[y][x]=1;
			int tdx[] = {1, 0, -1, 0};
			int tdy[] = {0, 1, 0, -1};
			REP(dir, 4) {
				if(dir==0 && x>=W-1) continue; // right
				if(dir==1 && y>=H-1) continue; // down
				if(dir==2 && 0>=x) continue; // left
				if(dir==3 && 0>=y) continue; // top
				int nx = x+tdx[dir];
				int ny = y+tdy[dir];
				int lvl = he[y][x];
				if(fl[y][x]+50<=ce[ny][nx] && fl[ny][nx]+50<=ce[ny][nx] && fl[ny][nx]+50<=ce[y][x] ) {
					int wait = max(0, lvl-(ce[ny][nx]-50));
					if(!st[y][x] && wait==0) {
						st[ny][nx] = 0;
						ti[ny][nx] = ti[y][x];
						he[ny][nx] = he[y][x];
					} else
					if(fl[y][x]+20<=lvl-wait) {
						if(ti[y][x]+wait+10 < ti[ny][nx]) {
							ti[ny][nx] = ti[y][x]+wait+10;
							he[ny][nx] = lvl-(wait+10);
						}
					} else {
						if(ti[y][x]+wait+100 < ti[ny][nx]) {
							ti[ny][nx] = ti[y][x]+wait+100;
							he[ny][nx] = lvl-(wait+100);
						}
					}
					//cout<<"push "<<ti[ny][nx]<<" "<<nx<<" "<<ny<<endl;
					q.push(MP(-ti[ny][nx], MP(nx, ny)));
				}
			}
			//cout<<"loop end"<<endl;
		}
		//cout<<ti<<endl;
		//cout<<he<<endl;
		//cout<<st<<endl;
		//if(!ok) cout<<"!!!!"<<endl;
		cout<<"Case #"<<ttt+1<<": "<<(double)ti[H-1][W-1]/10<<endl;
	}
	return 0;
}

ツイートする

GCJ2012 Round1B C. Equal Sums

14:37 |

• いくつかの整数が与えられる。和が同じになる異なる部分集合を２つ見つける問題

• small は部分集合とその和を全通り計算する

• large は乱択らしい 解説待ち。

void pr(ll i, VI& w, int N) {
	int first=1;
	REP(j, N) {
		if((i>>j)&1) {
			if(!first) cout<<" ";
			cout<<w[j];
			first=0;
		}
	}
	cout<<endl;
}

int main() {
	int test_cases;
	cin>>test_cases;
	REP(ttt, test_cases) {
		int N;
		cin>>N;
		VI w(N);
		REP(i, N) cin>>w[i];
		map<ll, ll> ma;
		int sum = accumulate(ALL(w), 0);
		int ok=0;
		REP(i, ((ll)1)<<N) {
			int A = 0;
			REP(j, N) {
				if((i>>j)&1) A += w[j];
			}
			if(ma.count(A)) {
				cout<<"Case #"<<ttt+1<<":"<<endl;
				pr(ma[A], w, N);
				pr(i, w, N);
				ok=1;
				break;
			}
			ma[A] = i;
		}
		
		if(!ok) cout<<"Case #"<<ttt+1<<": Impossible"<<endl;
	}
	return 0;
}

ツイートする