Class 8을 달았다.

Class 8에 처음? 등장하는 FFT / 플로우 / DnC opt 등을 공부하긴 귀찮고 그렇다고 국메기같은 굉장한 문제를 짜긴 싫어서, 최대한 구현이 편해보이고 이미 알고 있는 지식으로 풀 수 있는 문제들을 열심히 찾아서 풀었더니 딱 20문제가 됐다.

 

 

풀면서 재미 또는 감동이 있었던 문제에 대해 간략하게 사고과정과 풀이를 작성한다.

 

레드 블루 스패닝 트리 #4792

더보기

파란색 간선을 최소로 써서 MST를 만들어 그때 파란색 간선이 몇개인지 세고,

파란색 간선을 최대로 써서 MST를 만들어 그때 파란색 간선이 몇개인지 세면,

그 사이에 개수가 답이 될 수 있다.

 

풀이 자체는 n년 전부터 알고 있었는데, 이왕 푸는거 증명까지 해보기로 했다.

현재 MST에 파란색 간선이 x개 있을 때, 아래와 같은 과정을 통해 파란색 간선을 하나 추가할 수 있다. (단, 현재 파란색 간선의 개수가 최대가 아님)

 

일단 파란색 간선만 있는 그래프를 생각해 보자. 이 그래프에서 컴포넌트 개수를 C라고 하자.

현재 MST에서 파란색 간선만 남기면, 스패닝 포레스트?가 있을 것이다. 현재 파란색 간선의 개수가 최대가 아니니까, 이 스패닝 포레스트의 컴포넌트 개수는 C 초과일 것이다. 또한 이 스패닝 포레스트의 두 컴포넌트를 이을 수 있는 스패닝 포레스트에 포함되지 않은 파란색 간선이 있을 것이다. 이 파란색 간선을 추가하고, 원래 두 컴포넌트를 잇던 빨간색 간선을 삭제하면 된다.

 

빨간색 간선에 대해서 똑같은 논리를 적용하면 파란색 간선 하나 삭제도 설명할 수 있다.

달리기 #12963

더보기

내가 플로우의 ㅍ자도 몰라도, 최대 유량을 구하라는건 안다...

가중치가 $3^{k}$다. 여기서 나오는 성질을 잘 쓰면 플로우 없이 풀 수 있는 문제라서 Class 8에 있는거 아닐까... 하는 생각을 했다.

$i$번 간선의 가중치가 $3^{i}$니까, 더 작은 번호의 간선을 아무리 써도 $i$번 간선에는 자리가 남는다.

간선의 가중치를 내림차순 그래프에 추가하면서, $0$번 정점과 $N-1$번 정점이 이어지는 순간을 체크하면 되겠다.

$i$번 간선을 추가한 순간  $0$번 정점과 $N-1$번 정점이 이어졌다면, $i$번 간선을 가득가득 쓸 수 있다는 뜻이다. 답에 $3^{i}$를 더하고, 이제 $i$번 간선은 너덜너덜해졌으니까 그래프에서 지운다.

빌라봉 #8872

더보기

포레스트에 가중치가 상수 $L$인 간선을 몇개 추가해 트리를 만들고, 이때의 지름을 최소화해야한다.

컴포넌트가 딱 두개 있는 상황을 생각해 보자. 각 컴포넌트의 어디를 연결해야 될까...

가장 먼 점과의 거리가 최소인 점을 컴포넌트마다 뽑아서 연결시켜주면 되겠다.

일단 각 컴포넌트마다 가장 먼 점과의 거리가 최소인 점을 각각 뽑아주자.

이제 어떻게 연결하지?

그냥 가장 먼 점의 거리의 최솟값이 가장 큰 컴포넌트를 중심으로 해서, 성게 모양으로 이으면 되겠다.

 

트리의 지름을 구할 때 '아무 정점을 골라 거기서 가장 A를 찾고, A에서 가장 먼 정점 B를 찾으면 A-B가 트리의 지름이다'라는걸 어디서 줏어들은 적은 있어서 구현에 활용을 했는데, 증명은 모른다. 일단 귀찮아서 넘겼다.

점프 #17613

더보기

i번 연속으로 거리를 늘려가면서 점프하면 $2^{0} + 2^{1} + \cdots + 2^{i} = 2^{i+1}-1$ 만큼 이동한다.

이걸 그리디 하게 반복하면 최소 점프 횟수가 될 것이다.

구간의 최댓값을 구해야 되는데, 구간의 길이 scale이 $10^9$니까, 뭔가 로그 또는 로그제곱으로 풀릴거 같다는 생각을 했다.

 

