후기
ICPC 참가하고 싶다고 얘기만 했지 군 문제 때문에 참여가 3년이나 미뤄졌는데 다행히 팀이 구해져서 참가할 수 있었다.
이 분야에서는 가장 큰 메이저 대회기 때문에 매주 주말마다 모여서 연습했는데 시간이 2달도 안 되서 팀워크 맞추기엔 많이 부족한 시간이 아니었나 싶다. 조금 더 일찍 만나서 친해지고 맞춰볼 수 있었다면 더 나은 성적을 얻을 수 있었는데.. 하는 생각을 많이 했다.
성적이 많이 쪽팔려서 후기도 안 쓰려고 했는데 조금이나마 감정이 남아있을 때 정리해두는게 좋을 것 같다.
인예
3솔... (이딴게 학교대표?)
I(00:08)
누가 푼지는 모르겠고, 문제는 설명이 필요 없어 보이므로 패스
J(00:34)
같이 참가했던 형이 잡았던 것으로 기억한다.
문제 조건을 제대로 못 보고 "부분합인 것 같긴한데 시간내에 안 돌아가는데?" 하고 고민 하다가 "10"을 만들어야 된다는 거 뒤늦게 알아채고 무지성 부분합으로 ac받았다.
H(02:22)
무려 2시간이나 지나서 그 다음 문제를 풀 수 있었다.
내가 잡았던 문제였는데, 그냥 세그냄새를 대놓고 풍겨서 잡았다가 약간 고전했다. 그 백준에 비슷한 문제가 있었던 것으로 기억하는데 부등식 조건이 하나가 다르다.
$q_i < q_j < q_k$를 구하는 문제였나? 아무튼 세그먼트 2개로 최소값 범위의 최소값을 구해주는 식으로 구해 줬다.
E
같이 참가했던 형이 잡았었다.
나는 문제 읽다가 머리 아파서 안 보겠다고 선언했는데, 이거 쉬운문제같으니 내가 보면 풀 수 있다고 계속 설득하셨다.결론적으론 그 말을 들었어야 됐는데... 팀원들한데 많이 미안했다.
그냥 무지성 $n^2$ DP다. 뭐.. 할 말이 없다. 진짜 무지성 DP라서 대회 끝난 뒤에 밥먹다가 문제 설명 제대로 듣고 풀었을 정도.
K
누가 잡았는 지 기억이 안난다.
이것도 밥먹다가 "이거 세그 냄새 풀풀 나는데?" 해서 얼른 밥먹고 집와서 풀었던 기억이 난다.
세그로 풀고 나니까 어?? LIS네? 싶어서 다시 LIS로 제출해서 AC받았다.
set + 그리디 로도 풀린다는데 lis가 더 간단한 것 같다.
B
같이 참가했던 동생이 잡았었다.
귀찮아 보이기도 하고 동생이 거의 다 풀어 간다고 얘기했어서 신경 안 썼는데... WA한번 받고 못 풀었다.
동생이 푼 코드를 보지는 못 했지만, 아마 사분면 나눠서 case work한 뒤 처리가 까다로운 1사분면을 어떻게 처리하려고 한 것 같다.
그냥 x좌표 돌리면서 y좌표 개수 세어주면 끝나는 문제다. 문제 설명대로 끈을 돌려가면서 그려보면 마굿간 오른쪽 위 모서리에서 두 원이 겹치는 공간이 발생하기 때문에 포함배제원리 써서 제외시켜줘야 한다던데, 구현이 까다로워질 것 같아서 그냥 x좌표 돌리면서 y좌표 개수 세어주는 식으로 풀었더니 AC.
A
내가 잡았던 문제다.
이거 잡았다고 욕 엄청 먹었다. 누가봐도 Mo's 쓰는 문제고, 팀노트에 Mo's가 들어 있기 때문에 빠르게 풀고 넘어갈 줄알았다. 백준13548 문제와 완전 유사한데, 차이점은 최빈값의 빈도를 구하느냐 vs 최빈값을 구하느냐 차이이다. 물론 13548문제도 플레1로, 내 수준에선 많이 어려운 문제지만 다이아5는...
풀이를 대충 들어보니 13548 + 버킷 하나 더 만들어서 어떻게 처리 하면 된다던데, 여러번 시도해봤음에도 불구하고 아직까지 풀지 못 했다.
본선
3솔... (이딴게 36등...?)
C(00:26)
첫 솔이 굉장히 늦어져서 망했다 생각부터 들었다. 같이 나간 형이 풀었던 것 같다.
문제 설명은 생략
B(01:05)
내가 풀었는데.. 욕 무진장 먹었다.
처음엔 DP생각했다가 아무리봐도 DP로는 안 되고 투포인터 갈기면 되겠다는 생각을 했다. 그럼에도 불구하고 2WA나 먹었다.
DP로 짜놨던 코드를 수정해서 투포인터로 고친거라 중간에 뭐 잘못 수정한 줄 알았는데, 알고보니 입력을... string으로 받고 (s - '0')으로 받았다.. 왜 그랬는지 정확하게 기억은 안 나는데, 진짜 왜 그랬지????
같이 참가한 형이 10분정도 내 코드 보다가 발견했다.
L(02:21)
같이 참가한 형이 풀었다.
대회때 어떻게 푼 지는 기억 않나는데 bitset으로 무지성으로 갈기니 풀렸다고 들었다.
이 문제에서 bitset을 처음 접했는데, 크게 어렵지는 않아서 빠르게 업솔빙할 수 있었다. 다만, "이게 시간내에 돌아가?"느낌 이었는데 시간내에 돌아가서 신기했다.
정해는 포함배제원리라는데, 모르겠고 그냥 브루트포싱해도 풀린다.
F
우리 관심 밖이었던 문제다.
DP같기도 하고 그리디같기도 하고.. 둘 중 뭔지 고민하다가 다른 문제로 틀었다. 결론적으론 DP + 그리디 + 부분합.
두 배열을 정렬하면 같은 index끼리 매칭 시켜주는게 max가 min이 된다(그리디). 거기서 상품 하나($i - 1$를 빼고, 매칭 되었던 가격표가 하나 남는다. 여기서 $i$번째 가격표와 매칭되었던 $i$번째 상품이 $i$가격표 또는 $i-1$가격표를 선택해야하는데 이걸 dp로 처리해주면 된다. max의 min을 구하기 위해서 max를 부분합으로 처리해두고 dp를 돌리면 된다.
dp를 앞, 뒤에서 두번 돌려야 한다는 점 빼고는 다른 생각할 건 없는 것 같다.
D
세명이서 마지막으로 잡았던 문젠데, 아직 업솔빙 시도는 하지않았다.
대충 풀이를 들었었는데 "이게 여기에 붙으면 저게 모순이 되니 불가능 해서 이게 정답이다"라는 느낌으로 들었고, 세명 다 듣자마자 무릎을 탁 하고 쳤다. 문제가 기억이 나지는 않고, 그때 그 충격의 파동만 머리에 남아있다.
G
나랑 동생이 잡았던 문제다.
bfs 2번으로 트리 지름 구하는 문제와 비슷한 느낌이 들어서 접근했었다. 마찬가지로 아직 업솔빙은 해보지 않았는데, 대충 dp를 써야한다는 느낌은 받았었기 때문에 업솔빙 하고나면 풀이를 올려보도록 하겠다.
