더불어민규당 Petrozavodsk 2019 Winter 직전 연습

1월 22일 연습

오후: ARC 064

	C	D	E	F
ainta (guest)	36:35	49:33	43:44	34:33
tncks0121	2:48	23:38	9:23	59:19
koosaga	3:30	97:56	31:58	-

실제 연습 환경에서 한 게 아니라 변동 사항이 있을 수 있다. (아인타는 약간 늦게 합류했고, 집중할 수 있는 상황이 아니었고, 등등..)

하지만 내가 문제를 못 푼 건 그래서가 아니었다. 일단 D의 풀이를 보는데 한 30분 정도를 사용했고, F를 보고 풀 수 있다고 생각하고 너무 과도하게 달려들었던 것도 참패 요인이다.

F는 내가 보통 거르고 보는 약수 포배 유형이다. 풀이를 들었는데 웬만큼 잘 생각하지 않았으면 못 풀었을 문제인 것 같다. 그런데 그런 유형인지를 모르고 E를 푼 이후 F로 넘어갔다. 지금 돌아보면 원순열과 비슷하게 rotating한 것중에 같은 것을 빼주는 것이니 약수로 논리 전개를 하는 것이 당연한 것 같은데, 그 때는 잘 몰랐다.

정말 반성해야 할 것은 D인데, 풀이가 상당히 간단하고 그 근처까지 갔던 것 같으나 어째서인지 계속 복잡하게 생각하고 헤메다가 풀이를 찾지 못했다. 초기에 계속 생각이 안 나서 나중에 F를 포기한 이후에야 다시 돌아왔고 그 때 풀었다.

밤: JAG Summer Camp 2017 Day3

ainta는 연습하고는 상관없다.

뻘짓을 여럿 했으나, 셋 돌면서 그런 걸 안 하는 게 더 이상하니 (...) 감안하면 꽤 만족스럽게 했다. 혼자서 올솔하기는 쉽지 않은 셋으로 보인다.

문제는 JAG치고 실망스러웠다. 아이디어를 떠올리는 건 거의 어렵지 않고, 그냥 구현만 엄청 많이 하는 셋.

 

1월 23일 연습

밤: Asia Yokohama 2018

나랑 수찬이랑 팀으로 참가했다. 모든 문제를 풀고 리저널 챔피언도 했다. 최고~~

E F는 수찬이가 풀고 나머지는 전부 내가 풀었다. 스코어보드 없이 해서 순서가 약간 뒤바뀐 것 같긴 하다.

• G는 풀이를 잘못 생각해서 말리기 직전까지 갔다. 다 짰는데 반례가 나왔을 때 머리가 띵해졌다 (...) 특히 스코어보드도 없는 상황이라, 정말 무서웠다. 알고 보니 간단한 문제.
• 구사과 블로그를 성실히 읽은 자는 H를 쉽게 풀 수 있다. 그냥 5색 정리랑 똑같은 방법으로 Kempe Chain을 잡으면 된다. Kempe Chain 비슷한 걸 더 생각해 보고 싶은 사람은 CERC 2008 Two Professor를 풀어보면 좋을 듯.
• I는 행렬의 rank를 가지고 잘 사바사바해야 했던 문제이다. 끝까지 풀이가 안 나와서 수찬이랑 계속 이야기를 하면서 풀었다. 완벽한 증명을 하기가 버거워서, 거의 직관에 의존해서 풀이를 접근했고, 다행이도 그 직관이 잘 맞아서 AC.
• J는 do you know dfs ordering. 우리 팀은 저게 E~K 중 가장 쉬운 문제였다. 자료구조 조아.
• K 역시 꽤 쉬운 문제였는데 우리는 게임이라는 키워드가 나와서 한참을 안 읽었다 (...)

E / F는 말리기 좋은 문제들이었는데 뒤에서 수찬이가 잘 밀어줘서 나머지 문제들을 정말 순조롭게 밀 수 있었다. F는 컴퓨터 빌 때마다 계속 잡는 식으로 하다가 아주 깔끔하게 밀렸다. 팀워크도 괜찮았고 문제도 잘 풀렸고. 오랜만에 대회를 순항해서 기분이 좋았다.

 

1월 24일 연습

아침: 랭작 (...)