구간을 마지막에 연속 점프한 횟수를 기준으로 재귀적으로 분할해 문제를 풀자. $i$번 연속 점프하려면 $2^{i+1}-1$ 이상이어야 하므로, 구간은 대충 로그개로 나눠질 것이다. 이때 대부분의 경우 구간이 $[2^{k}-1,2^{k+1}-2]$ 꼴로 나눠질테니 (약간 세그먼트트리 바이브로) 구간에 대한 답을 map 등에 메모이제이션하면 빠르게 돈다. 아마도 로그제곱?? 인듯

사수아탕 #2419

더보기

사탕을 먹는데 시간이 들지 않으므로, 최적해에 포함된 사탕들은 연속된 구간을 이룰 것이다. 아니라면 그냥 지나가는 사이에 먹으면 되니까...

일단 $dp[s][e]$ := $[s,e]$구간의 사탕을 전부 먹는 최적해 형태로 생각을 해본다. 아하... 시간이 얼마나 흘렀는지를 모르니 구간을 늘릴 때 몇개의 사탕을 먹게될지를 모르니 dp 전이에서 얼마나 더해줄지를 모른다.

 


사탕의 개수가 음수가 될 수도 있다고 하자. 이렇게 해도 답은 제대로 구할 수 있다.

최적해가 $a_1, a_2, \cdots, a_k$위치의 사탕을 순서대로 먹는거라고 해보자. 

$0$에서 $X_{a_1}$ 까지 이동해 $M-abs(X_{a_1}-0))$만큼의 사탕을 먹고,

$X_{a_1}$에서 $X_{a_2}$ 까지 이동해 $M - abs(X_{a_1} - 0) - abs(X_{a_1} - X_{a_0} ) )$만큼의 사탕을 먹고,

...

$M \times k$에 각 $i$에 대해 $i \times (X_{a_i}-X_{a_{i-1}})$만큼 빼준 값만큼 사탕을 먹게된다.

아~ $k$를 고정하고 dp를 돌리면 되겠다.

경주 #5820

더보기

센트로이드 분할은... 왠지 모르게 거부감이 든다.

스몰투라지로 {거리, 정점 개수} map을 관리한다.

map의 전체 원소에 x만큼 더하는 연산이 필요한데, map별로 offset을 따로 저장해두면 O(1)에 할 수 있다.

수열과 쿼리 4 #13546

더보기

개뻔한모스...인데

각 수의 위치를 deque로 관리하는건 뭔가 sexy하지 못하다는 생각이 들었다.

어쨌든 루트질로 잘 풀 수 있다. 한번도 안해본 형태의 루트질이었는데 글로 설명하려니까 어렵다.

http://boj.kr/9f3eac1169ca4d76ac69a4c767966a0a

사실 쿼리 처리 순서 자체는 모스랑 똑같다.

이거 풀면 수열과 쿼리 0도 부분합 배열 만들고 복붙하면 풀 수 있다. 개꿀

 

'PS > 기타' 카테고리의 다른 글

4월 2주차 정리  (0) 2020.04.11

구재원 Jaewon Koo

Email: jjaewon@hanyang.ac.kr

 

학교

  • (2022.03 - Current) 한양대학교 컴퓨터소프트웨어학부 재학
  • (2019.03 - 2021.12) 창원과학고등학교 졸업

대회 참가

  • 2024년
    • (교내 동아리 대회) ALOHA 벚꽃컵 Div.1 (2위)
  • 2022년
    • 2022 ICPC Seoul Regional 장려상 (12위, 3인팀)
    • 2022 ICPC Seoul Regional First Round (26위, 3인팀)
    • 2022 UCPC 본선 (52위, 3인팀)
    • 2022 UCPC 예선 (30위, 3인팀)
    • 2022 숭고한 연합 알고리즘 콘테스트 - Division 2 (2위)
  • 2021년
    • 제 6회 국민대 알고리즘 대회 금상 (2위)

대회 운영

기타 활동

온라인 저지 프로필

대회 중

뇌절했다.

자살 ㅈㅈ

 

대회 후

인터넷 친구들과 링고에 다녀왔다.

신기한 술이 많았다

 

 

UCPC 2022에 sean9892, pentagon03 와 함께 참여했다. 3명 모두 공대 새내기라, 새내기들을 괴롭히는 과목들인 일물실, 일화실, 캘큘을 닉네임으로 하고 팀명을 '새내기 개노답 삼형제' 로 지었다.

 

대회 전

팀 연습은 3번정도(나는 한번 빠졌다) 설렁설렁 했고, 팀연습과 이번 예선 모두 디스코드를 이용해 각자 치뤘다. 전날 했던 SUAPC 2021 Winter 팀연습에서 나름 좋은 폼을 보여줬기 때문에, 괜찮은 결과를 기대하며 예선에 임했다.

 

