[editorial] SRM 373 DIV 1 후기

  • astein
    astein

    오늘의 스탠딩입니다.
    srm373.PNG
    음.. 150등 안에 한국인이 다섯명이 있긴 하지만 성적은 썩 좋지 않네요.
    개인적으로는 다들 맞은 Level 1 틀린게 좀 컸네요 -.-;;

    Easy (250 pts.)

    • 문제설명 single space로 구분되어 있는 String을 적당히 잘라서 width * height 크기의 panel에 채우려고 한다. String을 잘라서 여러 줄에 걸쳐서 채울 수 있지만, 입력받은 순서대로 채워야 한다. 한 줄에 여러 개의 단어를 사용할 때는 항상 space로 구분되어야 하지만, 다른 줄에 위치한 경우에는 필요없다. 또한 각 단어들은 잘라서 사용할 수 없다. (즉, 하나의 단어는 항상 한 줄에 표현되어야 한다.) 당신은 7보다 큰 font size만 사용할 수 있다. font size가 N인 경우, 각 글자의 height는 2*N pixel이고, width는 N+2 pixel이다. (alphabet과 space의 width는 모두 N+2로 같다.) 반드시 써야 할 text와 panel의 크기가 주어졌을 때, 사용가능한 최대 font size를 구하시오. panel은 회전할 수 없으며, 7보다 큰 font size를 사용하여 채울 수 없는 경우 -1을 리턴한다. [spoiler="더 보기..."]* 해결방법 width와 height의 제한이 10000이기 때문에, font size를 8 ~ 10000까지 돌려보면서 "각각의 font size에서 panel에 채울 수 있는가?" 를 풀면 됩니다. font size가 정해지면, 각 line에 사용할 수 있는 단어를 greedy algorithm으로 구할 수 있습니다. ( width가 제한되어 있으므로 line을 최소로 만들면 되기 때문입니다. ) 아래에 제 소스코드를 추가합니다. ~~~ cpp

    #define sz(a) ((a).size())
    bool go(vector word, int w, int h, int fontsize) {
    int lines = h / (2 * fontsize); // panel에 채울 수 있는 최대 line
    int chars = w / (fontsize + 2); // 한 줄에 채울 수 있는 최대 글자수
    // 어떤 단어도 height제한 때문에 panel에 들어가지 않는 경우
    if (lines == 0) return false;
    int a = 1, b = -1; // a는 몇 개의 line을 사용했는지, b는 현재 line에 몇 개의 character를 사용했는지 count합니다.
    for (int i = 0; i < sz(word); i++) {
    // panel의 width제한 때문에 단어를 채울 수 없는 경우
    if (sz(word[i]) > chars) return false;
    b += sz(word[i]) + 1;
    if (b > chars) {
    a++;
    if (a > lines) return false; // height 제한 초과
    b = sz(word[i]);
    }
    }
    return true;
    }

    P.S)  8부터 5000까지 Linear하게 다 보는 방법도 있지만, binary search를 사용하면 좀 더 효율적으로 작성할 수 있습니다 :-)
    [/spoiler]
    
    
    
    Medium (500 pts.)
    * 문제설명
      몇 명의 보행자가 횡단보도를 건너고 있다. 당신은 모범적인 운전사이기 때문에 사람들을 절대로 치고 지나가지 않는다. 하지만 매우 뛰어난 드라이빙 스킬을 가지고 있어, 도로의 어느 위치에서든지 carWidth이상의 틈이 있다면 순식간에 횡단보도를 지나갈 수 있다.
      보행자가 횡단보도에 도착하는 시간과 보행자의 속도가 입력으로 주어진다. (당연한 이야기이지만, 보행자는 횡단보도를 건너다가 쉬거나 하지 않고, 일직선으로 건넌다.) 그리고 횡단보도의 길이 roadWidth, 차의 폭 carWidth, 자동차가 횡단보도에 도착하는 시간인 carArrival이 주어졌을 때, 이 자동차가 횡단보도를 통과할 수 있는 최소 시간을 구하시오.
    [spoiler="더 보기..."]
    * 해결방법
      운전자가 이 횡단보도를 건널 수 있는 타이밍은 대략적으로 아래의 네 가지 경우로나눌 수 있습니다.
      - 자동차가 도착하자마자 (at carArrival)
      - 보행자가 시작점/횡단보도 끝점에 도착했을 때
      - 보행자가 carWidth 위치 / roadWidth - carWidth 위치에 도착했을 때
      - 어떤 두 보행자 사이의 거리가 carWidth가 되는 순간
      (물론 위의 경우중에 불필요한 타이밍이 있을수도 있습니다.)
      그러면 각각의 이벤트가 발생하는 시간을 미리 계산해 둔 후, 어떤 시점에서 carWidth만큼의 틈이 있는지를 구합니다. 어떤 시점에서 carWidth만큼의 틈이 있는지 없는지의 여부는 횡단보도 상에 있는 모든 보행자의 위치를 구한 다음, 각 보행자 사이의 거리를 계산하면 됩니다. (각 보행자 사이의 거리를 체크할 때, 시작점 - 보행자간 거리와 보행자 - 끝점간 거리도 체크해 주어야 합니다.)
    ~~~ cpp
    
    double passTime(vector <string> pedestrians, int roadWidth, int carWidth, int carArrival) {
        int N = sz(pedestrians);
        vector <double> timing;
        timing.pb(carArrival); // check 1
        REP(i, N) {
            istringstream sin(pedestrians[i]);
            sin >> T[i] >> V[i];
            timing.pb(T[i]); // check 2-1
            timing.pb(T[i] + roadWidth * 1.0 / V[i]); // check 2-2
            timing.pb(T[i] + carWidth * 1.0 / V[i]); // check 3-1
            timing.pb(T[i] + (roadWidth - carWidth) * 1.0 / V[i]); // check 3-2
        }
        REP(i, N)
            REP(j, N) {
                if (V[i] == V[j]) continue;
                double x = (carWidth + T[i] * V[i] - T[j] * V[j]) * 1.0 / (V[i] - V[j]);
                timing.pb(x); // check 4
            }
        sort(all(timing));
        vector <int> T(N), V(N);
        REP(i, sz(timing)) {
            if (timing[i] < carArrival) continue;
            vector <double> pos;
            pos.pb(0.0); // 횡단보도 시작점
            pos.pb(roadWidth); // 횡단보도 끝점
            REP(j, N) {
                if (timing[i] <= T[j]) continue; 
                if (timing[i] >= T[j] + roadWidth * 1.0 / V[j]) continue;
                pos.pb(V[j] * (timing[i] - T[j])); // 횡단보도 사이에 있는 보행자의 위치
            }
            sort(all(pos));
            REP(j, sz(pos) - 1) 
                if (pos[j + 1] - pos[j] + EPS >= carWidth) return timing[i];
        }
        return -1;
    }

    [/spoiler]

    Hard (1000 pts.)

    • 문제설명
      어떤 점들의 집합이 주어졌을 때, 아래의 조건을 만족시키는 나선(Spiral)을 구성하는 최대 점의 개수를 구하시오.
      << 조건 >>

      1. 항상 (0, 0)에서 시작한다.
      2. 현재의 위치에서 (x, y)로 이동한다면, 둘 사이를 연결하는 선분을 긋는다. (x, y)는 새로운 시작점이 된다.
      3. 아래의 규칙을 모두 만족하는 조건 아래에서, rule 2를 반복한다.
      4. 규칙 1 : Spiral은 스스로 겹치지 않는다. 인접한 선분이 공유하는 끝점들을 제외하고, 다른 교점이 없다.
      5. 규칙 2 : 각각의 점은 두 번 이상 사용되지 않는다.
      6. 규칙 3 : 다음 선분으로 연결할 때, 항상 반시계 방향으로 꺾거나, 직진한다. 즉, 회전각 angle은 0 <= angle < 180이 된다.
      7. 규칙 4 : "마지막 바로 이전 점"에서 "마지막 점"은 선분이 아니라 반직선이라고 가정한다. 즉, 같은 선상에 spiral의 다른 선분(혹은 점)을 지나가지 않는다. 아래의 그림은 규칙 1, 2, 3을 만족시키지 못하는 예를 나타낸다. 아래의 그림은 규칙 4를 만족시키지 못하는 경우들이다. [spoiler="더 보기..."]
      8. 해결방법 전체적인 큰 틀은 Dynamic Programming을 사용하였습니다. DP 테이블의 정의는 아래와 같습니다. table[a][b][S] = 최근에 사용한 선분이 a-b 이고, 현재 사용되지 않는 점들의 set이 S일 때, 앞으로 사용할 수 있는 최대 점 수.

      위와 같이 정의된 table에서 최근에 a - b 가 연결되었고, 아직 사용되지 않는 점들의 집합 S가 있습니다. 그러면 이 중에서 S - p를 연결할 수 있고, table[b][p][S - p] + 1 중에서 제일 큰 값이 table[a][b][S]에 들어가게 됩니다.
      4가지 규칙 중 마지막 규칙을 해결하는 것이 제일 까다롭지만, 이 규칙은 "제일 마지막에 연결되는 선분(위의 설명에서, 선분b - p)이 현재까지의 spiral에서 사용했던 점들 모두 strict하게 left side에 있다"를 체크함으로서 해결 가능합니다. 만약 b - p와 같은 선 상에 점이 있다면, b - p 다음 점은 항상 반시계 방향(혹은 일직선)으로 꺾여야 하므로 spiral 안쪽으로 휘어들어가는 모양이 됩니다. 결국 위를 반복해도, 마지막 반직선은 spiral 어딘가에 부딪치게 되므로, 어떻게 하더라도 규칙 4를 만족시킬 수 없게 됩니다.
      P.S) 일단 소스를 첨부하긴 합니다만, 매크로에 익숙하지 않은 경우, 읽으시는 데 약간 어려움이 있으실 수도 있겠네요 ㅜㅜ
      다음에 시간나면 수정하겠습니다 orz

    #define EPS 1e-10
    #define pb push_back
    #define sz(a) ((int)a.size())
    #define REP(i,n) FOR(i,0,n)
    struct Point {
    int x, y;
    Point(int ix = 0, int iy = 0) : x(ix), y(iy) {}
    bool operator == (const Point &a) const {
    return abs(x - a.x) < EPS && abs(y - a.y) < EPS;
    }
    };
    char table[16][16][1 << 16];
    vector a;
    int N;
    struct SpiralConstruction {
    // a, b, c가 일직선상에 있다고 가정했을 때 a -- b -- c => true
    bool between(Point a, Point b, Point c) {

    int X = (a.x - b.x) * (c.x - b.x);
    int Y = (a.y - b.y) * (c.y - b.y);
    return (X <= 0 && Y <= 0);
    }
    // a-b-c가 counter clockwise꺾임인가? (일직선 상이라면, 현재 방향 그대로 직진인 경우 true)
    bool left(Point a, Point b, Point c) {
    int p = (a.x * b.y + b.x * c.y + c.x * a.y);
    p -= (a.x * c.y + b.x * a.y + c.x * b.y);
    if (p < 0) return false;
    if (p == 0 && !between(b, a, c)) return false;
    return true;
    }
    // for memoization.
    int go(int q, int w, int bit) {
    if (table[q][w][bit] != -1) return table[q][w][bit];
    int ret = 0;
    REP(i, N) {
    if (bit & (1 << i)) {
    bool flag = true;
    REP(j, N + 1) {
    if (!(bit & (1 << j)) && j != w && j != i && !left(a[w], a[i], a[j]) ) flag = false; // (w - i - 현재까지 사용한 점)이 strict 왼쪽꺾임이 아닌 경우 더 이상 진행하지 않으면 되므로, flag = false;
    }
    if (flag) ret >?= go(w, i, bit - (1 << i)) + 1; // >?=는 ret = max(ret, go(w, i, bit - (1 << i)) + 1) 과 같습니다. ㅠㅠ
    }
    }
    return (table[q][w][bit] = ret);
    }
    int longestSpiral(vector points) {
    memset(table, -1, sizeof(table));
    N = sz(points);
    a.resize(N + 1);
    REP(i, N) {
    istringstream sin(points[i]);
    sin >> a[i].x >> a[i].y;
    }
    a[N] = Point(0, 0); // N번째 점은 (0,0)
    int ret = 0;
    REP(i, N)
    ret >?= go(N, i, (1 << N) - 1 - (1 << i)) + 1; // N-i로 시작
    return ret;
    }
    };

    [/spoiler]
    <div>[이 글은 과거 홈페이지에서 이전된 글입니다. <a href="http://algospot.andromeda-express.com/zbxe/editorial/2567">원문보기</a>]</div>

    17년 전
5개의 댓글이 있습니다.
  • Toivoa
    Toivoa

    나도 Template + Plug-in 쓰면 250 fastest 할 수 있을까? :|


    17년 전 link
  • 하나반
    하나반

    한국사람들 순위만 조회할 수 있는 방법이 있나요? 랭킹 어떤 방법으로 뽑으셨는지 궁금합니다.


    17년 전 link
  • JongMan
    JongMan

    에디토리얼 짱성실함;;;; 만세


    17년 전 link
  • JongMan
    JongMan

    템플릿만 써도 충분해 ㅋㅋㅋㅋ


    17년 전 link
  • astein
    astein

    http://felix-halim.net/tc/index.php?rd=10659 을 이용하시면 됩니다 'ㅁ'


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