2시간 연습을 하려 했으나 늦잠자서 펑크냈다. 뭐라도 돌려야 하니 1시간동안 간단히 할 만한 12문제 랭작셋을 돌렸다.

강의실 배정 문제에 대해서 좀 늦게나마 변을 풀자면, 코이스터디 버전이 $S_i < T_i$ 로 well-formed되어 있는 점을 보았을 때, 코이스터디에서 문제를 옮길 때 실수가 있었던 것 같다. $S_i \le T_i$ 를 인용하는 버전 역시 well-formed되어 있지만 의도된 풀이에서는 특수한 예외 처리가 필요하다. 조만간 추가 데이터를 지우고, 디스크립션을 고칠 것 같다. 나 혹은 백준님이 안 귀찮으면...

오후: SEERC 2017

개인 연습이었다. 이번에도 어제처럼 매우 만족스럽게 했다. 디스크립션 상태가 정말 엉망이었다. 그걸 빼면 문제들은 나쁘지 않았던 것 같다. 특히 쉬운 쪽 문제들이 재밌었다.

• A: simple DP

• B: 재밌는 문제. 어떤 구간을 011111110 으로 만들 수 있는 필요충분이 생각보다 아주 쉽게 결정된다. 이 필요충분을 알면 $n^2$ DP를 설계할 수 있고 보조 배열 하나를 두면 $n+m$ 으로 최적화할 수 있다. 처음 생각했던 풀이의 방향이 저랬는데 필요충분이 어떤지를 생각하는데 오래 걸렸다. 답을 떠올리고 돌아보니 정말 허무했음.

• C: 어렵고 재밌는 문제. 각각의 수에 대해, 그 수들을 span하는 가장 짧은 path에만 칠해주면 된다 (그 Path는 무조건 칠해야 하며 더 칠하는 모험을 할 필요가 전혀 없다.) 그러면 각 수에 대해서 칠하게 될 path가 고정되어 있다. 어떠한 정점에 수가 적혀있다는 것은, 그 정점을 지나는 path들이 그 수보다 먼저 색칠되었다는 것을 의미한다. 여기까지의 관찰을 사용하면 위상정렬로 $O(n^2)$ 에 문제를 해결할 수 있다. 이는 느리니 최적화가 필요하다.

  어떠한 수가 위상 정렬의 큐에서 빠진다는 것은, 해당 숫자들에 대해서, 그 숫자를 지나는 path가 하나 (자기 자신) 밖에 없다는 것이다. 각각의 숫자에 대해서, 해당 숫자를 지나는 Path의 count를 들고 있는다고 생각해 보면, 그 카운트가 1일 때 해당 숫자를 "완성" 되었다고 하고, 모든 숫자가 "완성" 되었을 때 큐에 넣어주면 되겠다.

  하나의 Path를 제거한 후 새롭게 완성된 수들을 빠르게 찾을 수 있다면 저 알고리즘을 완성할 수 있다. 어떠한 숫자를 지나는 path의 count는 1 이상 $\infty$ 이하의 수라고 가정할 수 있으니, 카운트가 1인 것을 찾는 것은 최솟값을 찍는 수를 찾는 것과 같다. Path가 제거되었을 때는, 구간에 있는 숫자들의 카운트가 감소한다. Heavy-Light Decomposition을 구하고 각 노드에 최솟값 + 구간 덧셈 segment tree를 관리하면 전체 문제 해결. 코드가 짧지 않다.

• D: 에휴... $rank(A) = rank(A^T)$

• E: 풀이 자체는 재밌으나 워딩과 제한이 최악이었던 문제. 각각의 수에 대해서 해당 수부터 시작해서 덮을 수 있는 segment의 길이를 구할 수 있다 ($12n$). 이걸 따라 단순히 시뮬레이션하면 $O(n^2)$이다. sparse table로 $O(n\log n)$ 도 가능하다. 하지만 아마 느릴 거 같다. 이를 최적화하는 아이디어는 다음과 같다. 한바퀴 도는 해를 아무거나 잡고, 그 해의 가장 짧은 segment 하나를 고르자. 가장 짧지만 아무튼 maximal하니, 이 segment 사이의 길이 중 하나는 잘려야 할 것이다. 고로 다 잘라본다. 답이 $K$이면, 세그먼트 길이는 $\frac{N}{K}$ 이고, brute force하면 곱해져서 선형.