플레티넘 상위 문제까지 전부 풀었다

대회 초반

ABCD(sean9892) / EFG(jjaewon9) / HIJ(pentagon03) 으로 분할해 문제를 먼저 읽었다.

역시나 A가 가장 쉬운 문제였고, sean9892가 의문의 RTE를 한번 받은 후 AC를 띄웠다.

04:19 A RTE
05:15 A AC (+1) by sean9892

 

그 사이 난 E: 시키는대로 잘 구현 / F: 알파벳 격자 위에서 이상한짓 / G: 적당히 잘 구현 이라는 코멘트를 각각 남기고, G부터 잡으러 갔다. '주어진 입력에 CHAIN을 잘 끼워넣어 ABAB...AB 형태로 만든 뒤, 남은 수들을 한번에 어딘가 잘 끼워넣는다' 는 풀이는 바로 생각했지만, 한시간 넘게 이것저것 구현 디테일 미스와 코딩 미스로 페널티를 신나게 적립했다. 

44:37 G TLE
47:53 G TLE

62:55 G WA

 

pentagon03은 H, I, J를 읽고 H를 잠시 고민하다, J로 넘어간 것 같다. 풀이는 금방 나온 것 같은데, 잘은 모르겠지만 똑같이 이런저런 미스들로 고통받고 있는 것 같았다.

41:10 J WA

 

나와 pentagon03이 0솔의 벽에서 허우적대고 있는 동안, sean9892는 D를 잡으러 갔다. 'set에서 x보다 작은 숫자 개수' 를 지원하는 자료구조가 필요하다면서 bst 구현체를 찾길래, pbds나 kth 세그를 짜라고 이야기했다. pbds 잘 몰?루 라면서 kth 세그를 짜러 간 그는, 출력초과를 잔뜩 안고서 돌아왔다. 고통받고 있던 나, pentagon03과 함께하기로 한 듯 했다.

50:25 D WA
58:06 D WA

64:54 D WA

51분 시점의 상태

뭔가... 조옷된게 느껴졌다.

 

대회 중반

거의 한시간가량을 각자 맞왜틀을 외치며 고통받다가, pentagon03이 J를 AC받아왔다. 파이썬 함수 이슈라는데, 잘 몰루.

58:22 J AC (+1)

 

나도 G를 열심히 고쳐서 AC 받았다. 그냥 이런저런 미스들...

68:12 G AC (+3)

 

여전히 출력초과를 내뿜던 D를 pentagon03이 넘겨받고, sean9892은 H를 잡았다.

난 뭘 잡을지 고민하다 스코어보드를 보니 F가 굉장히 많이 풀려있었고, 다시 읽어보니 생각보다 많이 쉬운 문제길래 들어갔다. 역시 풀이는 바로 나왔지만 G 고통의 재림인가, 또 또 이상한 미스들 많이 박고 패널티를 신나게 쌓다 AC.

89:07 F WA
97:55 F WA
99:36 F WA
105:03 F WA
108:51 F AC (+4)

 

sean9892는 H가 카탈란이다 선언한 뒤 한번 틀리더니 잘 맞아왔다.

83:57 H WA

119:45 H AC (+1)

 

D는 pentagon03이 __int128과 pbds를 함께 박아서 열심히 지지고 볶더니 결국 맞아왔다.

110:28 D WA
117:03 D WA

122:29 D WA
129:26 D AC (+6)

 

대회 후반

마지막 한시간, A D F G H J로 6솔브.

기하+그리디인 B,

단순 구현 문제였지만 실수오차가 두려워서 건들지 않았던 E,

누가봐도 개어려워보이는 C와 I가 남았다.

 

sean9892는 E를 파이썬으로 구현하러 갔고,

난 F를 푼 뒤 pentagon03이 D를 AC띄우는동안 B를 생각해보고 있었다.

선분교차 구현체를 열심히 구글링하면서 징징대니 sean9892이 선분교차 1 코드를 가져다줬다.

증명 없이 이상한 코드로 proof by AC 시도하다 1틀 적립후, pentagon03과 풀이에 대해 이야기했다. 참고로 이건 이번 대회에서 유일한 의논이었다 ㅋㅋ.

개소리 난무

의논 아닌 의논(?) 뒤 B AC.

133:53 B WA
143:25 B AC (+1)

 

잠시 뒤 E도 sean9892가 파이썬으로 열심히 코딩해 AC받아왔다.

144:55 E AC ( - )

 

