196개의 댓글이 있습니다.
-
-
lazyboy -
2007년 사건의 요약은 다음과 같습니다:
Director : 동작그만, 부정행위냐?
PUCIT : what?
Director : 지금 judge solution가지고 printf했지, 우리가 빙다리 핫바지로 보이냐
PUCIT : 증거 있어?
Director : 증거? 있지, 이 컴퓨터에는 judge solution이 저장되어 있을 것이여.
PUCIT : 시나리오 쓰고 있네
Director : 어허허허허허허허 이 컴퓨터에 judge solution이 있다는 거에 풍선 모두를 건다, 넌 뭘 걸래
PUCIT : 꼭 그렇게 디스퀄을 시켜야겠어?
Director : 부정행위하다 걸리면 디스퀄되는 거 안배웠냐
....
그렇게 해서 PUCIT는 디스퀄이 되었습니다.
15년 전 link
-
-
-
고글 -
방금 문제셋이 올라왔습니다.
http://acm.kaist.ac.kr/2008/ProblemSet.pdf
15년 전 link
-
-
-
Toivoa -
참고로 스코어보드 주소는 http://acm.kaist.ac.kr/2008/fullnums.html 입니다.
15년 전 link
-
-
-
Kyungryeol -
J번은 점들이 찍혀있을때 simple & monotone polygon의 갯수를 구하는 문제 입니다.
15년 전 link
-
-
-
lazyboy -
C번은 weighted graph의 shortest path를 따라가다가 임의의 edge 하나가 끊어질 수 있다는 가정 하에 최악의 경우를 구하는 문제네요.
고려해야 하는 shortest path는 입력으로 단 1개만 받고(즉, 여러 개의 shortest path가 있다는 가정은 안해도 됩니다)
어떤 edge가 끊어져 있을 때, 그 edge가 연결된 점에 도달하기 전에는 그 edge가 끊어져 있는지 모른다는 게 특이한 점입니다.
바로 idea가 떠오르진 않는데(n이 10000이라) 조금 더 생각해봐야겠네요.
15년 전 link
-
-
-
JongMan -
B번 문제는 약간 흥미롭습니다. A,G,C,T 로 구성된 문자열이 주어질 때, 이 문자열의 부분문자열 두 개에 대해 각 글자의 빈도수가 모두 같으면 이 둘을 equivalent 하다고 합니다. equivalent 한 문자열들을 하나씩의 셋으로 묶었을 때, 가장 큰 셋의 크기는 얼마일까요?
일단 가장 기본적으로, O(n*k) 의 모든 부분 문자열을 고려해서 풀어야 할 것으로 보입니다. 문자열의 길이를 1 부터 k 까지 증가시키며 각각에 대해 문제를 푼 이후에 그 중 가장 큰 것을 출력하면 될 것 같네요. 그럼 각 경우에 O(n) 으로 문제를 풀어야 하는데, 길이 x 인 부분문자열을 쭉 스캐닝해가면서
AGCCTB 에서 X = 4 라고 하면
AGCC, GCCT, CCTB 를 순서대로 고려하게 되는데, 맨 앞 글자의 빈도수가 하나 줄고 다음 글자의 빈도수를 하나 늘리면 각각 O(1) 에 빈도수를 계산할 수 있게 되죠.
그럼 문제는 이걸 어떻게 저장하느냐는 것인데, 빈도수의 차원은 600^3 (x 가 일정하다는 사실을 이용하면 600^4 에서 ^3으로 줄일 수 있습니다)이므로 배열을 잡기엔 여의치 않습니다. 하지만 전체 빈도수의 개수는 최대 60000 에 불과하므로, hash_map 등의 연관 맵 자료구조를 이용하면 시간 안에 적절히 나와주지 않을까 하는 생각이 드는 군요. :)
15년 전 link
-
-
-
하루 -
재미있는 중계를 위해 대회감독님이 http://acm.kaist.ac.kr/2008/summary.html 공개 하라고 하시네요 -_-;
15년 전 link
-
-
-
일루 -
Problems are really really too easy.. I thought problem difficulty is C >>>>>>>>>> (impenetrable 4D wall) >>>>>> other problems (difficulty is like topcoder srm 500~600) >>>>> A, B but four teams already solved them. Because there are all Korean teams(including Ajou, Sogang Univ's team), there is still good possibility to defend No. 1 place for Korean teams.
15년 전 link
-
-
-
일루 -
Also.. there is some possibility that SNU teams fail to get a ticket to the final. NP^3 team is ranked 4th, but their penalty + expected penalty is somewhat large and easily can be passed by other universities' teams. Assuming 'Children's Playground' team will rank first in Korean teams, and if one of other univ's team beats NP^3, probably SNU won't get a ticket.
15년 전 link
-
-
-
JongMan -
E번 문제는 O(n^2 lgn) 으로 해결할 수 있을 것 같습니다. 가장 많은 과녁을 꿰뚫는 반직선을 가정합시다. 이 반직선을, 가능한한 -x 방향으로 평행이동합니다. 그러면, 이 직선은 반드시 어떤 과녁의 왼쪽 끝을 지나게 됩니다. 그럼, 모든 과녁에 대해 이 과녁의 왼쪽 끝 점 P 를 지나는 반직선이 통과할 수 있는 최대 과녁의 수를 O(nlgn) 에 구해봅시다.
반직선이 P 를 지난다고 하면, P 을 통과하면서 주어진 어떤 과녁을 통과하기 위해 사격해야 할 구간을 y=0 직선 위에 구할 수 있습니다. 각 과녁의 왼쪽 점과 P 를 잇는 직선의 x절편, 오른쪽 점과 P를 잇는 직선의 x절편이 되겠죠. 그러고 나면, 이 구간들에 대해 최대 겹치는 구간 수를 구하는 문제가 되는데, 이건 소트 후 O(n) 으로 간단하게 풀리는 문제이죠.
좌표들이 굉장히 큰 관계로, 확실히 맞게 구현하려면 64비트 정수를 쓰는 유리수를 이용해야할 텐데 이것이 좀 번거롭군요.
15년 전 link
-
-
-
lazyboy -
상위권 순위 정리합니다. 아래 순위는 대회 공식 발표자료(학교별로 고려한)가 아닌 문제수/페널티만 가지고 제가 순서대로 매긴 순위입니다.
6위까지는 정확한 거 같은데 그 아래로는 조금 틀릴 수도 있습니다(특히 해외팀 관련)
1위 - 서울대학교 HP^3, 10문제, 대상
2위 - 서울대학교 MP^3, 9문제
3위 - 중산대학교 ZSU_Metatron, 8문제
4위 - 도쿄대학교 __________(andaasukoaazu), 8문제
5위 - 서울대학교 NP^3, 8문제
6위 - 한국과학기술원 So Hot, 8문제, 금상
7위 - 포항공과대학교 POSCAT, 7문제, 금상
8위 - 한국정보통신대학교 Children's Playground, 7문제, 은상
9위 - 톈진대학교 TJU_HanoiTower, 7문제
10위 - 서강대학교 Coderani, 6문제, 은상
11위 - 연세대학교 Morning Tree, 6문제, 은상
15년 전 link
-
-
-
lazyboy -
아, 정리한 보람도 없이 바로 공식으로 떴네요 ^^
http://acm.kaist.ac.kr/forum/portal.php?article=1
15년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
lazyboy
금방 시작했네요 중계 시작합니다
[리플 중계 보기 클릭]
15년 전