ㅠㅠ 우선 대회 진행이 매끄럽지 못했던 점 송구스럽게 생각합니다 ㅠㅠ....
문제는 올라온 곳이 있으니 생략하고 (대회 공지 글에 댓글로..) 문제 출처 및 간단한 해법을 공개하겠습니다
A번: 아 뭔가 복잡한 기하 그림을 넣어서 보기 싫게 만들고, 사실 읽고나면 풀기 쉬운 문제를 내야겠다 싶어서 만든 문제 입니다. 읽어보시면 알겠지만 별 쓸데없는 얘기를 막 하다가 마지막에 R = 2r이라는 조건이 있어서 주어진 식을 풀고나면 타원 방정식이 나옵니다. 정답은 (r-d)(r+d)pi 가 됩니다 (이걸 때려 맞춘팀이 두 팀 있었습니다.. -_-; sample input/output을 보고 ㅋㅋ)
B번: 폴란드 OI 16회 Stage II Ice Skates 문제 입니다. http://oi.edu.pl/php/show.php?ac=e180311
C번: 폴란드 OI 14회 Stage I Query 문제 입니다. http://oi.edu.pl/php/show.php?ac=e180502 pre-processing을 잘하면 빨리 나오는데, 정답 맞춘 두 팀 중 LAX 팀의 솔루션이 조금
D번: 3^n 트릭입니다. 3^20이 조금 크기 때문에 3^10, 3^10으로 처음 n/2자리와 다음 n-n/2자리를 나눠서 brute force한 후 바이너리 서치 등을 이용해 풀면 됩니다 (저는 귀찮아서 그냥 map썼습니다). 조금 더 설명하자면 예를 들어 n=5여서 5자리라면 처음 2자리를 3^2로 모든 가능한 t_i들을 구해서 a_i * (t_i-1)의 합을 구해놓고 어디 저장해놓습니다. 다음 3자리도 또 3^3으로 하는데 하면서 나온 숫자를 S에서 빼면 저장해 놓은 곳에 우리가 원하는 숫자가 있나 없나 찾을 수 있습니다. (제가 열악한 환경에서 글을 쓰느라 자세하게 작성하지 못하겠네요 ㅠㅠ)
E번: CEOI 2008년도 Order라는 문제 입니다. http://www.ceoi2008.de/en/contest
max flow를 이용하여 풀 수 있습니다.
F번: 문제 이해를 정확히 하고 나면 어렵지 않은 문제 입니다. http://cepc.mimuw.edu.pl/pages/problems/g.pdf
CEPC 2003년도 문제이고, 이곳에 data와 문제와 예시 solution이 있습니다. http://cepc.mimuw.edu.pl/pages/problems.html
G번: 풀지 말라고 Astein님께서 내신 문제 입니다. 아마 댓글로 이 게임의 본 출처가 달릴 것으로 생각되므로 생략.
H번: 역시나 아주 살짝 낚시죠.. 문제가 좀 길고 더러워 보이지면 읽고나면 에라이 하고 푸는 문제입니다. 문제 풀이는 그냥 brute force후 조건을 검사해주면 됩니다. 많은 팀들이 생각지도 못한 실수를 해서 많이 WA가 나오기도 했습니다. 유일하게 모든 10팀이 푼 문제
I번: 폴란드 OI 13회 Stage III 문제 Sophie 입니다 http://oi.edu.pl/php/show.php?ac=e180602 (개인적으로 이 문제가 B, E, I 중에 가장 쉬워서 풀릴 거라 생각했는데 시도한 팀이 적어서 -아마도 두 팀 - 좀 놀랐습니다)
J번: TC 문제 입니다. DP로 간단하게 풀립니다. Sample input/output 두 번째 test case를 이해하면 못 풀 수가 없는 문제(?!) 입니다. http://www.topcoder.com/stat?c=problem_statement&pm=1256&rd=4493
K번: 폴란드 OI 14회 Stage II 문제 Driving Exam 입니다 http://oi.edu.pl/php/show.php?ac=e180502
ltdtl
ㅠㅠ 우선 대회 진행이 매끄럽지 못했던 점 송구스럽게 생각합니다 ㅠㅠ....
문제는 올라온 곳이 있으니 생략하고 (대회 공지 글에 댓글로..) 문제 출처 및 간단한 해법을 공개하겠습니다
A번: 아 뭔가 복잡한 기하 그림을 넣어서 보기 싫게 만들고, 사실 읽고나면 풀기 쉬운 문제를 내야겠다 싶어서 만든 문제 입니다. 읽어보시면 알겠지만 별 쓸데없는 얘기를 막 하다가 마지막에 R = 2r이라는 조건이 있어서 주어진 식을 풀고나면 타원 방정식이 나옵니다. 정답은 (r-d)(r+d)pi 가 됩니다 (이걸 때려 맞춘팀이 두 팀 있었습니다.. -_-; sample input/output을 보고 ㅋㅋ)
B번: 폴란드 OI 16회 Stage II Ice Skates 문제 입니다. http://oi.edu.pl/php/show.php?ac=e180311
C번: 폴란드 OI 14회 Stage I Query 문제 입니다. http://oi.edu.pl/php/show.php?ac=e180502 pre-processing을 잘하면 빨리 나오는데, 정답 맞춘 두 팀 중 LAX 팀의 솔루션이 조금
D번: 3^n 트릭입니다. 3^20이 조금 크기 때문에 3^10, 3^10으로 처음 n/2자리와 다음 n-n/2자리를 나눠서 brute force한 후 바이너리 서치 등을 이용해 풀면 됩니다 (저는 귀찮아서 그냥 map썼습니다). 조금 더 설명하자면 예를 들어 n=5여서 5자리라면 처음 2자리를 3^2로 모든 가능한 t_i들을 구해서 a_i * (t_i-1)의 합을 구해놓고 어디 저장해놓습니다. 다음 3자리도 또 3^3으로 하는데 하면서 나온 숫자를 S에서 빼면 저장해 놓은 곳에 우리가 원하는 숫자가 있나 없나 찾을 수 있습니다. (제가 열악한 환경에서 글을 쓰느라 자세하게 작성하지 못하겠네요 ㅠㅠ)
E번: CEOI 2008년도 Order라는 문제 입니다. http://www.ceoi2008.de/en/contest
max flow를 이용하여 풀 수 있습니다.
F번: 문제 이해를 정확히 하고 나면 어렵지 않은 문제 입니다. http://cepc.mimuw.edu.pl/pages/problems/g.pdf
CEPC 2003년도 문제이고, 이곳에 data와 문제와 예시 solution이 있습니다. http://cepc.mimuw.edu.pl/pages/problems.html
G번: 풀지 말라고 Astein님께서 내신 문제 입니다. 아마 댓글로 이 게임의 본 출처가 달릴 것으로 생각되므로 생략.
H번: 역시나 아주 살짝 낚시죠.. 문제가 좀 길고 더러워 보이지면 읽고나면 에라이 하고 푸는 문제입니다. 문제 풀이는 그냥 brute force후 조건을 검사해주면 됩니다. 많은 팀들이 생각지도 못한 실수를 해서 많이 WA가 나오기도 했습니다. 유일하게 모든 10팀이 푼 문제
I번: 폴란드 OI 13회 Stage III 문제 Sophie 입니다 http://oi.edu.pl/php/show.php?ac=e180602 (개인적으로 이 문제가 B, E, I 중에 가장 쉬워서 풀릴 거라 생각했는데 시도한 팀이 적어서 -아마도 두 팀 - 좀 놀랐습니다)
J번: TC 문제 입니다. DP로 간단하게 풀립니다. Sample input/output 두 번째 test case를 이해하면 못 풀 수가 없는 문제(?!) 입니다. http://www.topcoder.com/stat?c=problem_statement&pm=1256&rd=4493
K번: 폴란드 OI 14회 Stage II 문제 Driving Exam 입니다 http://oi.edu.pl/php/show.php?ac=e180502
14년 전