남은건 남들도 거의 못 푼 C와 I. 셋이서 "이거 ~랑 비슷한데?" "이거 그건가?" "몰?루" 거리며 대충 고민해보다 던졌다. 트롤링 제출로 마무리.

177:40 C WA
179:41 I CE

 

대회 종료 후

10문제 중 8문제를 풀었다. 물론 엄청난 패널티와 함께.

C I는 거의 안풀린듯 하고, 나머지 문제들 중 크게 어려운건 없었으니 8솔에 엄청나게 몰릴 것으로 예상했다. 어쩌만 본선컷이 8솔에 걸치지 않을까... 약간의 걱정을 하며 스코어보드 공개를 기다렸다.

 

 

 

와! 30등!

추가선발 제외한 커트라인은 딱 7솔까지였고, 우리 팀은 8솔 꼴지로 나름 널널하게 본선에 가게 되었다!

페널티를 좀 야무지게 쌓았는데, 셋 다 코딩을 그렇게 꼼꼼히 하는 타입은 아니라 무지성으로 제출하다보니 저렇게 된 거 같다.

예언적중

아무튼 총평을 해보자.

대회 내내 각자 의논 없이 하나씩 풀어나간 거 치고는 우리가 낼 수 있는 최대 아웃풋을 낸 거 같긴 하다. 다만 좀 꼼꼼하게 짜서 페널티를 줄일 필요는 있어보인다. 또 본선에는 각자 잡고 풀만한 문제들 수는 줄어들고 총 시간은 늘어나니, 플레 하위 정도까지 각자 밀고 나머지를 다같이 으쌰으쌰해서 어려운 것 두세개 정도 풀어야한다. 몰라 암튼 잘했음~

 

본선도 화이팅.

 

문제별 코멘트

A 쉬운거.

B 선분교차 + 그리디. 사실상 선분교차가 가장 어려운 부분.

C 트리에서 그리디를 아주 잘 하면 된다 카더라.

D 좌표압축+세그 / pbds.

E 실수오차 신경쓰기 / 파이썬.

F 구현.

G constructive.

H 카탈란 수.

I 몰루.

J 수학? constructive?

 

+ 난 나머지 둘과 다른 대학을 다니고 있어서 icpc 팀도 따로 구해야 한다. 누구랑 하지. 연락주세요...

Link

Tag

  • Union-find
  • 오프라인 쿼리
  • 평방 분할

Time Complexity

  • $O(Q \times (\frac {M}{B} lgM + B^2lgB))$ $(B=BucketSize)$

정점 $N(\leq 50,000)$개, 간선 $M(\leq 100,000)$개인 그래프가 주어진다.

1. $i$번 간선의 가중치를 $w$로 변경

2. 정점 $v$에서 가중치가 $w$ 이하인 간선들만 거쳐서 도달할 수 있는 정점의 개수를 출력

두가지 쿼리가 $Q(\leq 100,000)$개 주어진다.

오프라인으로 처리해도 된다.

 

1번 쿼리가 없을 때는, 간선들을 가중치의 내림차순으로 보면서 컴포넌트의 크기를 세주기만 하면 된다.

 

쿼리에 평방 분할을 적용한다. 아래와 같은 방법으로 $B$개의 쿼리를 한번에 처리한다.

1. 1번 쿼리에 영향을 받지 않는 간선들로만 1번 쿼리가 없을 때 처럼 가중치의 내림차순으로 보면서 union-find를 수행한다.

2. 실제로 2번 쿼리에 답해야 할 때는, 해당 쿼리 이전에 주어진 1번 쿼리들을 전부 고려하면서 union-find를 수행한다. 컴포넌트의 크기를 센 뒤에는 다시 롤백한다.

 

union-find에서 롤백이 필요하기 때문에, path compression이 아닌 size compression이나 rank compression을 적용한다. 어차피 컴포넌트의 크기도 구해야 하기 때문에 size compression을 이용한다. 이는 armotized $O(lgN)$에 동작한다.

1. 과정은 $O(MlgM)$시간이 소요된다.

1번 쿼리는 최대 $B$개 있으므로, 2. 과정은 $O(BlgB)$ 시간이 소요된다.

따라서 총 $O(MlgM+B^2lgB)$시간에 한 쿼리 묶음을 처리할 수 있다.

즉 $O(\frac {Q}{B} \times (MlgM + B^2lgB))$ 에 전체 문제를 해결할 수 있다.

$B=\sqrt{Q}$정도로 잡는게 일반적이겠으나, 실제로는 한 쿼리 묶음의 전처리의 오버헤드 때문인지 $B$를 키우는게 더 빠르게 동작한다. 나는 $B=1250$로 했을 때 가장 짧은 수행시간을 보였다.

 

Code

 

