221개의 댓글이 있습니다.
  • hyunhwan
    hyunhwan

    총 85개의 팀이 본선에 진출했고, 예년에 비해 상대적으로 많은 외국 학교가 참가를 한 상황입니다.


    1년 전 link
  • hyunhwan
    hyunhwan

    제가 확인한 간단한 해외팀 소개입니다:
    joisndra@Kyoto University - 2016 츠쿠바 대회 22위
    LLL@Peking University - 2015 창춘 대회 4위
    575.cpp@University of Aizu - 2016 츠쿠바 대회 4위


    1년 전 link
  • hyunhwan
    hyunhwan

    참고로 575.cpp팀은 작년 WF 참가 경험이 있습니다.


    1년 전 link
  • hyunhwan
    hyunhwan

    현장 특파원을 통해 입수된 현재 대회장 사진입니다. 팀들이 속속 자리에 앉고 있는것 같고, 올해 선수 유니폼은 검은색인 것 같습니다.


    1년 전 link
  • hyunhwan
    hyunhwan

    풍선수로 봤을 때 전년과 동일하게 12문제가 출제될 것 같습니다.


    1년 전 link
  • hyunhwan
    hyunhwan

    2분 남았습니다.


    1년 전 link
  • hyunhwan
    hyunhwan

    그리고 https://algospot.slack.com/ 접속하시면 아마도 실시간으로 관전하시는 회원분들과 이야기도 나누실 수 있을 것 같습니다.


    1년 전 link
  • wookayin
    wookayin

    대회가 시작되었습니다!

    스코어보드(Spotboard) 주소: https://contest.icpckorea.org/spotboard/


    1년 전 link
  • hyunhwan
    hyunhwan

    스코어보드를 봤을 때 정시에 시작한 것 같네요. 예전 경험으로는 보통 지연되는 경우가 많았는데, 좋은 현상입니다.


    1년 전 link
  • hyunhwan
    hyunhwan

    현재까지 제출이 없는 것으로 보아, 쉽게 푸는 문제가 없거나, 혹은 쉬운 문제의 순서 배치가 중간즈음에 있어 찾지 못하고 있는 것 아닌가 하고 생각되네요.


    1년 전 link
  • hyunhwan
    hyunhwan

    혹시 순위표가 업데이트가 아니되는 것일 수도 있겠네요. 아직 문제는 외부에 공개되지 않은 상황입니다.


    1년 전 link
  • koosaga
    koosaga

    G 풀렸어요


    1년 전 link
  • hyunhwan
    hyunhwan

    7분에 첫 AC를 ACGTeam(서울대학교)가 가져갑니다.


    1년 전 link
  • hyunhwan
    hyunhwan

    Is this hard mode?(KAIST)팀은 다른팀과 다르게 I를 풀었네요.


    1년 전 link
  • hyunhwan
    hyunhwan

    이번 스팟 보드는 각 문제 별 first run에 대해서 표시를 달리 해주는 것으로 보입니다.


    1년 전 link
  • hyunhwan
    hyunhwan

    PLEASE OPEN TESTDATA(서울대학교)팀은 L을 풀었네요.


    1년 전 link
  • hyunhwan
    hyunhwan

    드디어 문제 공개되었습니다: http://icpckorea.org/2016/REGIONAL/problemset-2016.pdf


    1년 전 link
  • hyunhwan
    hyunhwan

    ACGTeam팀 B번 제출했으나 실패


    1년 전 link
  • hyunhwan
    hyunhwan

    중계진의 문제 평입니다:

    ainu7 [20:12]

    어려워서 하나도 모르겠다


    1년 전 link
  • hyunhwan
    hyunhwan

    Hello World Final!(서울대학교) 2문제 해결하면서 1위로 순위 상승합니다.


    1년 전 link
  • hyunhwan
    hyunhwan

    ACGTeam B번 성공하였으나 방금 받은 오답으로 인해 2위 기록합니다.


    1년 전 link
  • hyunhwan
    hyunhwan

    스팟보드 제작자이신 wookyain님께서 팁을 하나 알려주시네요.

    wook [20:15]

    https://contest.icpckorea.org/spotboard/?time=N 하면 N분째의 스탠딩이 보여용


    1년 전 link
  • Doju
    Doju

    C번 문제는 1차원 직선 상에 k(10만 이하) 종류 중 하나의 타입의 부품을 생산하는 n(100만 이하) 개의 공장이 주어질 때, 임의의 위치에 집을 지어서 모든 타입의 부품을 공급받고자 할 때 가장 먼 공장까지의 거리를 최소로 하는 문제입니다. (이 때 집을 지어야 하는 위치 출력)


    1년 전 link
  • functionx
    functionx

    L번 문제는 이진 트리에서 처음에 루트 노드가 감염된 상태에서 1초에 하나씩 노드를 보호할 수 있고, 감염된 노드는 1초에 하나씩 이웃한 노드에 감염시킬 때, 감염되는 노드의 최솟값을 구할 수 있는 문제입니다.

    이 문제는 동적계획법을 이용하여 O(N)으로 풀 수 있습니다.


    1년 전 link
  • koosaga
    koosaga

    F는 수직선 상에 빌딩 (구간을 차지하며 높이가 있는) N개와 반직선 Q개가 주어질 때, 반직선과 가장 먼저 충돌하는 빌딩의 index를 찍는 문제입니다. 작년 대전 g문제랑 비슷한 느낌이 나네요


    1년 전 link
  • Doju
    Doju

    좌표순 정렬해 놓고 two pointers 로 구간 잡고 구간 내 타입별 갯수 갱신해 가면서 풀면 될 것 같습니다


    1년 전 link
  • Doju
    Doju

    (C)


    1년 전 link
  • VOCList
    VOCList

    A번 문제는 n = 100000 planar graph에서 한 개의 엣지가 부서져도 모든 정점이 연결되어 있기 위해 추가로 놓아야 하는 엣지의 수입니다. 이 때 추가로 놓이고 나서도 planar graph여야 합니다.


    1년 전 link
  • VOCList
    VOCList

    m <= 3 * n 정도


    1년 전 link
  • hyunhwan
    hyunhwan

    scoreboard@00:18
    5팀이 2문제를 해결했는데, 조합이 서로 다른 기이한 광경을 확인하실 수 있습니다.


    1년 전 link
  • hyunhwan
    hyunhwan

    scoreboard@00:20
    총 3팀이 세문제를 해결하였습니다.


    1년 전 link
  • koosaga
    koosaga

    A번 엄청나보이네요.. planar graph라


    1년 전 link
  • functionx
    functionx

    I번 문제는 (0,0)에서 오른쪽을 보는 로봇에 이동 명령과 90도 회전 명령을 할 때 (0~N,0~N)을 벗어나는지, 벗어나지 않으면 최종 위치를 출력하는 문제입니다.

    이 문제는 간단한 구현으로 풀 수 있습니다.


    1년 전 link
  • functionx
    functionx

    ACG가 4문제로 1등을 올라갑니다!


    1년 전 link
  • hyunhwan
    hyunhwan

    scoreboard@00:22

    ACGTeam 4문제 해결 후 1위로 올라섭니다. 하지만 아까 받은 패널티로 인해 1위를 쉽게 빼앗길 수 있습니다.


    1년 전 link
  • functionx
    functionx

    G번 문제는 격자의 위쪽에서 아래쪽까지 상하좌우로 이동하면서 1을 지나지 않는 경로가 있는지 확인하는 문제입니다.

    이 문제는 간단한 Flood-Fill 문제로 빨리 풀릴 것 같군요.


    1년 전 link
  • joinsung
    joinsung

    B는 축구 리그의 결과가 맞는지를 판단하는 문제입니다. n팀이 1:1로 매치를 하는데 승리팀이 승점 1점을 받습니다. n팀의 승점이 n개의 숫자로 주어질 때, 이것이 valid하면 1, 그렇지 않으면 -1을 출력합니다.


    1년 전 link
  • mjy0503
    mjy0503

    E번 문제는 주어진 수식을 2진 트리로 표현했을 때, 겹치지 않는 가장 큰 공통 subtree를 찾는 문제입니다.
    n <= 1000이라 각 subtree에 대한 hash를 이용해 풀 수 있겠네요.
    관건은 parsing을 얼마나 잘하느냐로 보입니다.


    1년 전 link
  • functionx
    functionx

    GoBack 팀이 B를 풀어서 1등으로 올라갑니다!


    1년 전 link
  • koosaga
    koosaga

    D번 bipartite maximum independent edge set에 대해서 언급하고 있는데 bipartite matching을 적당히 꼰거 같군요. 으 길어요


    1년 전 link
  • hyunhwan
    hyunhwan

    score@00:25
    하지만 GOBACK팀이 4문제 해결하며 ACGTeam을 뒤로 보냅니다.


    1년 전 link
  • koosaga
    koosaga

    D번 열심히 읽었는데 그냥 max matching + independent set 찍는 문제인거 같아요. nm <= 10^8이니 쉽네요


    1년 전 link
  • hyunhwan
    hyunhwan

    처음 언급했던 일본 아이즈 대학의 575.cpp는 B번을 잡고 돌돌 말리고 있는 것 같습니다. 0문제 팀들 중에서 B번을 시도했으나 실패한 경우가 많이 보이네요.


    1년 전 link
  • Doju
    Doju

    Nooglers+1 팀에서 K를 첫 제출합니다


    1년 전 link
  • Doju
    Doju

    틀리네요 ㅠㅠ


    1년 전 link
  • koosaga
    koosaga

    wa ㅠㅠ


    1년 전 link
  • hyunhwan
    hyunhwan

    B번의 경우에는 함정이 있는 것 같습니다.


    1년 전 link
  • koosaga
    koosaga

    A번 모든 정점들이 원호상에 있는 planar graph인데 중요한 조건일 거 같아요.


    1년 전 link
  • functionx
    functionx

    H번 문제는 그래프에서 몇 개의 에너지를 생성하는 노드에서 나머지 노드로 에너지를 전달할 수 있는지 구하는 문제입니다.
    각 노드는 에너지를 생성하는 노드(source)와 에너지를 받는 노드(sink)가 있고 에너지의 생산량과 소비량이 주어져 있습니다. 또 각 에지의 가중치는 최대 유량을 의미합니다.
    주의해야 할 점은 각 노드들은 2개 이상의 source 노드로부터 에너지를 받을 수 없습니다.

    이 문제는 MCMF 문제로 변환하여 풀릴 것 같군요.


    1년 전 link
  • Doju
    Doju

    풍선팀과 575 팀이 C를 제출합니다


    1년 전 link
  • Doju
    Doju

    하지만 둘 다 틀리네요..


    1년 전 link
  • VOCList
    VOCList

    J번 500000개의 정수좌표 점이 주어지는데 한 x 좌표에는 최대 한 점만이 존재합니다. x/y axis parallel한 선분들을 그어 점을 모두 포함하는 심플 폴리곤을 만들려 하는데, 각각의 점을 hori / verti 하게 선분이 지나쳐야 함이 주어집니다. 폴리곤 선분의 전체 길이를 구하세용.


    1년 전 link
  • hyunhwan
    hyunhwan

    생각되는 경우는 N-1번 매치를 치루지 않아도 승점이 유지되는 경우에 valid라고 출력해서 오답을 받는 것은 아닐까 하고 추측해봅니다.


    1년 전 link
  • Doju
    Doju

    테케팀이 B를 제출했지만 틀렸네요 ㅠ


    1년 전 link
  • Doju
    Doju

    LipCoding 팀은 꾸준히 A를 제출하고 있습니다


    1년 전 link
  • Doju
    Doju

    하지만 틀리네요 ㅠㅠ


    1년 전 link
  • Doju
    Doju

    쀼쀼삐쀼삐 팀이 B를 제출 - 맞아서 3등으로 올라갑니다


    1년 전 link
  • functionx
    functionx

    H번 문제는 Source 노드에서 에너지를 주는 노드로 (유량=각 노드의 가중치, cost=-inf)를 에지로 만들고 일반 에지는 cost가 1인 에지 2개(정방향, 역방향)를 만들고, 에너지를 받는 노드에서 Sink 노드로 (유량=각 노드의 가중치, cost=-inf)를 에지로 만들어서 MCMF를 돌리면 될 듯 합니다.


    1년 전 link
  • Doju
    Doju

    NTU C 제출


    1년 전 link
  • VOCList
    VOCList

    연세대 14등 힘내라 ㅜㅜ


    1년 전 link
  • Doju
    Doju

    틀림 ㅠㅠ


    1년 전 link
  • hyunhwan
    hyunhwan

    하지만 NTU C는 정답을 받지 못하네요.


    1년 전 link
  • Gravekper
    Gravekper

    힘내라 거품목욕!


    1년 전 link
  • Doju
    Doju

    575가 C랑 I를 동시에 제출합니다


    1년 전 link
  • VOCList
    VOCList

    Aizu 40분째 0솔브인데 여기 월파팀인거로.. 무슨일이 있는건가요 ㅜㅜ


    1년 전 link
  • Doju
    Doju

    둘 다 틀립니다. 부스터 팀도 C를 틀렸는데 생각보다 어려운 문제일까요?


    1년 전 link
  • hyunhwan
    hyunhwan

    ACGTeam C번 시도하네요.


    1년 전 link
  • Doju
    Doju

    C가 풀렸습니다. 다행이네요.


    1년 전 link
  • hyunhwan
    hyunhwan

    맞았습니다!


    1년 전 link
  • hyunhwan
    hyunhwan

    scoreboard@00:43
    ACGTeam이 다른 문제를 잡느라 제출이 없더라도 당분간 1위 탈환은 없을 것으로 보이는 상황입니다.


    1년 전 link
  • Doju
    Doju

    하드모드 팀이 B를 맞고 4등으로 올라옵니다.


    1년 전 link
  • functionx
    functionx

    F번 문제는 땅에 붙어있는 직사각형 형태의 N개의 빌딩이 주어지고 K개의 반직선이 주어질 때 각 반직선이 가장 먼저 만나는 빌딩의 번호를 구하는 문제입니다.

    이 문제는 일단 계산기하 문제이니, 나중에 시도될 듯 싶군요.


    1년 전 link
  • koosaga
    koosaga

    AFHJK 아직 결론 안난거 같네요. 맞나요?

    D는 곧 풀릴 거 같고, E는 risk가 커서 잘 모르겠는데 결국엔 풀리지 않을까 싶네요


    1년 전 link
  • Doju
    Doju

    NTU가 B가 아니라 C를 풀고 4문제를 달성합니다.


    1년 전 link
  • functionx
    functionx

    F번 문제 조건에 의하면 반직선의 시작점은 건물들의 최대높이보다 크고 y좌표 증가량은 음수입니다.
    또한, 빌딩들은 서로 교차하지 않습니다.


    1년 전 link
  • hyunhwan
    hyunhwan

    오 NTU C번 Yes


    1년 전 link
  • Doju
    Doju

    575가 I를 맞습니다. 클라이밍인지 아닌지..


    1년 전 link
  • 꿀호떡
    꿀호떡

    C에서 꽤 많이들 나가네요 음...


    1년 전 link
  • Doju
    Doju

    근데 이 게시판 왜 댓글 달 때마다 GET 인자가 증식하나요


    1년 전 link
  • Doju
    Doju

    월파팀이 C 맞고 5문제 2등이 됩니다


    1년 전 link
  • functionx
    functionx

    헬로월파 팀이 C를 풀어서 2등으로 올라갑니다.


    1년 전 link
  • koosaga
    koosaga

    헬로월파 vs ACG 매우 기대하고 있습니다


    1년 전 link
  • Doju
    Doju

    G I L 다음에 잡을 만한 문제가 B C 인 거 같은데 NO 비율이 엄청 높네요. 우울한 대회입니다 ㅠㅠ


    1년 전 link
  • Doju
    Doju

    ACG H 제출!


    1년 전 link
  • hyunhwan
    hyunhwan

    @Doju 댓글 작성 후 포커싱을 GET을 이용해서 하기 때문에 그런 것으로 추측됩니다.


    1년 전 link
  • Doju
    Doju

    ㅠㅠ


    1년 전 link
  • hyunhwan
    hyunhwan

    H는 오답 판정되었습니다.


    1년 전 link
  • koosaga
    koosaga

    ACG가 H를 냈는데 굉장히 의외의 선택인거 같네요. 일단 틀렸습니다.


    1년 전 link
  • Doju
    Doju

    @hyunhwan 근데 포커싱 안 되고 그냥 페이지 맨 위로 가요 ㅠㅠ Windows 10, Firefox 49.0.2 쓰고 있습니당


    1년 전 link
  • Doju
    Doju

    혜아팀이 D 제출!


    1년 전 link
  • hyunhwan
    hyunhwan

    hYEAHyea D시도합니다.


    1년 전 link
  • Doju
    Doju

    혜아팀 D WA, 쀼쀼삐팀 C WA ㅠㅠ 5문제의 벽이 높군요


    1년 전 link
  • hyunhwan
    hyunhwan

    @Doju저도 그런 현상이 있네요. 누군가 고쳐주실거에요. 알고스팟 pull-request는 누구에게나 열려있습니다! https://github.com/jongman/algospot


    1년 전 link
  • hyunhwan
    hyunhwan

    scoreboard@01:13

    어느덧 한 시간이 지났네요.


    1년 전 link
  • koosaga
    koosaga

    K번에서는 N * M 표가 주어지고 row 합 column 합이 주어집니다. 주어지는 숫자가 실수면 ceil(x) / floor(x)로 rounding해서 정수로 만들어야 하고, 모든 rounding을 했을 때 consistent한 표가 존재하는 지를 찍고 있으면 그 표의 상태까지 찍어야 합니다.


    1년 전 link
  • hyunhwan
    hyunhwan

    고려대 Never Give Up 5문제로 3위!


    1년 전 link
  • Doju
    Doju

    Never Give Up 팀 C 맞고 3등으로 올라갑니다!


    1년 전 link
  • functionx
    functionx

    Never Give Up 팀이 C를 맞아서 3등으로 올라갑니다.


    1년 전 link
  • koosaga
    koosaga

    row 합과 column 합이 유동적이어서 상당히 어려운거 같습니다. 더 쉬운 풀이가 있는지는 잘 모르겠지만, 예선 H에 나왔던 L-R maxflow로는 확실히 풀 수 있는 문제인 거 같네요. 공부를 열심히 한 자!


    1년 전 link
  • Doju
    Doju

    연대 팀 C 맞고 3등!


    1년 전 link
  • hyunhwan
    hyunhwan

    3위 경쟁이 치열하네요! ACGTeam다시 H제출!


    1년 전 link
  • Doju
    Doju

    테케팀은 C를 4번만에 맞고 12등이 됩니다. (편파응원)


    1년 전 link
  • etaehyun4
    etaehyun4

    ACG가 H를 맞았네요


    1년 전 link
  • hyunhwan
    hyunhwan

    맞았습니다! 6문제!


    1년 전 link
  • koosaga
    koosaga

    ACG H! 진짜 대단하네요


    1년 전 link
  • etaehyun4
    etaehyun4

    hYEAHyea D 제출!


    1년 전 link
  • etaehyun4
    etaehyun4

    D를 맞춰서 4등으로 올라갑니다!


    1년 전 link
  • functionx
    functionx

    HyeahYEA 팀이 D를 풀어서 5문제로 올라갑니다!


    1년 전 link
  • hyunhwan
    hyunhwan

    개인적으로 E번이 지저분해 보이지만, 뭔가 쉬워보이는거 같은데 아직 아무도 안건들고 있네요. 수식에 대한 Tree를 만든 다음, largest common subexpression을 찾는 문제인데 제약 조건이 잘 걸려 있어서 크게 무리 없이 정답을 맞을 수 있지 않을까 합니다.


    1년 전 link
  • Doju
    Doju

    NTU가 H를 제출했지만 틀립니다 ㅠ


    1년 전 link
  • hyunhwan
    hyunhwan

    다시 읽어보니 생각보다는 쉽지는 않네요. 물론 트리를 만드는 것은 쉽습니다.


    1년 전 link
  • VOCList
    VOCList

    연세대학교 C를 풀면서 3등으로 올라갑니다!


    1년 전 link
  • hyunhwan
    hyunhwan

    개인적으로 AC_FROM_ZZAM 이 팀명 마음에 드네요. (참고자료)


    1년 전 link
  • 꿀호떡
    꿀호떡

    KAIST 선두가 뒤집혔네요.


    1년 전 link
  • 꿀호떡
    꿀호떡

    Hello World Final팀 K 도전


    1년 전 link
  • functionx
    functionx

    헬로월파팀 K 풀어서 2등으로 올라갑니다!


    1년 전 link
  • hyunhwan
    hyunhwan

    성공!


    1년 전 link
  • 꿀호떡
    꿀호떡

    hyunhwan님이 고대하시던 E 서브밋!


    1년 전 link
  • Doju
    Doju

    테케팀이 E 퍼솔을 먹습니다


    1년 전 link
  • functionx
    functionx

    PLEASE OPEN TESTDATA팀이 E번 문제를 풀었습니다!


    1년 전 link
  • 꿀호떡
    꿀호떡

    90분 시점에 AFJ를 제외한 모든 문제가 풀렸네요


    1년 전 link
  • hyunhwan
    hyunhwan

    PLEASE OPEN TESTDATA팀 E을 맞고 7등으로 올라갑니다.


    1년 전 link
  • wookayin
    wookayin

    Scoreboard @ 90 min

    90분 상황입니다. SNU-SNU-Kaist-Yonsei-KAIST-Korea 순입니다.
    6문제 2팀, 5문제팀은 5팀이네요!


    1년 전 link
  • hyunhwan
    hyunhwan

    ACGTeam K성공!


    1년 전 link
  • functionx
    functionx

    ACG팀이 K를 풀었습니다!


    1년 전 link
  • VOCList
    VOCList

    K는 엣지를 2개로 쪼개서 미니멈 플로우를 보장하는 방향으로 풀면 되지 않을까 싶네요


    1년 전 link
  • functionx
    functionx

    NTU 팀이 H를 풀었습니다!


    1년 전 link
  • koosaga
    koosaga

    H는 그리디인 것 같습니다. capacity = inf 라고 생각했을 때, 리프부터 올라가면서 문제를 해결해서, supply 1개 조건과, 합 >= 0 조건을 만족하면서 최대한 루트까지 올리는 형식으로 탐욕적으로 해결합니다. 이렇게 생각하면 capacity가 생겨도 크게 달라지는 건 없는 거 같습니다. 관건은 서브트리의 그리디를 합쳐주는 쪽이 될 거 같은데 sorting 선에서 해결될 거 같아요


    1년 전 link
  • hyunhwan
    hyunhwan

    대회시 제공되는 점심 사진입니다! 김밥은 항상 보이는거 같네요.


    1년 전 link
  • koosaga
    koosaga

    AFJ는 결론이 안났네요


    1년 전 link
  • 꿀호떡
    꿀호떡

    B는 하도 많이들 틀려서 정체가 뭔지 궁금하네요(..) 정렬하면 대충 풀릴줄 알았는데!


    1년 전 link
  • koosaga
    koosaga

    D랑 K가 둘다 2명이라니 역시 워딩의 중요성...


    1년 전 link
  • 꿀호떡
    꿀호떡

    575.cpp: "이러려고 한국까지 왔나... 자괴감 들고 괴로워"


    1년 전 link
  • Doju
    Doju

    유니스트 고슴도치 팀이 C를 제출합니다. 6문제 갈 수 있을까요?


    1년 전 link
  • Doju
    Doju

    틀리네요 ㅠ


    1년 전 link
  • mjy0503
    mjy0503

    ACG D 맞아서 8문제가 됩니다!


    1년 전 link
  • Doju
    Doju

    ACG가 D를 맞고 2등과 2문제 차이를 벌립니다!


    1년 전 link
  • hyunhwan
    hyunhwan

    ACGTeam 8문제!


    1년 전 link
  • Doju
    Doju

    테케팀 D 맞고 3등!


    1년 전 link
  • Doju
    Doju

    B를 안 풀고 D와 E를 푸는 이색적 행보를 보여줍니다


    1년 전 link
  • hyunhwan
    hyunhwan

    scoreboard@01:50
    1등부터 3등까지 서울대학교팀들이 차지하고 있는 상황입니다.


    1년 전 link
  • Doju
    Doju

    혜아팀이 H를 맞춥니다. 이제 저 팀은 A랑 E가 남았네요


    1년 전 link
  • Doju
    Doju

    (닉값 얘기)


    1년 전 link
  • 꿀호떡
    꿀호떡

    (중계석에서 A를 얼추 밝혀낸 분위기인데....)


    1년 전 link
  • Doju
    Doju

    NTU가 B를 풀고 6문제 대열에 합류합니다. 5등


    1년 전 link
  • 꿀호떡
    꿀호떡

    @koosaga @functionx A 해법 써주세요 ㅇㄲㄴㅇㄲㄴ


    1년 전 link
  • Doju
    Doju

    대회 시작 2시간 지났습니다.
    현재 1등 ACG가 8문제 - BCDGHIKL
    그 아래 6문제 팀이 4개 - 월파, 테케, hyea, NTU
    6문제 팀은 GIL 공통이고, 각각 BCK, CDE, BDH, BCH 를 풀었습니다.
    테케팀은 아직까지 E를 푼 유일한 팀입니다.


    1년 전 link
  • koosaga
    koosaga

    functionx님이 A 풀이를 찾으신 것 같습니다.

    일단은 lemma 하나가 있는데, 새로 추가하는 간선들은 polygon 상에서 인접한 두 점을 이어야 합니다. (i - i+1 처럼) lemma에 대한 명확한 증명은 없는데, 다만 직관적으로 이해할 수 있는 부분이라고 생각합니다.

    i - i+1 에지가 이어지지 않았다면, 일단 잇고 생각합시다. 이 에지들을 이었을 때 생기는 영역들로 Dual Graph를 구성합니다. Dual Graph는 영역을 정점으로 하고, 그래프 상에 존재하는 bridge (bridge 아니면 무시) 를 간선으로 합니다.

    삼각분할을 생각해 보면 Dual Graph가 forest임은 자명합니다. 또한 각각의 정점 영역들은 임의의 i - i+1을 이은 선과 일대일 대응됩니다. 또한, 몇개의 bridge는 하나의 정점 영역에 의존적이기 때문에, 어떠한 선들은 무조건 이어져야만 합니다.

    이제 문제는 Minimum Vertex Cover로 환원됩니다. 그래프가 있고, 어떠한 정점들은 선택해야만 하고 (정점 영역에 의존적인 bridge가 있다면), 그 조건을 만족하면서 모든 에지(bridge)를 덮어야 합니다. 이는 DP로 풀 수 있습니다.

    문제 삼을만한 부분은 맨위 lemma 파트인거 같은데 저도 직관적이라고 생각합니다. 아름다운 문제네요...


    1년 전 link
  • Doju
    Doju

    Never Give Up과 Master Spark 가 동시에 H 제출


    1년 전 link
  • koosaga
    koosaga

    어려운 문제지만 팀들이 잘 해서 한두팀 정도는 풀수 있지 않을까 싶네요. F 고민하러 갑니다...


    1년 전 link
  • Doju
    Doju

    하지만 연부팀만 맞아서 6문제 5등으로 올라갑니다


    1년 전 link
  • Doju
    Doju

    초반에 A 퍼솔을 노리다 실패하던 LipCoding 팀은 침착하게 5문제까지 올라섭니다. C 대신 H를 풀었네요.


    1년 전 link
  • koosaga
    koosaga

    functionx님이 lemma 증명 가능하다고 하시네요. 귀류법으로 최적해가 인접하지 않다고 치면, 문제 조건을 만족하는 선에서 그렇게 이을 수 있는 경우가 3개 정도 나온다고 합니다. 그 경우 모두 인접한 경우로 최적해를 수정할 수 있다고 합니다.


    1년 전 link
  • functionx
    functionx

    아직 네 팀이 0문제에서 헤어나지 못하고 있네요. ㅜㅜ (2팀은 불참) 이 팀들이 AC를 받을 수 있도록 응원해줍시다!


    1년 전 link
  • koosaga
    koosaga

    BCDGHIL을 받아낸 팀이 아직 ACG밖에 없군요


    1년 전 link
  • Doju
    Doju

    현재 해외팀 상황을 보면
    NTU 6문제 6등
    NCTU 4문제 19등
    홍콩 4문제 28등
    575 4문제 33등
    교토 3문제 37등
    북경 아마도 No show (한 명이 비자 문제로 못 왔다는 말이 있었습니다)

    외침은 큰 문제 없이 방어될 거 같습니다


    1년 전 link
  • koosaga
    koosaga

    aizu 눈물의 b ㅠㅠㅠ


    1년 전 link
  • Doju
    Doju

    카이스트 하드모드 팀 K 맞고 3등으로 올라섭니다. 아직까지 WA를 맞지 않았어요 ㄷㄷ


    1년 전 link
  • Doju
    Doju

    hyea 팀이 질세라 C를 제출하지만 틀립니다 ㅠ


    1년 전 link
  • functionx
    functionx

    Never Give Up 팀이 H번을 맞았습니다!


    1년 전 link
  • koosaga
    koosaga

    하드모드 vs 혜아도 재밌게 볼 수 있을거 같네요


    1년 전 link
  • koosaga
    koosaga

    6문제에서 다들 진전이 없네요 ㅠㅠㅠ


    1년 전 link
  • Doju
    Doju

    Never Give Up F 제출!


    1년 전 link
  • 꿀호떡
    꿀호떡

    동국대랑 숙대팀이 I를 풀었네요. 이제 0문제팀 2팀 남았어요.


    1년 전 link
  • Doju
    Doju

    틀렸네요 ㅠㅠ


    1년 전 link
  • Doju
    Doju

    월파팀 H 제출!


    1년 전 link
  • Doju
    Doju

    H 맞고 드디어 7문제가 생깁니다!


    1년 전 link
  • Doju
    Doju

    테케팀 드디어 B 제출!


    1년 전 link
  • Doju
    Doju

    맞추고 7문제로 따라붙습니다!


    1년 전 link
  • Doju
    Doju

    유니스트 고슴도치 팀 H 제출했지만 틀립니다 ㅠㅠ


    1년 전 link
  • etaehyun4
    etaehyun4

    0문제 팀이 No Show 팀을 제외하고 1팀 남았습니다. 부산외대 화이팅!


    1년 전 link
  • koosaga
    koosaga

    F : 이보다 좋은 솔루션이 있는지는 모르겠는데 제 솔루션은 sqrt-decomposition입니다.

    편의상 몇가지 가정을 하겠습니다. 이 가정을 넣어도 큰 차이는 없습니다.

    1. 모든 meteor는 x축 증가 방향으로 떨어진다
    2. 건물을 높이 있는 수직선 두개로 쪼개 생각하고, 수평선을 지운다

    조금만 생각해 보시면 저 조건을 넣어도 큰 차이가 없음을 알 수 있습니다. 코드는 늘어나지만..

    쿼리를 B개 씩 묶어서 처리합니다. 쿼리는 모두 하늘 위에서 떨어지니까 반직선을 x = -inf에서 오는 직선으로 처리할 수 있습니다.

    이제 sweep line을 사용해서 x좌표를 증가시킵니다. 쿼리로 들어오는 직선들의 y축 order를 관리하면서 sweep line을 유지할 것입니다. 이를 관리하기 위해서 초기 B^2 개의 event를 만들어서 x축 순으로 정렬합니다. 이제

    • sweep line이 빌딩을 만나면, y order가 작은거 pop
    • sweep line에서 쿼리 두개가 만나면, swap

    Q/B(N + B^2lgB) = NQ/B + QBlgB = N(QlgQ)^0.5 입니다. 교차점 정렬이 걸리는데, B^2/2 개고 sorting이니까 나오겠죠...?


    1년 전 link
  • functionx
    functionx

    F번 문제 온라인으로도 풀 수 있습니다! 이러면 O(Q log^2 N)이 될 것으로 보이는군요.

    각 메테오에 대해서 parametric search를 이용해서 답을 찾습니다. 왼쪽으로 움직이는 메테오에 대해서, 그 메테오보다 X좌표가 낮은 부분이 있는 가장 오른쪽 빌딩 Y를 구한 후 X를 조절하면서 메테오가 빌딩 X~Y 중 하나와 부딪히는지 체크합니다. 이는 convex hull을 indexed tree에 저장한 후, 메테오의 시작점에서 X~Y 범위의 빌딩으로 접선을 그어서 그 기울기가 메테오의 기울기보다 작은 지 체크해주는 방식으로 하면 됩니다. (접선의 기울기를 구하는 것이 O(log^2 N))
    그냥 이분검색을 사용하면 O(log^3 N)이 되지만, 인덱스트리의 특징을 이용하면 이를 O(log^2 N)으로 줄일 수 있습니다.


    1년 전 link
  • Doju
    Doju

    테케팀 H 맞추고 8문제 2등!


    1년 전 link
  • koosaga
    koosaga

    풀이 뭔진 모르겠지만 제 풀이가 맞으면 안풀릴듯... 1초 tl이 걸리네요. 교차점 정렬에 대해서 조금 더 생각해 봐야겠습니다


    1년 전 link
  • functionx
    functionx

    X~Y 범위의 빌딩 : X~Y 범위의 빌딩들의 convex hull


    1년 전 link
  • wookayin
    wookayin

    Scoreboard @ 168 min.

    TESTDATA 팀이 H를 풀고 8문제가 되어 Hello WF 팀을 추월합니다.. SNU 3팀 - KAIST 2팀 - POSTECH - 고대 순으로 이어지네요


    1년 전 link
  • 샥후
    샥후

    F는 건물을 선 두개로 보고 별을 각도순으로 정렬해서 푸는 문제로 보이네요 J는 그냥 자료구조문제...


    1년 전 link
  • koosaga
    koosaga

    functionx님 풀이가 저보다 낫네요 ㅠㅠ


    1년 전 link
  • Doju
    Doju

    월파팀 D 맞추고 8문제 2등! 8문제 팀이 3팀이 됩니다.


    1년 전 link
  • Doju
    Doju

    hyea 팀은 3번 틀렸던 C를 다시 제출합니다


    1년 전 link
  • Doju
    Doju

    하지만 ㅠㅠ


    1년 전 link
  • hyunhwan
    hyunhwan

    9문제!


    1년 전 link
  • wookayin
    wookayin

    ACGTeam 이 J를 맞추고(ㄷㄷㄷ) TESTDATA 팀도 K를 맞아서 195분 현재, 9문제 두팀입니다. 그 뒤로 8, 7, 6, 6, 6, ...


    1년 전 link
  • etaehyun4
    etaehyun4

    모든 팀이 1문제 이상을 풀었습니다!


    1년 전 link
  • hyunhwan
    hyunhwan

    scoreboard@03:29
    개인적으로는 ACGTeam이 유리해보이네요. 그리고 ACGTeam A번 제출합니다.


    1년 전 link
  • hyunhwan
    hyunhwan

    하지만 실패


    1년 전 link
  • koosaga
    koosaga

    밥먹고 들어왔더니 frozen!


    1년 전 link
  • VOCList
    VOCList

    3:32 기준으로 프리즈된 것 같은 기분이 드네요


    1년 전 link
  • VOCList
    VOCList

    간간히 박수소리도 들리고~


    1년 전 link
  • hyunhwan
    hyunhwan

    scoreboard@03:39

    생각보다 이른 시간에 스코어보드 갱신이 중단되었습니다. 아마도 ACGTeam의 A번이 정답인것으로 판단되어 중단하기로 결정한 것 아닌가 싶습니다. 현재는 채점 대기중으로만 떠있습니다.


    1년 전 link
  • VOCList
    VOCList

    E번 + 1로 11개 선에서 끝나지 않을까 조심스레 던져봅니다.


    1년 전 link
  • VOCList
    VOCList

    A번 펜딩 전에 프리징이 되었던 걸로 기억합니다 ㅎ_ㅎ
    재재출의 행방은 과연


    1년 전 link
  • hyunhwan
    hyunhwan

    공개된 내용을 기반한 한국팀들간의 학교별 순위입니다.
    1. ACGTeam @ Seoul National University
    2. hYEAHyea @ KAIST
    3. Master Spark @ Pohang University of Science and Technology
    4. Never Give Up @ Korea University
    5. Real Recognize Real @ Yonsei University
    6. The Hedgehogs @ Ulsan National Institute of Science and Technology
    7. BuzzerBeater @ Soongsil University
    8. HeroesEverDie @ Inha University
    9. Trilobite @ Sogang University
    10. NaHonJaMyWay @ Hanyang University
    11. HISASIBURI @ Kookmin University
    12. CodingMonGO @ Kyung Hee University


    1년 전 link
  • hyunhwan
    hyunhwan

    외국팀을 포함한 학교별 순위입니다.

    1. ACGTeam @ Seoul National University
    2. hYEAHyea @ KAIST
    3. Master Spark @ Pohang University of Science and Technology
    4. Never Give Up @ Korea University
    5. Real Recognize Real @ Yonsei University
    6. MeowiNThebox @ National Taiwan University
    7. The Hedgehogs @ Ulsan National Institute of Science and Technology
    8. 575.cpp @ University of Aizu
    9. BuzzerBeater @ Soongsil University
    10. HeroesEverDie @ Inha University
    11. Trilobite @ Sogang University
    12. NCTU_Radar @ National Chiao Tung University
    13. NaHonJaMyWay @ Hanyang University
    14. joisndra @ Kyoto University
    15. Train_To_Daejeon @ The Chinese University of Hong Kong
    16. HISASIBURI @ Kookmin University
    17. MAZIMAK_IPSE @ Chungbuk National University
    18. CodingMonGO @ Kyung Hee University
    19. Zaranara murymury @ Chung-Ang University
    20. VANSu_gak @ SungKyunKwan University

    1년 전 link
  • hyunhwan
    hyunhwan

    외부에서는 이제 스코어보드를 보는것 외에는 다른게 할게 없네요. 현지에 있는 특파원들의 선전을 기대합니다.


    1년 전 link
  • koosaga
    koosaga

    ACG E는 어떻게 됐는지 잘 모르겠네요. 윤지학이 계속 자리에 있는거 보면 일단 전 회의적입니다. 화이팅 ㅠㅠ


    1년 전 link
  • koosaga
    koosaga

    헬로월파가 F를 내서 놀랐는데 뒷북이었군요..


    1년 전 link
  • koosaga
    koosaga

    ACG 올솔브에 전 한표겁니다


    1년 전 link
  • koosaga
    koosaga

    윤지학이 박수를 쳤다! 근데 아직 제출은 없네요


    1년 전 link
  • koosaga
    koosaga

    헬로월파가 E를 냈네요.


    1년 전 link
  • koosaga
    koosaga

    카이스트 상황이 궁금한데 어떻게 됐는지 모르겠네요. 혜아혜아가 K를 못 푼거 같은데..


    1년 전 link
  • hyunhwan
    hyunhwan

    프리징까지의 해결문제 개수에 대한 팀의 분포를 그래프로 그려봤더니 생각보다 예쁜 분포가 나옵니다.


    1년 전 link
  • VOCList
    VOCList

    30 min left!


    1년 전 link
  • hyunhwan
    hyunhwan

    scoreboard@04:30

    현재 프리징 된 상태에서 제법 노란불이 많이 들어오고 있음을 볼 수 있습니다.


    1년 전 link
  • hyunhwan
    hyunhwan

    문제당 해결팀 숫자에 대한 그래프도 그려봤습니다.

    위의 결과를 토대로 난이도를 구분하자면

    • 쉬운문제: GIL
    • 중간문제: BCD
    • 어려운문제: AEHJK

    정도가 될 것 같습니다. 특히 입상을 노리는 팀이라면, 반드시 BCD는 풀고가야하는 관문으로 보입니다.


    1년 전 link
  • hyunhwan
    hyunhwan

    아래 표의 경우 # solved가 아니라 problems가 맞겠죠.


    1년 전 link
  • hyunhwan
    hyunhwan

    방금 스코어보드로 ACGTeam이 모든 문제를 제출하였음이 확인되었습니다.


    1년 전 link
  • hyunhwan
    hyunhwan

    앞의 그래프에 어려운문제에 F를 빼먹었네요. 추가합니다 @Xhark님 감사!


    1년 전 link
  • VOCList
    VOCList

    그리고 게임 셋인거같다는 찌라시가...


    1년 전 link
  • VOCList
    VOCList

    ACG 만세포즈로 사진을 찍었다는 제보가 있습니다


    1년 전 link
  • hyunhwan
    hyunhwan

    종료되었습니다. 다들 수고하셨습니다!


    1년 전 link
  • hyunhwan
    hyunhwan

    만약 프리징 이후에 냈던 모든 답안이 처음에 맞았다고 가정할 경우에 결과입니다.

    http://imgur.com/a/RQlaf


    1년 전 link
  • hyunhwan
    hyunhwan

    나머지 발표에 대해서는 현장팀에게 부탁을 하고 저는 이만 중계를 마무리하겠습니다. 다들 즐거우셨길!


    1년 전 link
  • VOCList
    VOCList

    스폰서 발표: 넥슨


    1년 전 link
  • VOCList
    VOCList

    전형적인 회사 소개 슬라이드가 흘러흘러갑니다. ㅠㅠ 심심해요


    1년 전 link
  • VOCList
    VOCList

    근무환경 복지 채용지원방법 불라불라


    1년 전 link
  • VOCList
    VOCList

    스폰서 발표: 데브시스터즈


    1년 전 link
  • VOCList
    VOCList

    카이스트 출신의 ICPC 참석 엔지니어. 진로에 대해서 고민하셨던 부분을 공유해 주시는 내용이네용


    1년 전 link
  • wookayin
    wookayin

    현재 시상식 진행중입니다. 생중계


    1년 전 link
  • wookayin
    wookayin

    최종 순위 : http://icpckorea.org/2016/REGIONAL/scoreboard.html

    대상

    • ACGTeam (서울대학교)

    금상

    • hYEAHyea (KAIST)
    • Never Give Up (고려대학교)
    • Real Recognize Real (연세대학교)

    은상

    • Master Spark (POSTECH)
    • The Hedgehogs (UNIST)
    • HeroesNeverDie (인하대학교)

    동상

    • BuzzerBeater (숭실대학교)
    • Trilobite (서강대학교)
    • Zaranara murymury (중앙대학교)
    • NaHonJaMyWay (한양대학교)

    특별상

    • Hello World Final! (서울대학교)
    • MAZIMAK_IPSE (충북대학교)
    • PLEASE OPEN TESTDATA (서울대학교)
    • HISASIBURI (국민대학교)
    • Is this hard mode? (KAIST)
    • SRC (고려대학교)
    • DoongDooRooDaRaDang (부산대학교)
    • Kimchi rains from above (서울대학교)

    1년 전 link
  • 댓글을 남기시려면 로그인하세요.