318개의 댓글이 있습니다.
-
-
legend12 -
말씀드리는 동안 현장 사진이 온라인에 공개가 됐습니다.
어제의 Pratice session 과 오늘 사진이 공개가 됐으니 한번 구경 가세요~
http://acm.kaist.ac.kr/forum/viewtopic.php?t=841
16년 전 link
-
-
-
DongJoo -
http://acm.kaist.ac.kr/2007/full.html
스탠딩은 이거인듯 합니다.... 각 team들의 무슨 팀인지 알 수 없을뿐 ㅠ.ㅡ
16년 전 link
-
-
-
Kyungryeol -
http://acm.kaist.ac.kr/2007/summary.html
여기서는 무슨팀이 어느문제를 풀었는지도 볼수있습니다.
16년 전 link
-
-
-
Kyungryeol -
최치선 특파원은 풍선들과 스탠딩을 보면서 ICU 선수들이 team 몇인지 좀 알려주면 고맙겠습니다 ㅋ
16년 전 link
-
-
-
Kyungryeol -
헉-_- 저런
16년 전 link
-
-
-
Kyungryeol -
다시 나타난 최치선 특파원
16년 전 link
-
-
-
Toivoa -
http://acm.kaist.ac.kr/forum/viewtopic.php?p=2497#2497
문제 떴습니다
16년 전 link
-
-
-
JongMan -
http://acm.kaist.ac.kr/2007/standing2007.html 아 현재 팀 이름이 나옵니다~!!
16년 전 link
-
-
-
JongMan -
C번 문제는 그래프 문제네요. 입력이 not-rooted tree 의 형태로 주어집니다만, S를 루트로 하는 트리로 편 후에 S에 대해 DFS 로 탐색하면서 동적계획법으로 문제를 풀면 될 것 같습니다. 예를 들어 현재 u 노드를 탐색하고 있고, 마지막으로 놓인 VOD 서버와의 거리가 x 라면 이 때의 답 sol(u, x) 은
1. u의 자손인 v들에 대해서, sol(v, x+1) 의 합
2. u의 자손인 v들에 대해서, sol(v, 1) 의 합 + 1
이 되겠죠. u에 VOD 센터를 놓느냐 아니냐의 문제이니까요. 물론 자세한 디테일은빠져있지만 이정도로 충분할거 같습니다.
이 정도 난이도라면 금방 풀리겠는데요
16년 전 link
-
-
-
Kyungryeol -
Punjab U. College of Info. Tech <- 여기는 어느나라인가요?
16년 전 link
-
-
-
JongMan -
자 WABMR 팀이 푼 D번에 대해서 말씀드리도록 하죠. 간략화 하자면, 2차원 grid 에 주어진 polyline 을 똑같이 그리기 위해 최소한으로 써야 할 선분의 개수를 구하는 문제입니다. 겹치는 부분이나, 두 수평인 선분의 끝과 끝이 이어져 있는 경우에는 한 개의 선분으로 충분하겠죠.
경우에 따라 다르겠지만 굉장히 쉽게 풀 수 있는 문제입니다. 구체적으로는 , 모든 선분을 (기울기, 왼쪽위점 x, 왼쪽위점 y) 의 튜플로 만든 뒤 이들을 소트하고, 기울기 가 같은 선분들에 대해서 문제를 풀면 되겠죠.
16년 전 link
-
-
-
Kyungryeol -
E도 풀리네요
16년 전 link
-
-
-
DongJoo -
ZhongShan Univ의 ZSU_Dubhe에 대한 간단한 정보를 말씀드리겠습니다.
팀원은 아래 3명입니다.
张子臻（队长，07计算机研）
张波 （04数计学院）
吴毅 （04计算机系）
04학번이 두명이네요.
The 2007 ACM Asia Programming Contest Changchun Site Internet Preliminary Contest(인터넷 예선)
에서 10위를 했습니다. 만만히 볼 팀은 아니네요.
http://acm.jlu.edu.cn/cc2007/report.htm
16년 전 link
-
-
-
Kyungryeol -
작년의 경우에는 시상식하는 방에서 서머리를 보여줬습니다.
16년 전 link
-
-
-
Kyungryeol -
역시 동주형의 정보력 ㅋㅋ
16년 전 link
-
-
-
최치선 -
사진은 실시간으로
http://220.69.176.137/~quadr/2007%20ICPC%20Pics/
에 업로드 되겠습니다
16년 전 link
-
-
-
Kyungryeol -
파키스탄 3등으로~
16년 전 link
-
-
-
Kyungryeol -
슬슬 우리 ICU 선수들도 올라가줘야하는데~
16년 전 link
-
-
-
JongMan -
아니 최치선 특파원 사진 중엔 http://220.69.176.137/~quadr/2007%20ICPC%20Pics/IMG_1115.JPG
이런 것도 있군요 -_-;;
16년 전 link
-
-
-
Kyungryeol -
윈터코더 한문제 더 풀었네요 3문제 상위권 그룹에 합류
16년 전 link
-
-
-
Kyungryeol -
헉 혼자 C를풀었군요
16년 전 link
-
-
-
Kyungryeol -
1시간이 지난 지금 F,G,H,I,J는 submit 0
16년 전 link
-
-
-
Kyungryeol -
사실 제가 그렇게 시켰습니다
16년 전 link
-
-
-
Kyungryeol -
파머존도 3문제로 상위권 그룹에 합류~
16년 전 link
-
-
-
legend12 -
잠시 뒤쪽으로 가서 J 번 문제를 보도록 하겠습니다.
최대 5만개의 integer 를 가지는 2개의 set S 와 T 가 주어졌을때, 이 set 에 포함되는 특정 element 를 s, t 라고 정의합니다.
이때 pair(s, t) 를 원소로 하는 set M 을 만들려고 할때, M 이 가지는 pair 에는 S 의 모든 원소와 T 의 모든 원소가 최소한 1번씩은 사용되어야 합니다.
이런 M 을 만드는데 드는 cost 는 원소로 가지는 pair 들의 cost 의 합과 같으며, 각 pair 의 cost 는 abs(s - t) 로 정의됩니다.
이런 M 을 만드는데 드는 최소의 cost 를 찾아서 출력하는 문제입니다~
16년 전 link
-
-
-
Kyungryeol -
한밭대 I 번 submit!
16년 전 link
-
-
-
Kyungryeol -
Anytime 한문제 더 풀었군요.
이팀도 벌써 멤버중 두명이 고정되어 icpc 3년차.
연습은 게을리 해도 어느정도의 실력을 갖추고 있죠.
16년 전 link
-
-
-
Kyungryeol -
1 Seoul N. U. "WE ARE BUT MEN, ROCK!" 4 123 2 Zhongshan U. ZSU_Dubhe 4 132 3 Punjab U. College of Info. Tech. Eagles 4 149 4 Seoul N. U. Incoming 4 177 5 Seoul N. U. Mighty Friend 3 67 6 KAIST Farmer John 3 88 7 ICU Anytime 3 95 8 ICU Winter Coders 3 96 9 KAIST ALLCHOL 3 177 10 Inha U. Oh Duck Square 3 198 11 ICU Strawberry 2 28 12 POSTECH Poscat 2 32 12등까지등수입니다.
http://acm.kaist.ac.kr/2007/standing2007.html
여기서 확인할 수 있습니다.
16년 전 link
-
-
-
JongMan -
http://acm.kaist.ac.kr/2007/standing2007.html
를 보세요.
16년 전 link
-
-
-
DongJoo -
http://acm.kaist.ac.kr/2007/standing2007.html
여기가 젤 보기는 편하네요.
16년 전 link
-
-
-
고글 -
55 Inha U. Fuzzy 0 0 55 Seoul N. U. of Tech. PLUM 0 0 55 Pyeongtaek U. CNP 0 0 55 Ewha Womans U. Tactics 0 0 55 Donga U. BlueColor 0 0 55 team17 0 0 3/-- 1/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 4/0 55 team28 0 0 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/0 55 team30 0 0 4/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 4/0 55 team5 0 0 5/-- 1/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 6/0 55 team57 0 0 0/-- 1/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 1/0 한팀을 제외하곤 다들 서브밋은 했네요!!
16년 전 link
-
-
-
JongMan -
음 H번은, 각 상태를
'현재 만든 string 의 suffix 중에서 forbidden 스트링들의 prefix 와 일치하는 것들 중 가장 긴 것'
으로 표현할 수 있을 것 같습니다. 이렇게 한 후 각 스트링 뒤에 A~Z 를 이어봐서 나오는 상태까지 간선을 연결합니다. 그리고 이 그래프가 DAG 가 되는지 (사이클이 있는지) 확인하면 되겠죠. 만약 없다면 동적 계획법으로 각 상태에서 나올 수 있는 가장 긴 스트링의 길이를 찾은 후 lexicographically largest 를 찾으면 됩니다.
단 하나 문제가 되는 것은 그래프 만드는 데 걸리는 시간인데요.. 이건 잠시 후.
16년 전 link
-
-
-
legend12 -
처음에 생각한건 Min-cost Max-flow 였으나 이건 너무 메모리 부하가 크고 설계에도 오류가 있어서 생각을 접었는데요..
현재 고려되고 있는 방법은 nlgn 그리디 입니다.
S의 원소들에 대해서 각각 T 에서 선택했을때 cost 가 작은것을 bsearch 를 통해 찾아서 선택한후, T의 원소들에 대해서 아직 선택받지 못한 것들을 S 의 원소에 대해서 bsearch 를 돌려서 min-cost 를 찾는 방식인데요..
S 에 4라는 값이 있고, T 에 2, 6 이라는 값이 있을때 2와 6중 하나가 이미 다른것과 매치가 되어있으면 그거와 매치가 안될걸 매치해야 cost 가 작아질텐데 그리디에서는 그 것이 고려가 안된다는 단점이 있네요..
현재는 다이나믹 접근법을 고민중입니다.
16년 전 link
-
-
-
JongMan -
모든 스트링들의 prefix 를 모으면 1000*50 = 50000개가 되겠죠. 이들을 모두 뒤집은 뒤 trie 에 넣어서 실질적으로 suffix tree 를 만들면 되겠는데요.. 25,025,000개의 노드가 필요한데 메모리가 안되겠군요.
그러면 이 prefix 들을 뒤집어서 소트해서 뒤집힌 prefix tree 를 만듭시다. 그럼 각각의 5만개 state 에 대해서, 26개의 알파벳을 붙였을 때 이 string 의 suffix 중에서 prefix 에 해당하는 가장 긴 것의 길이를 바이너리 서치로 찾을 수 있겠지요. 근데 이때도 스트링 비교를 해야 하기 때문에...
50000 * 26 * 50 * lg50000 인데요.. 실제 시간은 이것보단 적게 나오겠지만 솔직히 좀 불안하군요. ^^;;
16년 전 link
-
-
-
Kyungryeol -
제가 아까 잘못봤을 가능성도 있군요.. ^^;
16년 전 link
-
-
-
Kyungryeol -
동감입니다 제작년에 여자 세명한테 1위를 내줄때 너무 슬펐습니다
16년 전 link
-
-
-
Kyungryeol -
F도 풀렸네요 incoming
16년 전 link
-
-
-
Kyungryeol -
8문제 한표!
16년 전 link
-
-
-
Kyungryeol -
제가 특별한 애정을 보여줬기 때문에 올해의 ICU는 쉽게 침몰하지 않을것으로 믿습니다.
16년 전 link
-
-
-
Kyungryeol -
참가자들은 걸려있는 풍성과 화장실 가는길에 붙어있는 종이를 보고 summary를 확인할 수 있을듯 합니다.
16년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
legend12
한국시간으로 10:00 부터 시작합니다. 참가자 분들 모두 건투를 빕니다.
리플로 중계 합니다. 제목을 클릭해 주세요!
★☆응원의알고스팟☆★★☆응원의알고스팟☆★★☆응원의알고스팟☆★★☆응원의알고스팟☆★
★☆응원의알고스팟☆★★☆응원의알고스팟☆★★☆응원의알고스팟☆★★☆응원의알고스팟☆★
★☆응원의알고스팟☆★★☆응원의알고스팟☆★★☆응원의알고스팟☆★★☆응원의알고스팟☆★
★☆응원의알고스팟☆★★☆응원의알고스팟☆★★☆응원의알고스팟☆★★☆응원의알고스팟☆★
★☆응원의알고스팟☆★★☆응원의알고스팟☆★★☆응원의알고스팟☆★★☆응원의알고스팟☆★
★☆응원의알고스팟☆★★☆응원의알고스팟☆★★☆응원의알고스팟☆★★☆응원의알고스팟☆★
★☆응원의알고스팟☆★★☆응원의알고스팟☆★★☆응원의알고스팟☆★★☆응원의알고스팟☆★
★☆응원의알고스팟☆★★☆응원의알고스팟☆★★☆응원의알고스팟☆★★☆응원의알고스팟☆★
현장 특파원 : ???
16년 전