'PS > 문제풀이' 카테고리의 다른 글

BOJ 21607: Polynomial and Easy Queries  (0) 2021.08.17
BOJ 16909: 카드 구매하기 3  (0) 2021.04.02
BOJ 14870: 조개 줍기  (0) 2020.08.02
BOJ 16027: Global warming  (0) 2020.06.14
BOJ 17101: Dynamic Centroid  (0) 2020.06.13

스코어보드

 

2022 숭고한 연합 알고리즘 콘테스트에 Division 2로 참가해 2등을 수상했다. (빨갛게 빛나는 10틀) 아쉽긴 하지만, 대학 진학 후 첫 공식? 대회에 나름 좋은 성적을 거둬 기쁘기도 하다.

 

대회 전

Division 2의 참가조건은

 

  • 숭실대 SCCC / 고려대 Alps / 고려대 Alkor / 한양대 Aloha 의 부원이면서
  • ICPC, SCPC, UCPC, KOI 등 수상 X / solved.ac D3 미만 / Codeforces max rating 1900 미만

이며, 난 한양대 Aloha의 부원이고, 대회 수상이 없고, solved.ac P1, 코포 맥레가 1900이 조금 안돼서 Division 2에 참가했다.

 

대회 신청 후 공지를 읽어보는데 처음에는 zoom을 이용해 참가자 캠과 화면 녹화를 한다는 이야기가 있어서 좀 걱정했는데, 대회 전날 온 이메일에는 인터넷 검색을 허용하며 별도의 모니터링 없이 진행한다고 수정돼 있었다. 고등학교 2학년 초반 쯤 까지는 PS를 좀 열심히 하다 손 놓고 쉬엄쉬엄 한 지 거의 2년이 다 되어가서 연습을 좀 해야되나 걱정했지만, 인터넷 검색 허용이라길래 그냥 말았다.

 

온라인으로 치뤄지기 때문에 난 본가에서 참여했고, 4시간동안 진행될 대회에 대비에 대회 직전 니코틴 풀 충전 및 카페인 음료 한 캔 구매 후 책상 앞에 앉았다.

 

대회 중

문제는 A ~ H 총 8문제가 있었다. 난이도 순 일거라 믿고 A부터 열었다.

 

브론즈5가 하나 있었다. 예제도 안 돌려 보고 냈다. 퍼솔.

여담으로 나보다 늦게 제출한 코드가 먼저 채점이 돌아 스코어보드에 떴고, 퍼솔 놓친 줄 알았는데 나중에 보니 내가 퍼솔이더라.

A AC (0 : 00, First to solve)

 

B를 읽었다. 문제가 너무 길어 어지러웠다. 넘겼다.

 

C를 읽었다. 문제가 너무 길어 어지러웠다. 넘겼다.

 

D를 읽었다. 뭔가 적당한 그리디? constructive 문제같았다. 나중에 보기로 하고 넘겼다.

 

E를 읽었다. 처음에는 문제를 잘못 읽어 '연속으로 쉬는 날'의 최솟값의 최댓값를 구하라는 줄 알고 부분합 + 파라메트릭 풀이를 짰다. 예제가 안나오더라. 뭔가 잘못 짠게 있나 열심히 들여다 봤다. 맞는거 같았다. 한 30분쯤 씨름하다가 (예제를 손으로 풀어봤다면 잘못 읽었다는걸 일찍 알고 고쳤을텐데...) 말린 거 같아 나중에 보려고 넘겼다.

 

이때가 한 40분 시점. 시간을 한참 버려 걱정했는데, 스코어보드를 보니 1등이 ABC 3솔, 1솔인 나도 6위에 위치해 있었다. 패널티가 좀 걱정되긴 하지만, 극복 못할 차이는 전혀 아니며 문제 수로 벌리면 되겠다 생각했다.

 

F를 읽었다. 특정 정점들을 모두 지나는 최단경로...? 정점이 하나면 다익스트라 두번 돌리면 될텐데... 여러개면 어떻게 하지? 잠시만 이거 근데 TSP 아닌가? 순간 멘붕. 하지만 잠시 생각을 해 보니 어차피 무조건 그래프의 최단경로로 가야 의미가 있으니, '다익스트라를 돌리되 정점을 선택할 때 거리만 고려하는게 아니라 {거리, 지나온 특정 정점의 개수} pair로 비교'하면 되겠구나 하는 생각이 들었다. 열심히 짜고 1트에 맞았다. 퍼솔.

F AC (1 : 10, First to solve)

 

C로 돌아왔다. 열심히 읽어보니 그리디나 dp로 될거같긴 한데 생각하기 귀찮았다. N 제한이 비트마스킹으로 완전탐색 해도 될거같이 생겼다. 몇가지 구현에 헷갈리는 점이 있었지만 열심히 짜서 맞았다.

