2024년 9월 둘째 주 PS 일지

9/9 월요일

1708 볼록 껍질: 볼록 껍질 알고리즘을 배워서 풀었습니다. (클래스 6 밀기)

32145 매우 강한 연결 요소: 바로 반년 대회에 출제됐었던 볼록 껍질 문제를 해결했습니다.

3679 단순 다각형: yigzo에게 힌트를 얻고 풀었습니다. (클래스 6 밀기)

1948 임계 경로 (클래스 6 밀기)

5719 거의 최단 경로 (클래스 6 밀기)

14942 개미 (클래스 6 밀기)

11280 2-SAT -3: 2-sat 알고리즘을 배워서 풀었습니다. (클래스 6 밀기)

17401 일하는 세포: 행렬 개념을 모르지만, 태그를 보고 행렬 거듭제곱인 것 자체는 알고 있었고 뭔가 입력값을 행렬에 넣고 거듭제곱하면 될 것 같아서 했더니 풀렸습니다. (클래스 6 밀기)

 

9/10 화요일

13141 Ignition: 살짝 어려웠습니다. (클래스 6 밀기)

20149 선분 교차 3 (클래스 6 밀기)

3648 아이돌 (클래스 6 밀기)

11281 2-SAT -4 (클래스 6 밀기)

5670 휴대폰 자판: 트라이를 제대로 공부하기 전에 아호 코라식을 공부했었는데 그래서인가 쉽게 풀었습니다. (클래스 6 밀기)

19585 전설 (클래스 6 밀기)

4225 쓰레기 슈트 (클래스 6 밀기)

1533 길의 개수: 풀이를 보고 구현했습니다. 행렬이라는 개념 자체를 아직 모르기 때문에 2학년 때 배우고 나서 제대로 파봐야겠다고 결심했습니다. (클래스 6 밀기)

1214 쿨한 물건 구매 (클래스 7 밀기)

 

9/11 수요일

3295 단방향 링크 네트워크 (클래스 7 밀기)

 

Codeforces LATOKEN Round 1 (Div. 1 + Div. 2)

Kawaii2DIdolOfGSHS, jaewoo2009, realpsdoingdamyoo, ryansmg6496, lupin0000, minchan_bae와 버추얼을 돌았습니다.

A, B, C는 엄청 쉬워서 22분 만에 빠르게 풀었고 D를 1시간 30분 동안 잘못된 풀이로 접근하다가 결국 풀지 못했습니다. 이후 Kawaii2DIdolOfGSHS의 컬러링을 해서 푸는 풀이를 듣고 업솔빙을 했습니다. 사실 대회가 3시간 셋이라서 업솔빙 할 때 대회가 안 끝난 줄 모르고 제출했다가 대회에 반영돼서 정확한 퍼포먼스는 모릅니다. 그래도 민트~블루 하위 사이 퍼포였을 것 같습니다.

 

9/12 목요일

3640 제독: MCMF에서 양방향 간선에 대해 어떻게 처리할지 고민했었는데 정점 분할을 하면 된다는 것을 배우게 된 문제입니다. (클래스 7 밀기)

14286 간선 끊어가기 2: MFMC를 배웠습니다. (클래스 7 밀기)

1420 학교 가지마! (클래스 7 밀기)

3683 고양이와 개 (클래스 7 밀기)

 

9/13 금요일

1605 반복 부분문자열: 접미사 배열과 LCP 배열을 이용해서 푸는 문제인데 해싱을 배우고 해싱으로 풀었습니다. 해싱은 뭔가 WA가 났을 때 해시 충돌 때문에 발생한 것인지 구현의 문제로 틀린 것인지 헷갈려서 개인적으로 마음에 들지 않습니다. (클래스 7 밀기)

3033 가장 긴 문자열

 

9/14 토요일

Codeforces Round 868 (Div. 2)

mj1000j, KUHYAKU, minchan_bae, necu1029와 버추얼을 돌았습니다.

A에서 자잘한 실수 한번 하고 C까지 수월하게 풀었고 D를 고민하다가 약간 찍어서 맞혔습니다. E부터는 풀지 않았습니다.

퍼플 퍼포가 나왔습니다.

 

ABC 371

앳코를 쳤습니다. A, B와 비교적 쉽게 나왔던 D, E를 빠르게 밀고 문제가 살짝 복잡했던 C를 해결했습니다. 이후 DADAS가 G를 시도하는 것을 보고 저도 G를 잡았습니다. 약간 자명한 그리디 풀이를 찾고 중국인의 나머지 정리와 그래프 탐색으로 잘 해결해 줬는데 맞왜틀을 여러 번 겪었고 CRT에 문제가 있는 줄 알았습니다. 알고 보니 큰 수 여러 개에 LCM 연산을 해서 오버플로우가 나서 생긴 문제라는 것을 깨닫고 파이썬으로 바꾼 뒤 AC를 맞았습니다. F를 잘 읽어보지도 못하긴 했는데 결국 이득이 됐습니다. 대회 끝나고 읽어보니 레이지 세그먼트 트리와 파라메트릭 서치를 잘 해주면 되는 문제 같았습니다. 

결과적으로는 옐로우 퍼포가 나왔고 블루를 달성했습니다. 코포 퍼플보다 앳코 블루를 먼저 달성했으므로 아무래도 전 발상을 요구하는 문제들보단 전형적인 문제가 더 잘 맞는 것 같습니다..

 

Codeforces Round 972 (Div. 2)

코포를 쳤습니다. 오전에 했던 버추얼에서 D와 A가 유사하길래 D와 비슷한 사고방식으로 접근했다가 5틀 정도를 하고 결국 시간 안에 풀지를 못했습니다. 그래도 B1, B2는 빠르게 풀었고 C를 결국 풀어서 블루 퍼포가 나왔고 양수 델타가 뜨긴 했습니다. E1 셋을 이용한 풀이법으로 접근하다가 틀렸는데 사실 왜 틀렸는지는 잘 모릅니다... 대회가 끝나고 나서 A 업솔빙을 하고 E1 DP 풀이를 듣고 업솔빙했습니다.

 

9/15 일요일

32266 Nile: IOI 2024 셋을 보면서 그나마 해볼 만하고 태그에 세그먼트 트리, 오프라인 쿼리, 분리 집합이 있어서 쉬운 자구비빔밥이구나 하면서 시도했습니다. 66점 풀이까지를 그냥 쉬운 DP로 접근했는데 그래서 풀테를 생각해 내기 어려웠습니다. 그리고 KUHYAKU에게 질문해서 무게 차이가 $D$ 이하인 것들을 분리 집합으로 하나의 컴포넌트로 묶어준다는 아이디어와 묶어 준 뒤에 세그먼트 트리를 이용해서 최솟값을 구해줄 수 있다는 아이디어를 들었습니다. 세그먼트 트리를 이용해서 최솟값을 구해줄 수 있다는 것이 잘 이해가 안 돼서 생각해 보다가 그냥 분리 집합 하나로만 해결할 수 있을 것 같아서 구현을 해줬고 맞았습니다.

 

Codeforces Round 848 (Div. 2)

mj1000j, KUHYAKU 와 버추얼을 돌았습니다.

약간 얻은 게 많은 대회였습니다. C 덕분에 여러 개의 조합을 prev_permutation 함수로 효율적으로 구하는 방법을 알게 됐고, D 덕분에 분수 연산을 정수 연산으로 바꿔서 간단하게 계산하는 법을 배웠습니다. D가 완전 깡 수학 기댓값 구하기 문제가 나왔기 때문에 더욱 유리했고 오렌지 퍼포가 나왔습니다.