• F: 쉽고 재밌는 문제. $1 \rightarrow 1$ 인 수는 아예 그대로 냅두거나, 아니면 0으로 한번 바꿔서 코스트를 조금 덜고, 다시 1로 바꿔서 꾸는 식으로 할 수 있다. 저런 식으로 $1 \rightarrow 0 \rightarrow 1$로 바꿔가면서까지 코스트를 지불하기 부담스러운 애들은 비싼 비트들일 것이다. 고로 입력을 정렬한 후 가장 비싼 비트들의 모든 prefix에 대해서 바꿔준다. 이렇게 되면 변환이 필요한 남은 원소들은 $1 \rightarrow 0, 0 \rightarrow 1$ 밖에 없고 그건 simple greedy.

• G: 입력 제한이 안 적혀있음 ㅋㅋ

• H: 관심 없음

• I: 문제도 극혐이지만 디스크립션이 틀렸다. 다 코딩했는데 예제가 14로 나온다면, 맨 위 3*3은 절대 채우면 안된다는 것을 기억하자. 물론 디스크립션에는 써져있지 않다.

• J: 쓰레기 문제. 생각해보면 어떠한 수가 1이냐 아니냐가 꽤 중요하다. 반대로, 수가 충분히 크다면 어떤 수가 클지는 별로 상관이 없어 보인다. 백트래킹 돌리면 3 이상인 수가 2개 이상이거나 2 이상인 수가 4개 이상이면 무조건 진다는 것을 알 수 있다. 이제 1/2/3의 개수 경우의 수가 $n$. DP.

• K: 쉽고 재밌는 문제. LIS가 1인 수부터 순서대로 채워나가준다. 증명은 귀납법.

• L: 쉽고 재밌는 문제. 에지가 $2n-2$개고 1개로 못 끊으니까 글로벌 민컷이 2 아니면 3이다. 그리고 한 쪽 트리에서는 무조건 간선 하나만 끊는다. 고로 LCA+변홧값 배열.

1월 25일 연습

밤: NEERC 2009

나는 결과에 만족했으나 팀원들에게는 그렇게 만족스러운 결과가 안 나왔던 것 같다. 문제 셋 재밌었다. 실력을 막론하고 추천.

• A: 괜찮은 3D 기하 연습 문제. 첫번째로 convex polyhedra의 무게 중심을 구해야 한다. 일반성을 잃지 않고 $x$ 좌표만 구해보자 (나머지는 다 돌리면서 똑같이 하면 됨). 이 때 구해야 하는 건 $\int{\text{($x = T$ 평면으로 잘랐을 때의 넓이)}dx}$, $\int{x \times \text{($x = T$ 평면으로 잘랐을 때의 넓이)}}dx$ 이다.

  꼭짓점의 $x$ 좌표를 기준으로 polyhedra를 $x = X$ 평면으로 잘라보면, 결국에 잘린 각각의 모양은 $x$ 가 증가하는 방향으로 봤을 때 convex polygon이 선형적으로 늘어났다 줄어들었다 하는 모양임을 알 수 있다. 이 convex polygon의 꼭짓점이 무엇인지는 각 잘린 구간에 대해서 바뀌지 않으나, 위치가 선형적으로 변한다. 어떠한 convex polygon의 넓이는 점 위치에 대한 외적으로 구할 수 있다. 각 점 위치를 $x$ 에 대해서 매개화하면, 이 넓이 식은 $x$ 에 대한 이차함수 꼴임을 알 수 있다. 그러면, 우리가 구하는 것은 결국 이차함수 / 삼차함수의 적분 값이다.

  특정한 $T$ 에 대해서, $x = T$ 평면으로 잘랐을 때의 넓이는 $O(n^2 \log n)$ 시간에 단순 convex hull 알고리즘으로 계산할 수 있다 (설명 생략). 그래서 내가 처음에 생각했던 건, $x = p, x = (p+q)/2, x = q$ 에 대해서 넓이를 계산해 놓고, 이차함수가 유일하게 결정될테니 이를 손으로 잘 써서 (...) 푸는 것이 계획이었다. 하지만 이게 나름 빨리 풀린 문제라서 더 좋은 방법이 있을 거라고 생각했다.

  얼핏 생각해 보니 $(q-p)\frac{f(p) + 4f((p+q)/2) + f(q)}{6}$ 로 적분하는 걸 고등학교 시간에 배웠던 것 같았고, 이걸 쓰면 굳이 이차함수를 일일이 계산할 필요가 없었던 것 같았는데, 정확히 무엇인지는 기억이 나지 않아 검색을 해 봤다 (개인 연습은 간단한 구글 검색이 가능하다는 게 그전에 정한 우리 팀 policy였다). 이 방법의 이름은 trapezoidal rule 이었고, 3차함수 이하의 다항함수를 적분할 수 있다는 사실을 배웠다. 그러면 넓이 뿐만 아니라 x * 넓이도 간단하게 해결! 무게 중심을 구할 수 있다.

  이제 무게 중심과 표면의 거리를 계산해야 한다. $n$ 이 작아서 비효율적인 방법도 여럿 시도할 수 있고, 나 역시 간단한 $O(n^4)$ 로 풀었다. 세 점을 잡고, 이 점이 이루는 삼각형이 convex polyhedra의 표면에 있는지를 내적으로 확인한다. 있다면, 삼각형과 점과의 거리를 계산할 수 있다. 이를 모든 쌍에 대해 다 하면 $O(n^4)$ 에 convex polyhedra를 전부 탐색할 수 있다.

  삼각형과 점과의 거리는 옛날에 짜본 적이 분명 있었으나 이 때는 그 방법을 까먹었다 (...) 하지만 사실 이것도 필요없다! 그냥 삼각형이 이루는 평면과 점과의 거리를 계산하면, 더 작은 답이 나올 일이 없다 (convex polyhedra의 접평면이니까). 그래서 이제는 정말 단순 내적. AC.