C AC (1 : 32)

 

B로 돌아왔다. 지문이 길고 문제 상황이 복잡하다. 뭘 하라는 건지 이해하는 데에만 20분은 걸린 거 같다. 특히 '현재 모닥불에서 머물거나 인접한 모닥불로 이동해 장작을 넣는다' 가 '[현재 모닥불에서 머물거나] [인접한 모닥불로 이동해 장작을 넣는다]' 인지 '[현재 모닥불에서 머물거나 인접한 모닥불로 이동해] [장작을 넣는다]' 인지 헷갈려서 운영진에게 질문을 했고, 후자라는 답변을 받았다. (이후 이 사항은 공지에도 올라왔다.) 아무튼 적당히 이해된거 같았고, 이것 역시 열심히 완탐하면 되는거 같아 열심히 짜서 제출했더니... 틀렸다! 문제를 다시 읽어보니 잘못 이해한 부분이 있어 (그런데도 채점이 60%까지나 돌았다) 수정하고, 이런저런 이슈로 몇번 틀리고 나서야 AC를 띄울 수 있었다.

B WA (2 : 01) (-1)

B WA (2 : 03) (-2)

B WA (2 : 10) (-3)

B AC (2 : 11) (+4)

 

D로 돌아와 생각을 잠시 해 보다 딱히 떠오르는게 없어서 E를 잡았다. 예제 3을 손으로 풀어보니 내가 문제를 완전 잘못 이해했다는걸 깨달았다. 어쨌든 파라메트릭이라는 큰 틀은 똑같고, 결정문제는 dp로 해결해주면 된다. $dp[i] = dp[j] + W[i]\;(j<i)$ 를 계산해야 하는데, 나이브하게 하면 $O(n^2)$ 이고, prefix max를 이용하면 선형으로 줄일 수 있다.

E AC (2 : 22, First to solve)

 

G를 열었다. G는 간선이 딱 N개니 간선 하나만 제외시켜 트리로 만든 다음, 남은 간선 하나는 잘 관리하면 되겠다는 생각이 들었다. 경로에 연산하는건 HLD로 잘 펼친 다음 쿼리는 마지막에만 날리니 누적합으로 처리하면 $O(NlgN)$에 할 수 있을거다. 근데 구현이 귀찮아보여서 일단 넘어갔다.

 

H를 열었다. 원형이니 선형 두개 이어붙여서 잘 처리하면 될거고... 쿼리 생긴게 보니 딱 봐도 레이지 같긴 한데 노드를 어떻게 정의해야 될 지 모르겠더라.

 

대회 시간은 90분 정도 남았고, E를 퍼솔하면서 단독 5솔로 1위인 상태다. 다만 나는 B C를 늦게 풀었을 뿐더러 B에서 패널티를 많이 쌓았으니, 공동 5솔일 경우 2위로 밀릴 게 뻔했다. 당시 2위는 A B C F를 풀었고, E가 크게 어렵지 않으니 곧 5솔로 올라올 것 같았다. H는 전혀 모르겠고, G는 열심히 짜면 될 거 같았고, D는 당장 생각나는건 아니지만 앞쪽에 있는걸 보면 적당히 잘 하면 될거라는 믿음을 가졌다.

따라서 한시간 정도를 G에 투자해 AC를 띄운 후, 남은 시간동안 D를 고민하기로 계획을 세웠다.

 

그리고...

-틀-

여러가지 이유로 구현 미스와 이상한 주장을 5번쯤 해서 틀리고 열심히 고쳤지만, 끝까지 AC는 띄우지 못했다. 아마 어딘가에 구현 미스가 있거나, 내가 생각하지 못한 케이스가 있을지도. 아무튼 10틀을 박고, 장렬히 전사했다.

 

마치며

G 풀이를 보니, 내가 짜려고 한 것과 방향성은 비슷하지만 몇가지 처리를 더 해서 훨씬 구현을 간단하게 만들었더라. 앞으로는 문제를 풀 때 자세한 구현 스펙과 더 간단히 하는 방법은 없는지 생각해보고 키보드 잡는 버릇을 들여야겠다.

 

대회의 퀄리티는, 내가 대회를 많이 참여해 본 적 없어서 모르겠지만, B C 둘 다 지문 개판 + 노잼 완탐이었고 전체적으로 educational한 문제가 없었던거 같아 아쉬웠다.

 

G를 풀었다면, G를 풀고 남는 시간에 D를 잡아서 풀었다면... 하는 생각이 머리에서 떠나질 않지만 그래도 2등이니 기분은 좋다. 키보드 77ㅓ억

