kdh9949

대회 Timeline4분 : 1번 AC (왠지 모르게 한 번 틀림...)~1시간 : 2번을 짜다가 말림. 계속 틀리더라 ㅜㅜ~2시간 : 3번을 짜다가 말림. ㅋㅋㅋㅋㅋㅋㅋ 이쯤부터 약간 느낌이 안 좋았다.~3시간 : 5번 풀이를 생각한 줄 알았는데 아니더라. 70점을 긁음.이 때 점수가 80 / 17 / 23 / 0 / 70 이었어서 나는 내가 스코어보드에도 안 보일 줄 알았다. (10등까지만 보여줌) 그런데 있더라? ㅋㅋㅋ 사람들도 나와 같은 길을 걷고 있다는 것을 깨달으니 약간 안심이 되었다(??)테트리스 문제가 처음에는 너무 어려워 보여서 넘겼는데 이제는 침착하게 마주해야 할 것 같아서 짰다. 생각보다 코딩 시간이 짧게 걸려서 1시간도 안 돼서 다 짜고 제출을 했는데, 처음에는 두 개 빼고 다 죽더..

처음 나가는 IOI라서 되게 설레기도 하고 긴장도 조금 됐는데 완벽하지는 않지만 그래도 내 당시 상태에서 할 만큼은 하고 온 것 같다. 새롭고 다시는 해 보지 못할 경험을 많이 했다는 점은 되게 좋은 것 같다.IOI라고 해서 대회 환경이 좋음이 보장되는 것은 아닌 것 같았다. Practice session 초반에 채점이 안 되는 것부터 뭔가 낌새가 이상했는데, Day 1때는 대회 시작 시점에 문제 pdf가 올라와 있지도 않았으며(프린트된 문제가 있어서 상관은 없었지만) 중간에 채점 큐가 조금씩 밀리기도 하고 Day2 때는 채점이 아예 안 되던 시점도 있었다. 이런 상황에서 굳이 연습할 필요까지는 없지만 제출을 좀 더 신중하게 쓰는 연습은 분명 필요한 것 같다.내 최대한의 실력을 발휘 못 한 것 같아 아쉬..

paint, messy, ailen 문제를 풀었다. 일단 messy가 interactive고 뭔가 별로 안 어려워 보여서 먼저 시작했다.제한을 보면 N=128인데 입력, 조사 쿼리가 각각 896=7*128=NlogN이라 딱 봐도 뭔가 반씩 나눠서 잘 하면 되겠다는 생각이 들었고, 일단 처음에 "1000...00", "01000...00" 같이 1개만 1인 문자열을 처음 반 개만 만들어서 넣어 보면 처음 반이 어디로 mapping되는지 알 수 있다는 것에서 시작하여, 그 다음에 분할을 어떻게 할 지 생각하다가 일단 보고자 하는 구간 [s, e]의 모든 수가 어디로 가는지 안다면 나머지 부분에 다 1을 채워 넣으면 된다는 것을 생각하고, 이를 이용해 간단한 분할 정복 풀이를 짜서 맞았다. 풀이가 빠르게 생각..

molecules, railroad, shortcut 문제를 풀었다. 사실 세 문제 다 예전에 본 적이 있는 문제였긴 하다.가장 먼저 molecules를 풀었다. 탐지 범위가 분자들간의 무게 차이의 최댓값 이상이라는 조건 때문에 주어진 수들을 정렬한 뒤 임의의 [s, e] 구간의 합만 고려해도 충분하다는 사실을 알 수 있다. 각 구간의 길이에 대해 이분탐색으로 간단히 조건을 만족하는 구간이 있는지 판별할 수 있다.그 다음에는 railroad와 shortcut을 각각 봤는데, 둘 다 일단은 아무 생각이 들지 않았다. railroad는 34점 풀이까지는 간단히 생각할 수 있었어서 일단 보류한 뒤 shortcut에 대해 고민을 좀 한 결과, 케이스를 적절히 나누고 전처리를 몇 가지 하여 모든 지름길을 놓는 경..

역대 POI 문제 중 ploughing, subway, railway 문제를 한 셋으로 풀었다.처음 문제 세 개를 훑어 본 후 ploughing과 subway는 일단 제쳐 둔 뒤 railway 문제에 대해 뭔가 쉬운 그리디가 떠올랐고, 1시간 좀 안 되게 열심히 노력한 결과 그게 틀렸다는 것을 알 수 있었다... 습관이 참 무섭다.그냥 18점 naive 풀이를 긁은 후 ploughing으로 넘어와서 다시 생각을 해 봤는데 O((HW)^2) 말고는 아직 잘 모르겠었다. subway도 마찬가지로 "리프 쌍들을 적절히 잘 고르면 된다"라는 것에서 더 넘어가지를 못 했다.railway 문제에 대해 다시 고민해 본 결과 풀이에 접근할 수 있었다. 기차가 들어오는 순서가 정해지면 각 기차가 몇 번째 기차까지 들어온..

