[10월]

분명 9월에 글 쓸 때는 1달보다 적은 간격으로 일기를 쓸 줄 알았다. 변명을 해보자면 시험기간이라서 여유롭지 못했다! snupc 검수와 카이스트 가을 대회도 있었고 ps도 못하고 그래서 안 썼다. 이제 써야지 후후

아래에 2023 snupc와 카이스트 가을대회에 대한 스포일러가 조금 있다. 주의!

 

코드포스 말아먹음

div1 코드포스를 말아먹고 시작한다. 왜 말아먹었냐 잠깐 설명을 하자면

1) B번에 케이스워크 문제가 나왔는데 이런 문제에 약하다.

2) C번에 쉬운 조합 문제가 나왔는데 1)로 인해서 시간도 없고 그냥 내가 구현을 잘 못해서 구현하다가 끝났다. 참고로 다음날 일어나서 코드 조금 고치니까 맞았다.

 

 

코드포스 레드 달성!

그 다음 코드포스에서 떡상했다. D번 문제는 그냥 정리할 것을 정리하면 풀리는 문제라서 D번 위치보다 쉬운 것 같다. 

E번 문제는 보고 일단 n^3 knapsack dp가 바로 떠올랐다. 그래서 이것을 n^2으로 우겨넣을 생각을 하고 있었는데...

1) xor의 성질을 이용하면 dp 테이블에서 사용하는 상태의 수를 줄일 수도 있다.

2) dp의 전파를 사실 n^3번 하지 않아도 된다.

3) 신기한 관찰로 문제가 풀린다.

와 같은 생각들을 하면서 문제를 풀었지만 생각에 진전이 없었다. 그러다가 2의 갈래에서 '사용하지 않아도 되는 구간'의 성질이 나왔고, 이것으로 dp를 전파했을 때 n^3을 꽉 채우는 케이스를 머릿속으로 만들 수 없기도 하고 사람들이 많이 풀기도 했어서 커팅해서 제출했는데 맞았다. 사실 아직도 왜 맞는지 잘 모른다.

 

그리고 F번 문제를 풀었다. 이 문제는 어떻게 풀게 되었냐면

1) 어떤 숫자 x가 주어졌을 때 x보다 빨리 오는 수의 개수를 세려고 했다.

2) 자릿수를 고정하면 개수를 셀 때 편하다. 자릿수를 p로 고정했더니 x/k^a의 꼴의 합으로 나타났다. (a 중에 0 이하의 수도 있다)

3) 그래프가 머릿속에 그려졌는데 굉장히 가파라서 이분탐색을 해야겠다고 생각했다.

와 같은 프로세스로 문제를 풀었다. 그래프가 머릿속에 떠오른 것이 크지 않았나 싶다.

 

암튼 그렇게 해서 레드를 찍었다. 백준에 닉네임이 빨간색으로 나오니까 기분이 좋았다.

 

 

snupc 2023

그리고 snupc 검수를 했다. 서울대 대회 문제들은 항상 문제 퀄리티가 좋은 것 같다. 검수를 조금 늦게 시작해서 호다닥 검수해야 한다는 점이 있다. D3 이상은 못 풀겠어서 못 건드렸고, 나머지 문제들은 거의 풀어봤다. 나름 기억에 남았던 문제들을 말해보자면

V: 선형대수학에 많은 조건 분기 문제였다. 처음에는 쉬워보였는데 디테일이 양파처럼 계속 나오는 문제가 신기했다.

마술 도구: 초등학생때 어떤 수를 생각하라고 한 뒤에 수가 몇 개 쓰여진 준비된 카드를 주고 자신이 생각하는 수가 들어있는 카드를 모두 말해주면 수를 맞추는 마술이 친구들 사이에서 유행했다. 이때는 decision tree도 몰랐고 수학 문제로 환원도 못해서 신기하네 하고 넘겼는데 지금 푸니까 바로 수학적으로 접근이 되어서 재미있었다. 초등학생때의 나보다 수학을 잘한다.

문자열 만들기 2: ad-hoc이라서 재미있다. (물론 다른 문제들도 거의 ad-hoc이지만 이것은 더 ad-hoc이다)

히스토그램 K개 빼기: blackking26이 만들고 내가 푼 문제이다. 고등학생때 같이 문제를 많이 만들었는데, 대학생이 되어서도 가끔 문제를 주고받으면서 만들었다. 이 문제가 그중 하나이다. 하지만 빠른 n^3이 통과하는 바람에 오픈컨테스트로 넘어갔다.

 

 

