algospot.com :: 과거 게시판: [editorial] SRM393 Div 1

[editorial] SRM393 Div 1

Medium 과 Hard 가 골고루 어려웠던 SRM393 은 하드를 세 명밖에 못 풀면서 안드로 매치로 달려갔습니다. 뭐 그래봐야 페사마가 1등을 먹은 건 여전합니다만. (개인 레이팅 최고기록을 깸으로써, 이제 다시 저와 1000점이 넘게 차이가 납니다. 이거 뭥미)
한국에서는 저와 kimyolo, ilyoan 님이 두 문제 풀면서 선전하셨고요.. 저는 얼떨결에 풀고 챌린지도 안했는데 Top 10 에 들어서 부끄럽습니다. 이런 매치에서는 챌린지를 좀 더 적극적으로 했어야 하는데..
자 그럼 문제 해설 갑니다.
250 - InstantRunoffVoting : 매우 간단한 '이걸 구현해라' 문제이죠. 문제 잘 읽고 따라 치면 되는 문제. (훗, 레코드입니다..) 따라서 틀릴 구석이 많진 않습니다만 은근히 쏠쏠히 틀렸네요. 많이 틀린 부분은 후보 수 != 투표자 수일때, 배열 크기를 바꿔 쓰는 것이었습니다. (한국 A모 레드님도 이걸로 Systest fail) 요런건 공통된 챌린지 포인트이니 잡아주는 센스..
제 소스입니다. 매크로는 좀 봐주세영.

#include<algorithm>
#include<sstream>
#include<string>
#include<vector>
#include<cmath>
using namespace std;
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();++it)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define CLEAR(x,with) memset(x,with,sizeof(x))
#define sz size()
typedef long long ll;
struct InstantRunoffVoting 
{
    int winner(vector <string> voters) 
    {
        bool alive[10]; REP(i,10) alive[i] = true;
        int n = voters.sz, m = voters[0].sz;
        while(true)
        {
            if(count(alive, alive+m, true) == 0) break;
            int got[10]; CLEAR(got,0);
            REP(i,n) REP(j,m) if(alive[ voters[i][j]-'0' ]) { ++got[voters[i][j]-'0']; break; }
            REP(i,m) if(got[i]*2 > n) return i;
            int mini = 987654321;
            REP(i,m) if(alive[i]) mini <?= got[i];
            REP(i,m) if(got[i] == mini) alive[i] = false;
        }
        return -1;
    }
};

500 - NSegmentDisplay; 굉장히 복잡해 보입니다만 알고 보면 그렇게 복잡하진 않습니다. 일단, 한 번이라도 켜진 segment 가 있으면 걔는 고장났을 수 없다는 걸 알 수 있죠. 따라서, 이걸 갖고 맨 처음에 inconsistent 체크를 할 수 있습니다: 매 pattern 에 대해서, 이 symbol 이 보이는 거라고 설명할 수 있는 게 최소한 하나라도 있어야 하는데, 없으면 inconsistent 인 거죠. 예를 들어, pattern[i] = 0 이고 symbol[i] = 1 이라고 합시다. 이 때, i 번째 segment 가 딴 데서도 한 번도 안 켜졌다면 이건 고장난 거라고 치고 넘어갈 수 있습니다. 하지만 딴 데서 한 번이라도 켜져 있다면 이건 말이 안 되죠.
inconsistent 체크를 통과했다면, 한 번이라도 켜졌던 segment 는 모두 work 한다고 주장할 수 있습니다. 그 후, 모두 꺼져 있었던 segment 에 대해 not work 인지, don't know 인지 판단해야 합니다. (한번도 안 켜졌다면 work 일 수는 없습니다. 왜일까요?) 이 점을 각각의 segment 에 따라서 독립적으로 판정을 할 수 있습니다. 이 점이 약간 비직관적이라 어려운데요.. a 비트가 망가진 게 아니려면 X 라는 시나리오로 가야 하고, b 비트가 망가진 게 Y 라는 시나리오로 가야 한다고 합시다. 이 때 알 수 없는 본능이, 'X 와 Y 가 서로 상호 배제적이라면, a와 b에 대해 서로 결과가 연관 있어야 하는 게 아닌가' 라고 속삭입니다만, 사실은 생까고 둘다 '알수 없음' 으로 해야 합니다. 당연히, X 일지 Y 일지 우리는 모르니까요.
하나의 segment 에 대한 판단은.. 모든 패턴을 돌아보면서, 해당 비트가 꺼져 있는 symbol 들을 다 이 패턴에 매칭해 보면 됩니다. 그래서 하나라도 말이 되는 것 (work 인 segment 들이 일치하는 것) 이 있으면 시나리오가 말이 되는 거죠.
소스 나갑니다. 매크로는 위 소스 코드에서 참조하세염;;