Day 2 set에서 내가 예전에 풀었던 적이 있는 router를 빼고 kangaroo가 들어갔다.kangaroo를 보고, 문제가 뭔가 쉬울 것 같아서 먼저 잡았다. 너무 급하게 달려들었는지 생각이 잘 정리가 되지 않았고, 51점 풀이 같은 것을 생각한 뒤 일단 넘어갔다.match는 처음 봤을 때는 아무런 생각이 들지 않았다. 뭔가 Greedy한 가정을 하나 세워야 할 것 같은데 그것이 뭔지 잘 보이지 않아서 일단 또 넘어갔다.popeala는 문제를 읽자마자 "dp 최적화 문제"라는 생각이 바로 들었고, O(NT^2) Naive dp를 세워 일단 코딩을 했다. 그 다음에 좀 더 생각을 해 본 결과, i번 나눈 dp값에서 (i+1)번 나눈 dp값을 구할 때 더해지는 cost값을 N개의 구간으로 나누면 각각..

문제를 한 번 훑어 본 결과 1번이 뭔가 쉬워 보였고, 2번은 예전에 풀었던 다른 문제와 굉장히 비슷해 보였다. 그래서 그 두 개를 먼저 풀기로 했다.1번은 최대 8개의 다른 색의 점 중 일정 구간의 점들을 택하는데, 어떤 k종류 이상의 색의 점을 모두 같은 개수씩 가져가는 구간 중 가장 긴 구간의 길이를 구하는 문제이다. 8개 중 k개 이상의 색을 고르는 경우를 모두 해 보면서(약 2^8가지 경우가 있다) 각 경우에 대해 map을 이용하면 선택한 색들이 모두 같은 갯수만큼 들어간 구간들을 O(NlogN) 시간에 구할 수 있는데, 마지막 부분에서 약간 애매하게 TLE가 난다. 새로운 풀이를 잠시 생각해 보았으나 더 좋은 풀이가 생각이 나지 않아 2번으로 넘어갔다.2번은 레이저 광선이 지나가는 경로에 거울..

시험 날 왠지 모르게 졸렸다. 그게 약간 영향을 미친 것 같기도 하다....시험장에 들어가 컴퓨터를 만져 보는데 엄청 느렸다. 삼성전자 인재개발원이 그리워지는 대회 환경이었다 ㅠㅠ문제 3개를 딱 펴 본 뒤 처음 든 생각은 "아무것도 모르겠다" 였다. 1번은 2차원 그리드에서 특정 직사각형 내의 점들의 연결 컴포넌트 수를 구하는 쿼리 문제였는데 매우 어려워 보였고, 2번은 그래프를 돌면서 특정 작업을 하는데 그러면서 가장 짧은 시간 안에 이익을 많이 내는 사이클의 효율을 구하는 문제였는데 역시 매우 어려워 보였다(...) 3번은 interactive하게 게임을 진행하면서 상대가 N개의 아이템에 매겨 놓은 값을 구하는 문제였는데 이것도 아무것도 모르겠었다 ㅜㅜ 일단 그나마 잡으면 점수가 나오긴 할 것 같았던..

문제를 다 읽은 후 잠시 생각을 해 본 결과 1, 2번은 일단 전혀 모르겠었다. 생각나는 대로 적당히 긁은 뒤 그나마 하면 점수가 나올 것 같았던 3번을 잡았다. 3. Tasks Author (데이터 만들기)Single source shortest path 문제와 vertex coloring 문제를 푸는 코드에 대해 어느 것은 시간초과를 내고(cnt 변수를 100만 이상으로 증가시키고) 어느 것은 통과시키는 데이터를 만드는 문제다. 총 8가지의 subtask가 다음과 같이 나뉘어 있다.(SSSP : 최단경로 / Mystery : vertex coloring)subtask 1, 3 : n = 101이고 간선 없는 데이터 넣으면 된다. 손으로도 20초면 만든다.subtask 2: BellmanFord 코드와..

문제 난이도가 1->2->3 순서인것 같아서 (사실 1은 유명한 문제라 대충 알고 있었다) 그 순서대로 풀었다. 1. Dispatching큰 set에 작은 set을 합치는 그 유명한 테크닉을 쓰는 가장 대표적인 문제라고 주변에서 워낙 많이 들었었다. 그래서인지는 몰라도 문제를 직접 읽어 본 적은 없었지만 읽자마자 풀이가 바로 떠올랐고, 짜서 어려움 없이 맞았다.매니저가 정해지면 그 매니저의 서브트리에 있는 노드들 중 월급이 작은 것부터 최대한 많이 고르는 것이 당연히 이득이다. 따라서 각 서브트리별로 월급 순으로 적절히 정렬된 자료구조를 잘 들고 다닐 수 있으면 될 텐데, 각 노드별로 set을 들고 다니면서 합쳐 주면 편하게 처리할 수 있다.한 번 고려 대상에서 제외된 노드가 나중에 다시 들어올 일은 없..