• B: easy

• C: 재밌는 Interactive. 최솟값과 최댓값을 알면 나머지를 대충 다 찍을 수 있다는 것에서 착안한다. $n = 4$ 일 때 손으로 해 보면, 최솟값 / 두번째 최솟값, 최댓값 / 두번째 최댓값을 구분할 수 없고, 어떤 것이 작은 축에 속하는지 큰 축에 속하는지를 구분할 수 있음을 관찰할 수 있다. 임의의 $n$ 에 대해서도 최솟값 / 두번째 최솟값, 최댓값 / 두번째 최댓값은 서로 구분이 불가능하며, 저 2개 / 2개 원소의 구성을 알고 있으면 전부 답을 찍을 수 있다. 고로, $n = 4$ 일때의 4개 원소의 정보를 손으로 구하고, 하나 하나 추가될 때마다 이 정보를 $O(1)$ 쿼리로 업데이트하면 해결 가능. 쿼리 개수가 널널해서 좋았다 (한편으로 이분 탐색이라고 낚일 뻔하기도 했다. 2000이 적절한 제한이었던 것 같다.)

• D: 파싱 후 정렬.

• E: 아주 재밌는 문제였다. 풀린 것에 비해서 그렇게 어렵지 않고 아이디어도 재밌다. Longest Path가 $T$ 라는 것은, 이 그래프를 $T+1$ 개의 독립집합으로 나눌 수 있다는 것과 동치이다. 증명은 어렵지 않다. 이 직관을 얻기 위해서는, Longest Path를 중심으로 그래프의 정점들을 일종의 "레벨" 혹은 "wave" 로 분리했다고 생각하면 좋을 거 같다. 이제 우리가 구하는 것은 그래프의 최소 채색 수이다. 이는 $O(3^V)$ 시간에 Bit DP를 사용해서 간단하게 구할 수 있다. 이제 구한 각각의 독립 집합을 대충 라벨링한 후, 각 에지에 대해서 consistent한 방향을 주면 (말하자면, 색깔 수가 큰 쪽으로 방향을 주면) 간단하게 해결.

