1/14 ~ 2/18
위 기간 동안 2024 1/2차 선발고사를 대비하여 푼 문제들 목록이다.
매일은 아니지만 꽤나 자주 서브태스크가 있는 문제로 4문제 5시간 셋을 만들어서 풀었고, 그 외의 시간은 시간 중에 풀지 못한 문제를 업솔빙하거나, 서브태스크가 없는 문제를 풀었다.
(O : 직접 푼 문제 / X : 업솔빙한 문제)
27508 던전(O)
-> 2차원 DP
27511 야유회(X)
-> 아이디어, 투스텝
27605 기지 간소화(O)
-> 대충 큰작
-> pair<int, set<int>> 절대 쓰지 말자. 엄청 느리다.
27607 학생들(O)
-> 재밌었던 아이디어 문제. 문제의 조건을 완벽히 이해하면 나머지는 할만 함.
3654 L퍼즐(O)
-> 2-SAT
22029 철도(O)
-> 그냥 투스텝
17624 검은 돌(X)
-> 검은 돌 DP를 익히는 문제
22028 렉(X)
-> 개쩌는 2D Query 문제. 부분문제도 거의 못 품.
14898 서로 다른 수와 쿼리 2(O)
-> PST 짜기 싫어서 MST로 풀었다.
27289 Gym Badges(X)
-> Exchange argument는 떠올렸지만 PQ 아이디어를 못 떠올림
14421 The Kingdom of JOIOI(O)
-> 그냥 쉬운 문제. 구현하니까 그냥 한 번에 나옴.
28056 Merging Branches(X)
-> 문제를 다른 문제로 바꾸는 아이디어. 전에 한 번 봤는데 그 때도 못 풀고 지금도 못 품.
21844 Keyboard(X)
-> bitset 최적화는 했으나 2^i Knapsack 아이디어를 못 떠올렸다.
27510 택시 여행(X)
-> Centroid Tree 문제. 어렵다.
17642 Dynamic Diameter(X)
-> Centroid Tree + Multiset 여러개 들고 다니면 될거 같지만 구현이 너무 복잡하기에 오일러 투어로 품.
19683 Spring Cleaning(O)
-> 그냥 쉬운 문제. 보자마자 풀었다.
15556 Commuter Pass(O)
-> 최단경로를 DAG로 바꾸는 아이디어.
1199 오일러 회로(?)
-> 그냥 오일러 회로.
18848 Capital City(X)
-> 분할 정복할 생각을 못했다. 분할정복 생각하면 Centroid 뚝딱
19932 Painting Squares(X)
-> 오일러 회로 응용
1616 드럼통 메시지(X)
-> 위 문제의 상위호환. 크게 다르지 않다.
27509 외곽 순환 도로 2(X)
-> 홀수 사이클 조건을 이분 그래프 조건으로 바꾸는게 신기했던 문제. 그 뒤로는 그럭저럭 할만(?)하다.
31286 철도 2(O)
-> 이번 선발고사에서 만점 받은 문제. 트리의 지름 아이디어를 생각하면 쉽다.
25008 문자열 찾기(O)
-> 정해는 KMP랑 비슷하게 하는 거라는데 무지성 해시 써도 풀린다. easy
25011 칠하기(O)
-> 주어진 2차원 격자를 그래프로 바꾸고 2-SAT 돌리는 아이디어. 재밌다.
9373 복도 뚫기(O)
-> 기하로 위장된 Union Find 문제. 크루스컬이랑 비슷하게 풀 수 있다.
1848 동굴 탐험(X)
-> 신기한 아이디어 문제. 이진수로 분할정복하는 아이디어가 신기했다.
17671 두 안테나(X)
-> 개쩌는 2D Query 2. 오프라인 쿼리라는 점을 이용해 엄청 어려운 Lazy를 짜면 된다.
27472 깃발 꽂기(O)
-> 2-SAT 중에서 어려운 문제. 정해는 사다리 어쩌고 트릭을 쓴다고 하지만, 나는 NsqrtN으로 뚫었다.
15249 Building Bridges(O)
-> 리차오 뚝딱
15246 One-Way Streets(X)
-> 그동안 몰랐던 몇 개 안되는 알고리즘 BCC. BCC 생각보다 별거 없잖아...(?)
16911 그래프와 쿼리(?)
-> ODC 처음 공부해봤다. 재밌다.
16912 트리와 쿼리 12(O)
-> =16911
16695 The Bridge on the River Kawaii(O)
-> ~16911
20987 Robot(X)
-> 첫번째로 해야 하는 중요한 관찰을 놓쳐서 못 풀었다. 풀이가 신기하다.
27992 Two Currencies(X)
-> PBS 너무 오랜만에 봐서 못 풀었다.
25012 마법의 다이얼(O)
-> 원형 조건 무시하고 2개 붙여서 적당히 스위핑 돌리면 풀린다.
25013 하나 둘 셋(X)
-> 거의 풀었는데 마지막 회의실 배정 부분을 최적화 못해서 못 품.
24973 Up Down Subsequence(O)
-> 그냥 쉬운 세그 DP
2803 내가 어렸을 때 가지고 놀던 장난감(O)
-> 그냥 sos DP + 포배
5466 상인(O)
-> 덜 쉬운 세그 DP
14869 요리 강좌(O)
-> 정해는 덱 DP지만 그냥 우선순위 큐로 1928ms에 뚫어냈다.
20080 Simurgh(X)
-> 정말 신기한 아이디어 문제. 근데 구현도 꽤나 빡세다.
14870 조개 줍기(O)
-> 업데이트 되는 구간이 행별로 슬라이딩 윈도우처럼 밀린다는 성질을 관찰하면 투포인터 뚝딱
5813 이상적인 도시(X)
-> 매우 인상적이었다. x따로, y따로 계산하겠다고 생각하면 주어진 그래프를 트리로 바꿀 수 있다!
25267 Permutation(X)
-> 거의 풀었는데 마지막에 이상하게 생각해서 만점까지는 못 갔던 문제. 90점 정도까지는 쉽고, 아이디어 하나만 더 쓰면 풀린다.
22032 원숭이(O)
-> 그냥 쉬운 문제. 역시 -정보올림피아드위원회-
22031 회의실(O)
-> DP를 이상하게 정의해서 못풀 뻔 했던 문제. 그냥 하면 된다.
19560 Village(X)
-> 풀 땐 감도 안왔는데 풀이를 보니까 꽤 당연해 보인다. 최소는 그리디, 최대는 모든 엣지를 최대로 사용할 수 있다.
19916 Rectangles(X)
-> 최대가 되는 원소를 기준으로 그 원소를 포함하는 구간이 최대 1개라는 점을 이용하는 문제. 신기하다
28058 Tsunami(X)
-> LiChao + Lazy 써야 되는 문제. 딱 보고 직선의 방정식이라는 생각을 못 했다. + LiChao Lazy도 배울 수 있었던 문제
31285 경찰과 도둑(?)
-> 선발고사 날에는 시간이 거의 없어서 생각할 시간이 없었던 문제. 풀이 들으니까 대충 알 거 같아서 풀었다.
15555 Dango Maker(O)
-> 주어진 2차원 RGW를 사선으로 돌려서 G 기준으로 푸는 문제. 재밌다.
22023 Distributing Candies(X)
-> 부분 문제 몇 개 정도는 세그 비츠로 풀리지만, 정해는 스위핑...
19935 Carnival Tickets(X)
-> 내가 잘 못 푸는 유형의 문제. 일단 짝수 개라는 조건을 쓸 방법을 몰랐던 나란 놈
30100 호텔 배정(O)
-> 검은 돌 DP 재탕. 검은 돌 문제 풀어서 쉬웠다.
6762 Repetetivity(X)
-> 아이디어가 인상적이었다. 제곱을 부분문자열 2개의 매칭으로 본다는 아이디어...
13188 Kangaroo(X)
-> 이거도 매우 인상적. 이걸 보고 DP를 어떻게 떠올림?
25019 날다람쥐(O)
-> 정해는 슬로프 트릭이지만 그걸 몰랐던 나는 DP + Lazy로 열심히 해서 풀었다.
25016 진화(X)
-> HLD 생각을 해서 답이 최대 logN이라는 걸 알아냈지만, 못풀었다. ㅠㅠ
14875 City Attractions(O)
-> Lazy로 풀라 했는데 계속 시간초과 떠서 화났다. 그냥 O(N) Tree DP로 푸니까 슥삭 풀린다...
19927 Vision Program(X)
-> (x, y) 좌표계를 (x+y, x-y) 좌표계로 바꾸는게 신기했다.
25438 메기 농장(X)
-> O(N^3) DP는 했지만, 정해는 L, R 어쩌고... 미친 문제
10075 친구(X)
-> 모든 유저들의 영원한 루비 5 친구. 뭔 문젠지 궁금했는데 아이디어가 참신한 문제였다.
10922 말(O)
-> 섭테가 풀이의 스포였던 문제
19936 Packing Biscuits(X)
-> 내가 못 푸는 유형의 문제 2. DP로 바꾸는게 신기했다.
24942 Jail(X)
-> 세그먼트 트리를 이용해 간선을 줄이는 테크닉을 알고 있었다면 편할 수도 있는 문제. 몰라서 못 품.
17731 Historical Research(O)
-> Mo's 문제. 시간 제한이 빡세서 multiset, pq 이런거 안되고 세그먼트 트리 써야 된다.
11933 공장들(O)
-> 정해는 트리압축. 나는 Centroid Tree로 풀었다.
25022 마법 구슬 찾기(O)
-> 그리디한 아이디어를 떠올려서 풀었다. 재밌다.
15557 Snake Escaping(X)
-> O(Q*2^(L/2))까지는 생각을 했으나 반 발짝을 못 가서 못 풀었다. O(Q*2^(L/3))으로 풀린다.
11941 핀볼(X)
-> 밑에서 위로 구간을 확장한다고 생각해서 O(N^2logN)까지는 풀었으나, 위에서 아래로 가는 생각을 못했다. 양쪽만 고려해도 되는거였어?
5811 낙하산 고리들(X)
-> 복잡한 케이스 웤 문제. 5가지 정도로 경우를 나눌 수 있다.
25442 드문 곤충(X)
-> 이분 탐색을 왜 못 떠올렸지... 이분 탐색 아이디어 떠올리고 랜덤 비스무리하게 하면 만점까지 나온다.
18193 비행기 타고 가요(X)
-> 세그먼트 트리를 이용해 간선을 줄이는 테크닉 연습 문제. 이 테크닉을 쓴다는걸 알고도 못 풀었다.. ㅋㅋ 추가로 Mlog^3N이 안 돼서 더미노드를 만들어서 Mlog^2N으로 풀어야 한다.
오 언제 75개나 풀었지
피나는 노력 끝에 결국 국대 후보가 되었다고 합니다. ㅅ..ㅂ
상당히 슬프다.
이로써 (짧은 기간의) 노력은 배신한다는 교훈을 깨닫게 되었다.