struct NSegmentDisplay 
{
    bool works[50][50];
    bool worksAgainst(const string& observed, const string& symbol, const vector<bool>& seen)
    {
        int n = seen.sz;
        REP(i,n)
        {
            if(observed[i] == '1' && symbol[i] == '0') return false;
            if(observed[i] == '0' && symbol[i] == '1' && seen[i]) return false;
        }
        return true;
    }
    string brokenSegments(vector <string> symbols, vector <string> patterns) 
    {
        int s = symbols.sz, p = patterns.sz, n = symbols[0].sz;
        string ret(n, '?');
        vector<bool> seen(n, false);
        REP(i,p) REP(j,n) if(patterns[i][j] == '1') { seen[j] = true; ret[j] = 'Y'; }
        CLEAR(works,0);
        REP(i,p) REP(j,s) works[i][j] = worksAgainst(patterns[i], symbols[j], seen);
        REP(i,p) if(count(works[i], works[i]+s, true) == 0) return "INCONSISTENT";
        REP(i,n) if(!seen[i]) 
        {
            REP(a,p) 
            {
                bool canHappen = false;
                REP(b,s) if(symbols[b][i] == '0') if(works[a][b]) 
                { 
                    canHappen = true; break; 
                }
                if(!canHappen) 
                {
                    ret[i] = 'N';
                    break;
                }
            }
        }
        return ret;
    }
};

1000 - AirlineInternet ; 읽어보면 까마득합니다만 의외로 쉬운 문제입니다. (못 푼 놈이 말은 쉽게 한다) 일단, 비행기의 움직임은 R과 상관없이 동일하므로, R 로 할 수 (모든 비행기에 인터넷을 연결할 수) 있다면 R+1 로도 할 수 있다는 게 자명하죠. 따라서 바이너리 서치를 생각할 수 있습니다.
바이너리 서치는 임의의 R 을 정하고, 이 R 로 모든 비행기가 인터넷을 이용할 수 있는가 판단하는 것을 반복합니다. 이 판단을 어떻게 할까요? 비행기들은 continuous 하게 움직이기 때문에, 매번 시뮬레이션할 수도 없구요.
이런 때 유용하게 써먹을 수 있는 테크닉이, boundary 마다 잘라서 시간을 discrete 하게 바꾸는 방법입니다. 두 대의 비행기의 움직임을 살펴보면, 두 비행기의 거리는 2차함수의 일부를 그리게 됩니다. (왜냐면, 에, 비행기의 각 좌표를 시간에 대한 일차함수로 표현하면, 같은 t 에서 두 비행기 간의 거리는 t 에 대한 2차함수이기 때문에..) 따라서, 비행기간의 거리가 R 이 되는 시점을 찾아내면 그 전후로 그 비행기간에 연결이 가능하다/불가능하다 를 알 수 있게 되죠. 공항에 대해서도 이와 마찬가지로 해 줍니다. 이렇게 하고 이 시점들을 다 소트하면, 각각의 time interval (t[i], t[i+1]) 내에서는 연결 관계가 변하지 않는다는 걸 알 수 있죠.
그럼 t' = (t[i]+t[i+1])/2 시점을 구한 뒤 이 시점에서 비행기들의 위치를 계산하고, 모든 비행기가 인터넷을 쓸 수 있나를 확인하면 됩니다. 모든 time interval 내에서, 떠 있는 비행기가 모두 인터넷을 쓸 수 있어야겠죠?
소스 코드 나갑니다. (공항과 비행기 사이 거리 계산 안해서 섭밋 못하고, 바이너리 서치 100번 할 것 50번 해서 틀린 비운의 코드..)

