2009-05-06
SRM355 Div1 Easy (300points): MixingLiquids
- なんか線形計画法っぽい
- 最初に考えたやつではテスト通らない
- 横軸にsubstance,縦軸にwater、で生成可能な溶液の範囲を表すconvexと、求める濃度を表す（原点を通る）直線の交点（で原点から一番遠い所）
- convexは左回りが薄い順、右回りが濃い順
- 0%,100%の対策（直線の傾きが∞になっても死なないように）
- 同じ濃度の溶液が複数あった場合の対策（最初にまとめる）
- 求める濃度と同じ濃度の溶液については最初に除外
- など、解き方は分かったんだけど最初にあれこれ試行錯誤した分で時間が足りず。途中トイレに立ったのも入れて1時間半ぐらい。
- 90.0 points (time over), Passed System Test
#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())
#include <float.h>
class MixingLiquids {
public:
double howMuch(vector<int> percent, vector<int> amount, int need) {
int n=sz(percent);
// uniq
map<int,int> pa_;
rep(i,n){
int pi=percent[i],ai=amount[i];
if(found(pa_,pi))
pa_[pi] += ai;
else
pa_[pi] = ai;
}
vector<pair<double,pair<double,double> > > pa;
double subssum=0.0, watsum=0.0;
double mixsubs=0.0, mixwat=0.0;
tr(pa_,it){
int pi=it->first, ai=it->second;
double subs=0.01 * ai * pi;
double wat=(double)ai - subs;
if(pi==need){
mixsubs += subs;
mixwat += wat;
}else{
subssum += subs;
watsum += wat;
pa.pb(make_pair((subs==0)?DBL_MAX:wat/subs,make_pair(subs,wat)));
}
}
if(subssum==0 || need==0){ // water only
return mixsubs+mixwat;
}
double totalm = watsum/subssum, needm = (double)(100-need)/need;
if(totalm==needm){
return (mixsubs+mixwat)+(subssum+watsum);
}else if(totalm<needm){
// water左
sort(all(pa)); reverse(all(pa));
double x=0,y=0;
tr(pa,it){
double m=it->first, s=it->second.first, w=it->second.second;
double x_=x+s, y_=y+w;
if(x_==0){
if(need==0) return (mixsubs+mixwat)+y_;
} else if (y_/x_ <= needm) {
if(m==DBL_MAX){
x_ = x;
}else{
x_ = (m*x-y)/(m-needm);
}
y_ = x_*needm;
return (mixsubs+mixwat)+(x_+y_);
}
x=x_; y=y_;
}
}else{
// subs右
sort(all(pa));
double x=0,y=0;
tr(pa,it){
double m=it->first, s=it->second.first, w=it->second.second;
double x_=x+s, y_=y+w;
if(x_==0){
if (need==0) return (mixsubs+mixwat)+y_;
}else if (y_/x_ >= needm) {
if(m==DBL_MAX){
x_ = x;
}else{
x_ = (m*x-y)/(m-needm);
}
y_ = x_*needm;
return (mixsubs+mixwat)+(x_+y_);
}
x=x_; y=y_;
}
}
return (mixsubs+mixwat)+(subssum+watsum);
}
};
SRM223 Div1 Hard: RevolvingDoor
Algorithm Tutorials: How To Find a Solution (by Dumitru) より
- 1000点問題！
- マップ上のSからEまで行くのに、回転ドアを最低何回回転させる必要があるか。(辿り着けない場合は-1)
- 確かにBFSであります
- ドアの回転状態を持ち回る必要がある。listとか使うか?
- 問題よく読め！ドアは最大10個しかない！10bit！
- １つ回転数を少なく答えるケースがある・・・ゴールにドアがかぶっている場合にドアの状態を反映していなかった
- 時間かかったけどとりあえず全テストケース通るようになった！
- submit ... 317.84points (146'39'')
- 本番は３問で75分なんですけど＞＜
- しかしFailed System Test: TLE×1
"S ", " ", " ", "-O--O--O--O--O--O--O--O--O--O- ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " #", " #E"
- 確かにこれはゴールできないw
- ドアぐるぐる回しながら全ての状態(50x50x2^10)を走査することになるだろう
- ステップ数数え始める前に、ドア無視してflood fillしておくか
- どうやるんだっけ...queueだと重複あってなかなか進まない。set使うか
- できた
- →Passed System Test
- 最終的なコード:
#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())
class RevolvingDoors {
int w,h;
inline int cell(int x,int y){return (y<<6)|x;}
inline int cellx(int c){return c&63;}
inline int celly(int c){return c>>6;}
inline int left(int c){return c-1;}
inline int right(int c){return c+1;}
inline int up(int c){return c-64;}
inline int down(int c){return c+64;}
public:
int turns(vector<string> m) {
h=sz(m),w=sz(m[0]);
vector<bool> road(4096,false);
vector<vector<int> > score(4096);
vector<int> doors, doormap(4096,-1), doorof(4096,-1);
int doorcnt=0, start_cell=0, end_cell=0;
// pass1
rep(y,h){
rep(x,w){
int c=cell(x+1,y+1);
switch(m[y][x]){
case 'S': road[c]=true; start_cell=c; break;
case 'E': road[c]=true; end_cell=c; break;
case 'O': road[c]=false; doormap[c]=doorcnt++; doors.pb(c); break;
case '-': road[c]=true; break;
case '|': road[c]=true; break;
case '#': road[c]=false; break;
case ' ': road[c]=true; break;
}
}
}
int nm=1<<doorcnt;
rep(i,4096){
score[i].resize(nm); rep(j,nm) score[i][j]=INT_MAX;
}
int doorstat = 0;
// pass2
rep(y,h){
rep(x,w){
int c=cell(x+1,y+1), r,l,u,d,did=-1;
switch(m[y][x]){
case 'O': case '#': break;
case '-':
r=right(c),l=left(c);
if(doormap[r]>=0) did=doormap[r];
else if(doormap[l]>=0) did=doormap[l];
doorof[c]=did;
// doorstat |= (1 << did);
break;
case '|':
u=up(c),d=down(c);
if(doormap[u]>=0) did=doormap[u];
else if(doormap[d]>=0) did=doormap[d];
doorof[c]=did;
doorstat |= (1 << did);
break;
case ' ': case 'S': case 'E':
r=right(c),l=left(c),u=up(c),d=down(c);
if(doormap[r]>=0) did=doormap[r];
else if(doormap[l]>=0) did=doormap[l];
else if(doormap[u]>=0) did=doormap[u];
else if(doormap[d]>=0) did=doormap[d];
doorof[c]=did;
break;
}
}
}
// check impasse: flood fill (あとから追加)
vector<bool> reach(4096,false);
set<int> s0;
s0.insert(start_cell); // reach[start_cell]=true;
while(!s0.empty()){
typeof(s0.begin()) it = s0.begin();
int c=*it; s0.erase(it);
reach[c]=true;
if (c==end_cell) break;
printf(" I %d %d¥n", cellx(c),celly(c));
int nxt[4] = { up(c), right(c), down(c), left(c) };
rep(i,4){
int c_=nxt[i];
if(!road[c_]) continue;
if(!reach[c_]) s0.insert(c_);
}
}
if(!reach[end_cell]) return -1;
// let's探索
priority_queue<pair<int,pair<int,int> > > pq; // -score,loc,doorstat
pq.push(make_pair(0,make_pair(start_cell,doorstat)));
vector<int> goaled; int goaled_min=INT_MAX;
while(!pq.empty()){
pair<int,pair<int,int> > p=pq.top(); pq.pop();
int sc=-p.first, c=p.second.first, ds=p.second.second;
if (sc>goaled_min) break;
if (score[c][ds]<=sc) continue;
score[c][ds]=sc;
if(c==end_cell) {
if (sc<goaled_min) {
goaled_min=sc; goaled.pb(sc); }
continue;
}
int nxt[4] = { up(c), right(c), down(c), left(c) };
rep(i,4){
int c_=nxt[i];
if(!road[c_]) continue;
int did=doorof[c_];
if(did>=0){ // ドアな可能性あり
int dcell=doors[did], ofs=c_-dcell; if(ofs<0) ofs=-ofs;
int mask=1<<did;
int st=ds & mask;
if(st && ofs==64) { // |
if (c-c_ != c_-dcell){ //回転出来る
pq.push(make_pair(-(sc+1),make_pair(c_,ds-mask)));
}
} else if(!st && ofs==1){ // -
if (c-c_ != c_-dcell){ //回転出来る
pq.push(make_pair(-(sc+1),make_pair(c_,ds+mask)));
}
} else {
// ドアなし
pq.push(make_pair(-sc,make_pair(c_,ds)));
}
}else{
pq.push(make_pair(-sc,make_pair(c_,ds)));
}
}
}
if(sz(goaled) > 0){
sort(all(goaled));
return goaled[0];
} else {
return -1;
}
}
};
コメント
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20090506