'PS > 대회 후기' 카테고리의 다른 글

UCPC 2022 본선 후기  (0) 2022.07.24
UCPC 2022 예선 후기  (2) 2022.07.02
제 6회 국민대 알고리즘 대회 후기  (3) 2021.08.13
제 5회 국민대학교 알고리즘대회 후기  (3) 2020.08.15

Link

Tag

  • Segment Tree
  • Spare Table

Time Complexity

  • $O(Q(lgN+lgQ)+XlgX)$ $(X=100003)$

$f(x)=2x^2-1, g(x)=4x^3-3x$이고, 길이 N의 수열 $A$가 주어진다. $f,g$를 구간에 적용하는 쿼리와 $A_i$를 $100003$으로 나눈 나머지를 구하는 쿼리가 주어진다. 이러한 쿼리를 $Q$개 처리해야 한다. 일단 $f,g$가 곱셈으로만 이루어져 있으니 나머지를 구하는건 그냥 해주면 될거 같고, $f,g$를 어떻게 하느냐가 문제다. 근데 왜 하필 $f,g$를 저렇게 줬을까? 뭔가 특별한 성질이 있나? 결론부터 말하자면 $f \cdot g = g \cdot f$다. 그래서 1,2번 쿼리가 어떤 순서로 들어왔는지는 중요하지 않고, 각각 $A_i$에 $f,g$가 각각 몇번 적용되었는지 알아내고 빠르게 계산할 수 있으면 된다.

 

$f,g$가 각각 몇번 적용되었는지는 range-update point-query 세그먼트 트리 두개면 된다. 실제 $A_i$를 빠르게 계산하는건 Sparse Table로 전처리하면 $O(lgQ)$에 가능하다.

 

Sparse Table 전처리에 $O(XlgX)$ $(X=100003)$, 1,2번 쿼리당 $O(lgN)$, 3번 쿼리당 $O(lgN+lgQ)$에 처리 가능하다. 대충 엔로그엔~~

Code

'PS > 문제풀이' 카테고리의 다른 글

BOJ 17635: 다리  (0) 2022.04.25
BOJ 16909: 카드 구매하기 3  (0) 2021.04.02
BOJ 14870: 조개 줍기  (0) 2020.08.02
BOJ 16027: Global warming  (0) 2020.06.14
BOJ 17101: Dynamic Centroid  (0) 2020.06.13

제 6회 국민대 알고리즘 대회에 참가했다...! 작년에 본선에서 화장실 이슈(?) 로 아쉽게 장려상을 받아서 이번에는 정말 열심히 준비한..... 건 아니고 그냥 무지성으로 신청했다.

 

문제를 공개하면 안되나? 그래서 풀이는 대충 쓰도록 하겠다.

 

예선

올해도 온라인으로 1시간동안 진행됐다. 원래 12시 반 ~ 1시 입실에 2시 시작인데, 뭔가 문제가 있었는지 1시 이후에야 입실이 가능했다. 뭐 2시 시작이라 진행에 차질이 생기지는 않았다.

 

1번은 2차원 부분합을 구하는 문제였는데, 문제 지문에 대놓고 'prefix sum을 써라'고 적혀있었다. 뭘까....

 

2번은 대충 pq에 pair박으면 된다.

 

200점 15분컷내고 본선에 진출했다.

 

본선

본선은 국민대학교 미래관에서 2시~4시에 오프라인으로 진행되었다. 작년과 똑같이 비행기타고 당일치기로 다녀왔다. 작년과의 차이점이라면 코로나가 심해져서 서울 구경은 못하고 바로 왔다는 점?

 

1번은 주어진 좌표를 모두 통과하면서 조건을 만족하는 적절한 경로를 찾는 문제였다. x좌표가 같은 점끼리 묶고 $O(N)$짜리 dp를 하면 된다. 보자마자 dp풀이를 생각하긴 했는데 뭔가 구현이 귀찮을거 같고 더 쉬운 풀이가 있을거라 생각해 이상한 그리디를 짜다가 15분을 버렸다. 35분정도를 쓰고 AC.

 

2번은 이거였다. 그냥 짰다. 인덱스 실수를 몇개 해서 고치고 47분에 AC.

 

+ 블로그 전전글이 작년 5회 대회 후기인데, 블로그 좀 열심히 써야겠다는 생각이 든다.

 

[08.20 수정]

금상을 받았다!

Link

Tag

  • 스택

Time Complexity

  • $O(N)$

수열 $A$가 주어지고, $A$의 모든 구간 $[s,e]$의 최댓값-최솟값의 총 합을 구하는 문제다.