snupc를 검수하고 나서 바로 카이스트 가을 대회가 열렸다. 나는 4문제를 출제했고, 각 문제에 대한 비하인드 스토리는 다음과 같다.

Simple Link Cut Problem: 옛날에 트리 정리하기라는 문제를 낸 적이 있다. 그것은 트리의 지름을 4 이하로 줄이는 문제였다. 그 당시에 트리의 지름을 3으로 줄일 수 있을 것이라고 생각하고 문제를 풀었는데 풀지 못하고 지름을 4 이하로 줄이는 문제로 냈다. 그리고 지름을 3 이하로 줄이는 문제는 미해결로 남았다. 나중에 수학올림피아드 국대 친구에게 문제를 던져줬더니 2시간만에 풀어와서 문제를 내게 되었다. 검수진들도 잘 푸는 것 보면 다들 어떻게 문제를 잘 푸는지 신기하다.

Good Triangle: 고등학생 때 blackking26, 79brue와 함께 코드포스 div1 라운드를 열겠다는 생각으로 문제를 만들었던 적이 있다. 그 때 나온 문제들 중 하나이다. 아쉽게도 코드포스 라운드는 열리지 않았지만, 그 때 만든 문제들을 가끔 하나씩 꺼내서 사용한다. 옛날에 만들었음에도 불구하고 잘 만든 것 같다.

HLD: 런대회 출제를 마음먹고 만든 문제이다. Heavy light decomposition을 쿼리에 따라서 조금 더 빠르게 할 수 있지 않을까? 라는 궁금증으로 시작한 문제이다. 흥미롭게도 문제의 결론은 Heavy light decomposition은 잘 만들어진 알고리즘이라는 것이다. 문제가 굉장히 수월하게 풀렸다. 이제 나도 자구비빔밥 출제자다.

Swapping Brackets: 난이도 커브를 위해서 만든 문제이다. 원래는 i번 bracket과 j번 bracket을 swap할 때 A[i][j]의 비용이 들 때 올바른 bracket으로 만들기 위한 최소 비용을 구하는 문제였다. A를 일반적인 배열이 아니라 A[i][j]=max(B[i], B[j])와 같은 꼴로 만들었을 때 어떻게 되는지를 생각했다. 그리고 사용한 swap의 비용 중 최댓값을 최소화하는 문제로 바꾸는 것에 대해서 생각을 했다. 바뀌는 괄호들을 관찰했더니 )))(((가 ((()))로 바뀌는 것을 확인하고 이 관찰에 dp를 얹으면 좋겠다고 해서 생긴 문제이다. 예쁘고 전형적이게 만든 것 같아서 좋다.

 

 

JOISC 2016/2017

SongC한테 JOISC 2016/2017 문제 추천해달라고 했더니 이것을 줬다. 첨에 봤을 때는 다항시간 알고리즘도 안 떠올랐다. 침대에 누워서 곰곰히 생각했는데 '물을 못 먹어서 버스를 나간다'를 '물을 주는 시점 전에 있는 일정한 시간 구간에 대해서 사람들을 버스 밖으로 나가게 한다'로 생각했더니 슥슥 풀렸다. 문제 풀 때에는 문제를 보는 관점이 중요한 것 같다.

이 문제에는 CHT가 사용된다. 예전에 SCPC에서 CHT 구현하다가 말아먹은 경험이 있어서, 구현하기 전에 간결한 CHT 구조체를 만들겠다고 마음먹었다. 그래서 땅따먹기(6171) 문제로 가서 사람들의 CHT 코드를 봤다. 나는 직선을 관리할 때 (직선 시작 위치, 직선 식)을 stack으로 관리했는데 다른 사람들은 직선 시작 위치를 저장하지 않고 직선을 stack에 삽입삭제할 때 그때그때 두 직선의 교점을 구하는 것을 보고 나도 그러한 방식으로 고쳤다. 그리고 항상 같은 기울기가 여러 개 들어가는 경우에 대해서 고민을 했는데, 그냥 직선 삽입하기 전에 마지막 직선이랑 비교만 해주면 된다는 것을 깨달았다. 덕분에 예쁜 cht 구조체를 만들었다.

시험이 끝난 나는 시간부자다. ps 열심히 해야겠다.