kdh9949

블로그를 버려 둔 지 한참이 지났는데 얼마 전에 갑자기 생각이 났다. 블로그를 안 쓴 기간 동안 굵직한 PS 대회를 여러 차례 나갔었는데, 대충 리스트를 뽑아 보면 아래와 같다. SCPC 2018 - 7등(3등상) 카카오 코드 페스티벌 - 몇등인지 까먹음(아마 5등상?) ICPC Seoul Regional 2018 - 1등(대상) ICPC World Finals 2019 - 7등(은메달) SCPC 2019 - 7등(3등상) ICPC Seoul Regional 2019 - 2등(금상) Google Hash Code 2020 Final - 잘 기억안나는데 암튼 망함 SCPC 2020 - 특별상(2회 수상제한..) ICPC Seoul Regional 2020 - 4등(은상) World Finals는 다행히도 ..

SCPC는 삼성에서 주최하는 대학생 대회로, 상금이 빵빵하기로 유명하다. (스택메모리 1MB밖에 안 주기로도 유명하다 UPD(20.12): 이젠 스택메모리제한 따로 없다)1차 예선, 2차 예선을 온라인으로 치른 뒤 본선을 오프라인 대회로 치른다. 올해 1차 예선은 배점이 100 / 100 / 150 / 200 / 250점으로, 4번째 문제를 제외한 나머지 문제는 평범한 알고리즘 문제, 4번째 문제가 Optimization Problem (??)이 나왔다. 요즘 유행인가...나는 모든 문제에서 만점을 받았다! 예선 특별상 같은 거 안주나... 1. 버스 타기n(

대회 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개의 아이템에 매겨 놓은 값을 구하는 문제였는데 이것도 아무것도 모르겠었다 ㅜㅜ 일단 그나마 잡으면 점수가 나오긴 할 것 같았던..