• F: 초반부터 많이 풀린 문제였는데 도저히 풀이를 못 찾겠어서 멘붕이 왔다. 멘탈을 정리하기 위해 풀 다른 문제를 열심히 찾다가 J도 풀고, 3D 기하인 A도 풀었다 (...) 돌아와도 제대로 된 풀이는 안 보였고, 그나마 사풀이 중 될것 같이 생긴 게 떠올라서 그걸 짜서 맞았다. 끝나고 확인해 보니 팀원들의 풀이도 나랑 비슷했고 (다만 나보다 조금 더 될 거 같고), 팀원들 중 제대로 증명한 사람은 아무도 없었다. 뭐 어쨌든 증명이 있을 거 같긴 하지만, 좋은 기억으로 남지는 못한 문제. sensible BFS approach

• G: 흔한 Permutation $N$ 승하는 문제. 그 과정에서 지나온 길에 써져있는 모든 수를 더해야하는 류의 조건이 있지만, 문제는 별로 바뀌지 않는다. 짜증나는 점이 있다면 $N \le 10^{100}$ 이라는 것인데, 일단 큰 수 modulo와 나눗셈을 구현해야 해서 귀찮지만 풀이가 크게 바뀌지는 않는다. 나의 경우에는 사이클을 직접 찾아 지우는 것보다 permutation $N$ 승을 sparse table로 구현하는 걸 선호하는데, 위 경우에는 이진법보다 십진법으로 수를 다루는 게 편하니 sparse table을 $10^k$ 번 거쳐갔을 때의 결과 / 그동안 써진 수의 합 형태로 저장하면 구현이 간단하다.

  .. 그런데 이렇게 하니까 메모리를 100MB 써서 MLE가 났고 (옛날 대회라 ML 64MB ㅠㅠ) 엄청나게 당황했다. 하지만, sparse table도 DP니까, 토글링을 하면 된다. 모든 노드를 한꺼번에 처리해 준다면, 모든 $10^k$ 번째 조상을 그때그때 볼 필요 없이 한번에 한 $k$ 에 대한 결과만 필요하다. $10^k$ 번째 조상을 찾을 때는, $10^{k-1}$ 번 조상만을 참고한다. 고로 토글링이 가능하다. AC.

• H: 조건부 확률 연습.

• I: 이번에도 구사과 블로그에 있는 DAG Path Cover. 이분 매칭을 팀노트에서 직접 타이핑하지 않는게 우리 팀 개인 연습 policy라서, 평소보다 약간 빨리 풀 수 있었다.

• J: 약간의 제약 조건이 걸린 냅색. 일단 제약조건이 없을 때는 $O(m\times n^2 \times maxPercent)$ 시간에 풀린다. 이 때 $maxPercent$ 는 각각의 퍼센트에 대해서 해당 퍼센트가 나오는 정답률 쌍의 개수 최댓값을 뜻하는데, 딱 봐도 작을 거 같다 해서 돌려보면 실제로 작음을 알 수 있다 ($maxPercent = 100$). 난 이렇게 짰고 예제에서 WA를 받았는데 (...), 알고보니 최대 - 최소에 대한 제약 조건이 있었다. 이는 크게 두 가지 방법으로 해결 가능하다.

  • $[L, R]$ 구간에 있는 문제 수만으로 냅색이 가능한가? 쿼리를 대답할 수 있다면, inchworm의 요령으로 100번의 쿼리 만에 문제를 해결할 수 있다. 각 쿼리를 응답하려면 냅색을 빠르게 해야 하는데, 마법의 bitset을 사용하면 냅색은 64배 빨라진다 (...) 역추적은 한번이니 그 때는 비트셋 안 써도 그만. 100배 느려지고 64배 빨라졌으니 시간도 별 차이 안 난다. 난 이렇게 고쳐서 금방 맞았고, 짜증나는 문제라고 생각했다.
  • 팀원들의 풀이는 훨씬 깔끔하고 재미있다. 아마 정해는 이것일 거 같다. $[L, R]$ 구간에서, $L$ 은 항상 $\frac{n}{m}$ 이하임을 알 수 있다. $L$ 이 고정되었을 때 $R$ 을 최소화하는 것은, 냅색의 반환값을 boolean이 아니라 지금까지 나온 $R$ 의 최솟값으로 정의하면 구할 수 있다. 시간 복잡도는 $O(\frac{n}{m} \times m \times n^2 \times maxPercent) = O(n^3 \times maxPercent)$ 로 AC. 알고보니 재밌는 문제였다.

• K: ㅁㄹ