cormoran's note


cormoran

競技プログラミング・電子工作・ロボットなどで遊びます



Recent Post




aoj-VolumeICPCOOC2015-D

ACM-ICPC 2015 Tsukuba D : Wall Clocks

本番中に読んだけどCで死んでいたので放置されてしまった問題。ちゃんと考えたら方針くらいは自分でも立てられたかもしれない?雰囲気。座標をいい感じで一次元に落とすあたりの実装方法に自由度があってちょっとつらかった。

問題概要

W*Dの長方形の中に一人以上の人がいる。人は上下右左のいずれかを向いており、視界は90度。

長方形の壁に時計を置く時、全員が時計を見られるようにするには最低何個の時計が必要か?

解法

置く場所を1箇所決めると、そこから一方向に貪欲的(できるだけ置くのを遅らせる)においていくことで、その場合の最小個数になる。

 すべての候補箇所について上を試せば良い。n = 1000なので大丈夫。自分の解法ではO(n^2 * logn)。


struct Point{
    int x,y;
    Point():x(0),y(0){}
    Point(int x,int y):x(x),y(y){};
    Point& operator +=(const Point &p){x += p.x; y += p.y; return *this;}
};
ostream &operator << (ostream& os, const Point& p){ return os << "(" << p.x << "," << p.y << ")";}

struct ClosedRange{
    int l,r; //[l,r]
    ClosedRange(){}
    ClosedRange(int l,int r):l(l),r(r){}
    bool operator < (const ClosedRange &a) const { return make_pair(r,l) < make_pair(a.r, a.l); }
};
ostream& operator << (ostream &os, const ClosedRange &r){ return os << "[" << r.l << " " << r.r << "]"; }


// // // // // // // // // // // // // // // // // // // // // // // // // // // // // // // // // // //


// 2d to 1d
int lower_dimension(Point p, int w, int d){
    return  p.y == 0 ? p.x :
            p.x == w ? w + p.y :
            p.y == d ? w + d + (w - p.x) :
            p.x == 0 ? w*2 + d + (d - p.y) : -1;
}

Point find_cross_point(Point p, Point dp, int w, int d){
    while(0 < p.x and p.x < w and 0 < p.y and p.y < d) p += dp;
    return p;
}

ClosedRange calc_range(Point p, char dir, int w, int d){
    ClosedRange ret;
    Point dp[] = {Point(-1, 1), Point(1, 1), Point(1, -1), Point(-1, -1)};
    map<char, int> dtoi = {{'N', 0}, {'E', 1}, {'S', 2}, {'W', 3}};
    Point dp1 = dp[ ( dtoi[ dir ] + 1 ) % 4 ];
    Point dp2 = dp[ dtoi[ dir ] ];
    Point l = find_cross_point(p, dp1, w, d);
    Point r = find_cross_point(p, dp2, w, d);
    return ClosedRange(lower_dimension(l, w, d), lower_dimension(r, w, d));
}

bool check_used(set<int> &clock, ClosedRange &r){
    if(r.l <= r.r){
        auto itr = clock.lower_bound(r.l);
        return itr != clock.end() ? *itr <= r.r : false;
    } else {
        auto itr = clock.lower_bound(r.l);
        auto itr2 = clock.upper_bound(r.r);
        return  itr  != clock.end()   ? true :
                itr2 != clock.begin() ? *--itr <= r.r : false;
    }
}

int trial(vector<ClosedRange> &range, int start){
    debug("start at ",start);
    int n = range.size();
    set<int> clock;
    for(int i = start; i < start + n; i++){
        if( check_used(clock,range[ i%n ]) ) continue;
        clock.insert(range[ i%n ].r);
        debug("clock at ",range[ i%n ].r);
    }
    return clock.size();
}

bool solve(){
    int n, w, d; cin >> n >> w >> d;
    vector<ClosedRange> range(n);
    rep(i,n){
        int x,y;
        char f; cin >> x >> y >> f;
        range[i] = calc_range(Point(x,y), f, w, d);
        debug(range[i]);
    }   
    sort( all( range ) );
    int ans = INF;
    rep(i, n){
        ans = min(ans, trial(range, i));
    }
    cout << ans << endl;
    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    while(solve());
    return 0;
}

comments powered by Disqus