vector<double> solve(double coef[3])
{
    vector<double> ret;
    if(fabs(coef[2]) < 1e-9)
    {
        // order 1
        if(fabs(coef[1]) > 1e-9)
            ret.push_back(- coef[0] / coef[1]);
        else if(fabs(coef[0]) < 1e-8)
            ret.push_back(0);
    }
    else
    {
        // order 2
        double D = coef[1] * coef[1] - 4.0 * coef[0] * coef[2];
        if(D >= 0)
        {
            double sqrtD = sqrt(D);
            ret.push_back((-coef[1] + sqrtD) / (2 * coef[2]));
            if(sqrtD > 1e-9)
                ret.push_back((-coef[1] - sqrtD) / (2 * coef[2]));
        }
    }
    return ret;
}
struct AirlineInternet 
{
    double a[20], b[20], c[20], d[20];
    int fromTime[20], toTime[20];
    int airX[20], airY[20];
    int n, m;
    vector<int > integerTimes;
    void convert(const string& flight, int index)
    {
        int fromAir, fromTime, toAir, toTime;
        sscanf(flight.c_str(), "%d %d %d %d", &fromAir, &toAir, &fromTime, &toTime);        
        integerTimes.pb(fromTime);
        integerTimes.pb(toTime);
        int fromX = airX[fromAir], fromY = airY[fromAir];
        int toX = airX[toAir], toY = airY[toAir];
        double xSpeed = (toX - fromX) / double(toTime - fromTime);
        double ySpeed = (toY - fromY) / double(toTime - fromTime);
        a[index] = fromX - fromTime * xSpeed;
        b[index] = xSpeed;
        c[index] = fromY - fromTime * ySpeed;
        d[index] = ySpeed;
        this->fromTime[index] = fromTime;
        this->toTime[index] = toTime;
    }
    inline double sqr(double d) { return d*d; }
    bool feasible(double R)
    {
        vector<double> times;
        times.insert(times.end(), all(integerTimes));
        REP(i,m) REP(j,n) 
        {
            double ad = a[i] - airX[j], bd = b[i], cd = c[i] - airY[j], dd = d[i];
            double coef[3];
            coef[2] = sqr(bd) + sqr(dd);
            coef[1] = 2 * (ad * bd + cd * dd);
            coef[0] = sqr(ad) + sqr(cd) - sqr(R);
            vector<double> sol = solve(coef);
            REP(k,sol.sz) 
            {
                double t = sol[k];
                if(t <= fromTime[i] || toTime[i] <= t) continue;
                times.pb(sol[k]);
            }
        }
        REP(i,m) REP(j,i) 
        {
            if(toTime[i] <= fromTime[j] || toTime[j] <= fromTime[i]) continue;
            double ad = a[i] - a[j], bd = b[i] - b[j], cd = c[i] - c[j], dd = d[i] - d[j];
            double coef[3];
            coef[2] = sqr(bd) + sqr(dd);
            coef[1] = 2 * (ad * bd + cd * dd);
            coef[0] = sqr(ad) + sqr(cd) - sqr(R);
            vector<double> sol = solve(coef);
            REP(k,sol.sz) 
            {
                double t = sol[k];
                if(t <= fromTime[i] || t <= fromTime[j] || toTime[i] <= t || toTime[j] <= t) continue;
                times.pb(sol[k]);
            }
        }
        sort(all(times));
        times.erase(unique(all(times)), times.end());
        double x[20], y[20];
        bool included[20], visited[20];
        REP(i,times.sz-1) if(times[i+1] - times[i] > 1e-9)
        {
            double t = (times[i] + times[i+1]) * 0.5;            
            REP(j,m)
            {
                included[j] = (fromTime[j] < t && t < toTime[j]);
                if(included[j])
                {
                    x[j] = a[j] + b[j] * t;
                    y[j] = c[j] + d[j] * t;
                }
            }
            CLEAR(visited,0);
            queue<int> q;
            REP(j,n) REP(k,m) if(!visited[k] && included[k] && hypot(airX[j] - x[k], airY[j] - y[k]) <= R)
            {
                visited[k] = true;
                q.push(k);
            }
            while(!q.empty())
            {
                int here = q.front(); q.pop();
                REP(there,m) if(included[there] && !visited[there] && hypot(x[here]-x[there], y[here]-y[there]) <= R)
                {
                    visited[there] = true;
                    q.push(there);
                }
            }
            REP(j,m) if(included[j] && !visited[j]) return false;
        }
        return true;
    }
    double minimumRange(vector <string> airportLocations, vector <string> flights) 
    {
        n = airportLocations.sz; m = flights.sz;
        REP(i,n) { sscanf(airportLocations[i].c_str(), "%d %d", &airX[i], &airY[i]); }
        REP(i,m) convert(flights[i], i);
        sort(all(integerTimes));
        integerTimes.erase( unique(all(integerTimes)), integerTimes.end() );
        double lo = 0, hi = 0;
        REP(i,n) REP(j,i) hi >?= hypot(airX[i] - airX[j], airY[i] - airY[j]);
        hi *= 0.5;
        printf("hi %.9lf\n", hi);
        REP(iter,50)
        {
            double mid = (lo+hi) * 0.5;
            if(feasible(mid))
                hi = mid;
            else
                lo = mid;
        }
        printf("gap %.8lf\n", hi-lo);
        return hi;
    }
};
~~~<div>[이 글은 과거 홈페이지에서 이전된 글입니다. <a href="http://algospot.andromeda-express.com/zbxe/editorial/45545">원문보기</a>]</div>