최댓값의 총 합과 최솟값의 총 합을 각각 구하자.

각각의 $A_i$에 대해 $A_i$보다 왼쪽에 있으면서 $A_i$보다 큰 수 중 가장 오른쪽에 있는 수의 인덱스를 $s_i$, $A_i$보다 오른쪽에 있으면서 $A_i$보다 큰 수 중 가장 왼쪽에 있는 수의 인덱스를 $e_i$이라 하자. 그러면 구간 $[a,b]$ $(s_i \le a \le i \le b \le e_i)$ 의 최댓값이 $A_i$가 된다. 그러한 구간의 개수는 $(i-s_i)(e_i-i)+e_i-s_i+1$이다. 즉 최댓값의 총 합은 $A_i \times ((i-s_i)(e_i-i)+e_i-s_i+1)$의 총 합이다.

$s_i$, $e_i$는 스택으로 쉽게 구할 수 있다. (boj 17298 오큰수)

최솟값에 대해서도 똑같이 하면 되는데, 이때 그냥 모든 수의 부호를 뒤집어서 정확히 똑같은 과정을 진행시키면 된다.

Code

 

'PS > 문제풀이' 카테고리의 다른 글

BOJ 17635: 다리  (0) 2022.04.25
BOJ 21607: Polynomial and Easy Queries  (0) 2021.08.17
BOJ 14870: 조개 줍기  (0) 2020.08.02
BOJ 16027: Global warming  (0) 2020.06.14
BOJ 17101: Dynamic Centroid  (0) 2020.06.13

국민대학교에서 알고리즘 대회가 있었다.

왠만하면 본선은 붙지 않을까 + 붙으면 서울 구경이나 해야지 하는 생각으로 예선을 신청했는데...

예선

예선은 온라인으로 한시간동안 진행했다. 캠 켜고 핸드폰 켜고 귀찮았다.

 

1번은 어디서 많이 본 문제였다. https://codeup.kr/problem.php?id=3095

걍 뚝딱 풀었다. 4분?

 

2번은 사다리타기를 시뮬레이션 하는 문제였다. 간선이 10만개였나?

간선을 단방향으로 분리해서 생각해보면 어차피 한번씩밖에 안지나간다. 그래서 대충 lower_bound 같은거 때려가면서 $O(lgN)$에 간선 따라가는 풀이를 구상했다.

어... 근데 구현이 어렵더라. 한시간 내내 디버깅하다 결국 제출 한번 못해보고 시간이 끝났다.

 

문제는 둘 다 쉬웠다. 근데 내가 개못했을 뿐... 200점 만점에 100점을 받았다.

대회 끝나고 나서 든 생각은 본선 절대로 못가겠구나 싶었다. 본선 커트가 100점에 걸리면 빨리 풀었으니 갈수도 있겠지 하며 기도메타를 시전했다. 근데, 결과 보니 본선 커트 낮아도 한참 낮더라. 8X점인걸로 알고 있다.

 

본선

본선은 국민대학교 미래관에서 오프라인으로 진행했다. 창원에 사는 나는 무려 비행기를 타고 당일치기로 다녀왔다.

 

1번은 이거 였다. 읽고 그래프 만들고 도달가능성 따지면 될 거 같은데 당장 생각나는건 N번 탐색밖에 없었다. 근데 N이 10,000이길래 제곱은 안되겠구나 싶어서 이상한 풀이들을 막 생각했다. dfs 스패닝 트리에 스몰투라지에 뭐 이상한거 막 생각하다가 시간은 30분가량이 흘렀고, 에라 모르겠다 하고 N번 dfs를 돌리는 풀이를 짰다. 근데 만점 맞더라. 40분 조금 넘었을 때 2번으로 넘어갔다.

 

2번 문제는 일단 지문과 예제가 상당히 더러웠다. 아니 프로그래머스 예제 vector로 좀 안줬으면 좋겠다. 깔끔하게 보여주면 얼마나 좋아.

union-find로 같은 그룹을 묶어주고 물건을 나눌때는 prefix sum으로 더해주면 된다. 풀이는 바로 생각했고 짜기 시작했는데, 문제가 생겼다. 화장실이 너무 급했다 ㅋㅋ. 아무튼 화장실 다녀 와서 편하게 짜고 디버깅 몇번 하다가 만점을 받았다.

 

아마 1시간 15분쯤 퇴실했던 거 같고 먼저 나와있던 사람에 의하면 7번째로 나왔다고 한다. 동상 컷이 6등이던데 동상을 받을 수 있을까?

 

[08.24 수정]

장려상 받았다. 장려상 1등인듯.

80점도 장려 200점도 장려 할많하않...

+ Recent posts