후기
-
IOI 2023 후기일기장 2023. 9. 11. 15:41
8/28 ~ 9/4에 헝가리에서 열린 IOI 2023에 한국 국가대표로 참가했다. 한국 팀 멤버는 박상훈(qwerasdfzxcl), 반딧불(79brue), 이동현(lisifu/kizen), 이성호(puppy/windva)였고, 작년에 비해 꽤 강한 멤버였기 때문에 4금을 노려볼만하다고 생각했다. 나와 동현이는 금메달을 받았고, 딧불이와 성호는 은메달을 받으면서 2금2은의 성적을 기록했고, 국가 순위 5등을 했다. 작년에도 IOI에 참가했지만 코로나 이슈로 온라인으로 참가하게 되어서 대회만 치고 끝났는데, 올해는 오프라인으로 직접 헝가리도 가고 여러 행사나 관광을 즐길 수 있어서 매우 좋았다. 솔직히 말하자면 관광은 별 거 없어서 재미없었고 공통 관심사를 가진 외국인 친구들을 많이 만날 수 있었던 것이 너..
-
2023 IOI 멘토교육 5주차일기장 2023. 5. 29. 17:17
CEOI 2016을 돌았다. 0:00 ~ 1:47 1번과 2번을 읽었다. 1번은 나이브가 쉽고 풀태는 바로 안 떠올라서 2번을 읽고 풀었다. 나이브랑 풀태 모두 자꾸 틀려서 시간을 많이 날렸다. 처음에 dnc opt 풀이랑 덱dp 풀이를 내서 둘다 짰는데 둘다 틀린 풀이였다. 100점 받으려면 대충 비트스트링 들고 다니면서 적당히 dp 돌려주면 O(NTS)에 문제를 해결할 수 있다. 1:47 ~ 3:34 3번을 읽었다. input 노드 루트개 / output 노드 루트개 연결하는 노드들을 만들고 연결하면 47점을 받을 수 있다. 100점을 받으려면 이를 다중으로 해주면 된다. i번째 층의 노드는 input 노드 P^(i/k)개, output 노드 P^((k-i)/k)개를 연결하는 노드라고 놓으면 추가 노..
-
2023 IOI 멘토교육 4주차일기장 2023. 5. 24. 09:05
BOI 2022 Day 1을 돌았다. 0:00 ~ 0:17 1번 문제를 읽었다. 순열을 쿼리로 날리면 inversion 개수를 알 수 있을 때 N번 이하의 쿼리로 원래 순열을 복원해야한다. 순열을 N번 rotate하면서 넣으면 각 원소의 등수를 알 수 있기 때문에 쉽게 풀린다. 0:17 ~ 1:05 2번 문제를 읽었다. 섭태 풀이가 대부분 쉬웠고 100점 풀이도 쉬울 것 같아서 조금 고민해보기로 했다. 시작에서 끝으로 가는건 최적화하기 까다로워서 거꾸로 끝에서 시작으로 가는 방식을 생각해봤고 문제가 더 간단해졌다. 스파스테이블을 이용한 100점 풀이를 바로 짰고 AC를 받았다. 1:05 ~ 3:52 3번 문제를 읽었다. 가중치가 -M이상 M이하의 정수로 bound되어있을 때 M에 대한 다항시간으로 냅색을..
-
2023 IOI 멘토교육 3주차일기장 2023. 5. 14. 21:24
ROI18에서 4문제 뽑아서 5시간동안 돌았다. 1. Decryption 2. Quick sort 3. Quantum teleportation 4. Addition without carry 0:00 ~ 0:14 1번 읽고 바로 짜서 맞았다. 0:14 ~ 1:52 234번을 읽고 3번을 고민했다. 대충 다익스트라를 이용한 세제곱/64 풀이랑 제곱로그/64 풀이를 냈다. 일단 나이브인 세제곱/64를 짜고 디버깅을 했더니 67점이 긁혔다. 제곱로그/64를 짜고 100점을 받을까 생각해봤지만 x좌표나 y좌표 같은 점이 있으면 안 되는 풀이라는걸 깨닫고 그냥 넘어갔다. 1:52 ~ 2:07 4번은 섭태가 너무 많아서 일단 2번 버블소트로 50점을 긁었다. 2:07 ~ 2:54 2번을 좀 더 고민하니 대충 로그복잡..
-
2023 IOI 멘토교육 2주차일기장 2023. 5. 7. 15:10
USACO 23 us open 골드 123번 / 플래 13번으로 구성된 5문제 셋을 5시간 동안 돌았다. 문제 번호는 순서대로 붙어있다. 0:00 ~ 1:00 초반 1시간에는 문제를 다 읽고 바로 풀이가 보이는걸 짜려고 했다. 근데 풀이가 명확히 보이는건 없어서 일단 1번을 생각해봤다. 키를 배치하는 전략을 찾는 것은 어려울 것 같아서 다른 방향으로 생각해보다가 거꾸로 돌리면 되지 않을까 라는 생각을 하게 되었다. 그 아이디어가 핵심이었고 정방향 / 역방향 탐색을 해주면 문제가 쉽게 풀린다. 1:00 ~ 1:30 2번을 고민했다. 2번과 4번이 컨셉이 같은 문제인데 2번이 요구하는게 적어서 더 쉬울 것 같았다. 조금 고민하니까 2번 풀이가 나왔고 금방 짜서 맞았다. dp를 잘 돌리면 된다. 1:30 ~ ..
-
2022 IOI 멘토교육 2주차일기장 2022. 6. 17. 22:28
문제 셋: 1번 IOI09 POI (https://www.acmicpc.net/problem/5462) 2번 BOI06 Coin Collector (https://www.acmicpc.net/problem/3368) 3번 CEOI13 Adriatic (https://www.acmicpc.net/problem/9284) 4번 KTST20 하나 둘 셋 (https://www.acmicpc.net/problem/25013) KOI 스타일로 구성된 4시간 셋입니다. 0:00 ~ 0:06 난이도 순이라는 걸 알고 있었기 때문에 1번부터 차례로 풀었습니다. 매우 쉬운 문제이므로 바로 AC를 받고 넘어갔습니다. 0:06 ~ 1:30 2번을 봤습니다. 문제를 잘못 이해해서 1시간 가까이 뇌절을 했고, 일단 나이브라도 ..
-
2022 IOI 멘토교육 1주차일기장 2022. 5. 21. 18:49
문제 셋: 2011 IOI day 2 실제 대회처럼 5시간 타이머를 해놓고 봤습니다. 0:00 ~ 0:24 일단 1번 문제부터 읽어봤습니다. 부모 정점을 고려해서 적당한 트리 dp를 돌리면 서브태스크 1을 맞출 수 있다는 강한 확신이 있었지만 구현과 디버깅을 빠르게 할 자신이 없어서 일단 보류했습니다. 서브태스크 1의 배점이 매우 높기 때문에 일반그래프를 트리로 줄이면 문제가 해결되지 않을까 하고 생각을 해봤지만 잘 되진 않았습니다. dp관점으로 생각해보면 답이 작은 정점부터 차례로 계산해나갈 수 있고, 이는 다익스트라와 동일한 발상입니다. 구현도 매우 간단하기 때문에 바로 코딩을 했고, 100점을 받았습니다. 다른 문제를 읽지 않고 한 문제의 100점 코드를 짠다는 것은 매우 위험한 전략이지만, 풀이가..