16년 전

4개의 댓글이 있습니다.

JongMan

앗차 iter 50 이 아니라 100 인데 -_-

16년 전 link
nocut98

이번에 마라톤 매치가 끝나면서 (아직 정확한 건 아니지만) 양쪽으로 나가는 사람들이 결정되는데요(ACRush, bettyone) 등등 쟁쟁하신 분들이 아마 떨어질 예정입니다. 그 중에 제일 눈에 띄는 건!!! bhzhan!!! 놀랍게도 옐로의 레이팅을 가지고 알고리즘, 마라톤 양쪽대회 전부 나가십니다...ㄷㄷㄷ;;; 뭥미?

16년 전 link
nocut98

일본애들은 국가 칼라가 미듐 안풀고 하드 풀기 인듯...

16년 전 link
Taeyoon_Lee

종만님과 일루님이 250 1,2등을 하셨더군요..ㅠ 대단하십니다..ㅠ

16년 전 link
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.

JongMan: 앗차 iter 50 이 아니라 100 인데 -_-

16년 전 link

nocut98: 이번에 마라톤 매치가 끝나면서 (아직 정확한 건 아니지만) 양쪽으로 나가는 사람들이 결정되는데요(ACRush, bettyone) 등등 쟁쟁하신 분들이 아마 떨어질 예정입니다. 그 중에 제일 눈에 띄는 건!!! bhzhan!!! 놀랍게도 옐로의 레이팅을 가지고 알고리즘, 마라톤 양쪽대회 전부 나가십니다...ㄷㄷㄷ;;; 뭥미?

16년 전 link

nocut98: 일본애들은 국가 칼라가 미듐 안풀고 하드 풀기 인듯...

16년 전 link

Taeyoon_Lee: 종만님과 일루님이 250 1,2등을 하셨더군요..ㅠ 대단하십니다..ㅠ

16년 전 link

정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.

SINCE 2007

다가오는 이벤트들

[editorial] SRM393 Div 1

4개의 댓글이 있습니다.