221개의 댓글이 있습니다.
-
-
hyunhwan -
그리고 https://algospot.slack.com/ 접속하시면 아마도 실시간으로 관전하시는 회원분들과 이야기도 나누실 수 있을 것 같습니다.
7년 전 link
-
-
-
wookayin -
대회가 시작되었습니다!
스코어보드(Spotboard) 주소: https://contest.icpckorea.org/spotboard/
7년 전 link
-
-
-
hyunhwan -
드디어 문제 공개되었습니다: http://icpckorea.org/2016/REGIONAL/problemset-2016.pdf
7년 전 link
-
-
-
hyunhwan -
스팟보드 제작자이신 wookyain님께서 팁을 하나 알려주시네요.
wook [20:15]
https://contest.icpckorea.org/spotboard/?time=N 하면 N분째의 스탠딩이 보여용
7년 전 link
-
-
-
hyunhwan -
scoreboard@00:18
5팀이 2문제를 해결했는데, 조합이 서로 다른 기이한 광경을 확인하실 수 있습니다.
7년 전 link
-
-
-
hyunhwan -
scoreboard@00:20
총 3팀이 세문제를 해결하였습니다.
7년 전 link
-
-
-
hyunhwan -
score@00:25
하지만 GOBACK팀이 4문제 해결하며 ACGTeam을 뒤로 보냅니다.
7년 전 link
-
-
-
hyunhwan -
scoreboard@00:43
ACGTeam이 다른 문제를 잡느라 제출이 없더라도 당분간 1위 탈환은 없을 것으로 보이는 상황입니다.
7년 전 link
-
-
-
hyunhwan -
@Doju저도 그런 현상이 있네요. 누군가 고쳐주실거에요. 알고스팟 pull-request는 누구에게나 열려있습니다! https://github.com/jongman/algospot
7년 전 link
-
-
-
hyunhwan -
scoreboard@01:50
1등부터 3등까지 서울대학교팀들이 차지하고 있는 상황입니다.
7년 전 link
-
-
-
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 파트인거 같은데 저도 직관적이라고 생각합니다. 아름다운 문제네요...
7년 전 link
-
-
-
koosaga -
F : 이보다 좋은 솔루션이 있는지는 모르겠는데 제 솔루션은 sqrt-decomposition입니다.
편의상 몇가지 가정을 하겠습니다. 이 가정을 넣어도 큰 차이는 없습니다.
- 모든 meteor는 x축 증가 방향으로 떨어진다
- 건물을 높이 있는 수직선 두개로 쪼개 생각하고, 수평선을 지운다
조금만 생각해 보시면 저 조건을 넣어도 큰 차이가 없음을 알 수 있습니다. 코드는 늘어나지만..
쿼리를 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이니까 나오겠죠...?
7년 전 link
-
-
-
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)으로 줄일 수 있습니다.
7년 전 link
-
-
-
hyunhwan -
scoreboard@03:29
개인적으로는 ACGTeam이 유리해보이네요. 그리고 ACGTeam A번 제출합니다.
7년 전 link
-
-
-
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
7년 전 link
-
-
-
hyunhwan -
외국팀을 포함한 학교별 순위입니다.
- ACGTeam @ Seoul National University
- hYEAHyea @ KAIST
- Master Spark @ Pohang University of Science and Technology
- Never Give Up @ Korea University
- Real Recognize Real @ Yonsei University
- MeowiNThebox @ National Taiwan University
- The Hedgehogs @ Ulsan National Institute of Science and Technology
- 575.cpp @ University of Aizu
- BuzzerBeater @ Soongsil University
- HeroesEverDie @ Inha University
- Trilobite @ Sogang University
- NCTU_Radar @ National Chiao Tung University
- NaHonJaMyWay @ Hanyang University
- joisndra @ Kyoto University
- Train_To_Daejeon @ The Chinese University of Hong Kong
- HISASIBURI @ Kookmin University
- MAZIMAK_IPSE @ Chungbuk National University
- CodingMonGO @ Kyung Hee University
- Zaranara murymury @ Chung-Ang University
- VANSu_gak @ SungKyunKwan University
7년 전 link
-
-
-
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 (서울대학교)
7년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
hyunhwan
오늘 오전 10시에 KAIST 문지캠퍼스에서 진행되는 ACM-ICPC 대전 리저널 불판입니다!
problemset
scoreboard
대회사이트
7년 전