COI 2017 리뷰

 아주 오랫만에 블로그를 쓰는데 음...이유는 생략한다. 방학이 시작했고, 고1 여름방학 이래로 최초로 수올준비를 하지 않는 방학이 와서 ps와 수학공부에 온 초점을 맞출 생각이기 때문에, 이틀에 한번씩 셋을 돌고 업솔빙까지 완료하는 계획을 세웠다.(물론 이번 셋은 업솔빙을 전부 하진 못했다.) 아무튼, 이번에 돈 셋은 COI 2017(크로아티아 정올)이다. 생각보다 문제가 많이 매웠다. 또한 5시간짜리 셋이긴 하나, 깨어나자마자 비몽사몽한 상태에서 셋을 돌고 중간에 학원에 가야 했던 일, 생각보다 의지박약때문에 설렁설렁 친 것 때문에 그다지 부분점수도 안 긁고 성적이 딱히 좋지는 않다. 잡담은 이쯤까지 하고, 각 문제들에 대한 솔루션과 나의 접근에 대해 서술하겠다.

 

1. ili

 일단 n,m 제한이 살벌해서 언뜻 보기엔 제곱이 돌지 않을 것이라 착각할 수 있지만, 놀랍게도 정해는 제곱이다. 내가 떠올린 풀이도 제곱풀이인데, 상수가 커서 49점밖에 못 받고, 심지어는 에디토리얼을 보고 구현한 코드조차 시간초과때문에 49점밖에 못 받았다. 깔끔하고 쉬운 구현법을 찾아봐야 할 듯...

 

1-1. 오피셜 솔루션

 우선, 일반적으로 존재하는 모든 회로의 구성요소들을 노드로 간주하겠다. 어떤 값이 0으로 정해진 노드에 대해서, 해당 노드의 하위 노드들은 반드시 값이 0이어야 한다. 이런 조건을 만족하는 노드들을 찾는 것은 단순히 queue를 통한 bfs를 돌림으로써 알아낼 수 있다. 이제, 해당 노드들은 전부 제거한다. 왜냐하면, 해당 노드들이 다른 노드들에 직접적으로 영향을 줄 수 있는 방법이 존재하지 않기 때문이다.

 이제 1로 값이 결정된 노드들이 주는 영향에 대해 분석해야 하는데, 이때 알아야 하는 사실은, 아주 자명하지만, 모든 노드들의 답이 특정한 리프노드의 값들의 or값으로 결정된다는 점이다. 이 배열을 전부 구하는 것은 O(nm)정도에 해결할 수 있을 것이다. 그 다음에, 해당 표현들에 따라 어떤 노드가 다른 노드의 모든 표현을 전부 "포함"하는지를 계산할 수 있을 것이다. 노드 i가 노드 j를 포함하는지 확인하기 위한 방법은, j의 자식들을 노드 i가 전부 포함하면 된다. 따라서 이 또한 O(nm) 안에 구할 수 있다. 이제 핵심적인 내용인데, 일단 이미 반드시 0이 되어야 하는 노드들을 제거했기 때문에, 이들을 제외한 모든 리프를 1로 켜면 모든 노드가 1일 수 있다는 사실이다. 즉, 어떤 노드가 1이 아닐 수 있는지만 따지면 충분하다. 이를 확인하는 방법은, i가 포함하는 모든 j에 대해서, j의 값이 1인 것이 존재하는지를 확인하는 것이다. 오피셜 솔루션에선 이에 대한 증명을 생략하였지만, 나는 간략히 해당 내용에 대한 증명을 기술해보겠다.

 

 Claim) 어떤 노드 X의 출력값이 1이라는 것은, 어떤 노드 Y가 존재해서 Y의 표현이 X의 표현에 포함되고, Y의 출력값이 1임과 동치이다.

 

pf) 우선 오른쪽에서 왼쪽은 자명하다. 이제 대우명제를 증명할 것인데, 모든 출력값이 1인 Y에 대해서, X의 표현에 속하지 않는 리프노드가 적어도 한 개 존재한다는 조건이 주어지게 된다. 그러면 우리는 단순히 해당 리프노드를 1로 켜서 X를 켜지 않고, Y를 켤 수 있다. 따라서 명제가 증명된다 . Q.E.D.

 

따라서 O(nm)에 이를 계산할 수 있지만...짜봤는데 시간초과가 났다. 어케해야 효율적으로 짜지

 

1-2. 내 솔루션

 나는 조금 다르게 해결했는데, 아직 결정되지 않은 모든 노드들에 대해서, 해당 노드에 1 혹은 0을 박았을 때 전체 상태가 모순이 되는지, 혹은 그렇지 않은지 확인하는 것이다. 즉, 우리는 다음과 같은 결정문제를 적당히 빠르게(나의 경우에는  O(n+m)) 해결하면 된다:

 

 어떤 상태가 주어졌을 때, 해당 상태를 만족하는 리프노드의 세팅이 적어도 하나 존재하는가?

 

 이를 확인하는 것은 어렵지 않다: 우선 0들에 대해서는 전부 하위노드들을 보면서, 만약 1이 있다면 모순이고 아니면 0으로 바꾼다. 남아있는 모든 노드들은 ?이거나 1이기 때문에, 선택할 수 있는 다른 모든 리프 노드들을 1로 바꾸는 것이 이득이다. 이렇게 바꿔준 뒤, 모든 노드들에 대해 출력값을 계산하는데, 모순이 발생하는 경우는 1이어야 하는데 하위노드들이 전부 0인 경우이다. 지금 이렇게 풀이를 쓰고 있는데 생각해보니 그냥 0으로 설정한 노드에 대해서 그냥 0으로 확정지을 수 있는 모든 노드들을 따기만 해도 모순을 전부 걸러낼 수 있지 않을까...? 쓸데없이 귀찮게 구현했네

 아무튼 이것도 시간초과가 났다.

 

2. Raspad

문제 제목들을 볼때마다 생각하는 거지만 이게 크로아티아어로 무슨 의미인지 이따금 궁금해진다. 이 문제는 대충 읽고 정해에 거의 다 근접했지만, 세 가지 정도의 이유로 구현을 하지 않고 0점을 받았다.

 1. 한번도 커넥션 프로파일 dp를 짜본적이 없음

 2. 더 쉽고 간결한 풀이가 있을 것이라 확신함.

 3. 귀찮음(이건 반성할 점이 맞는 것 같다. 항상 최선을 다해 셋을 쳐야 할 것 같은데...다음부터는 학원시간도 안 겹치는 때에 체계적으로, 진심으로 쳐야겠다.)

아무튼, 오피셜 솔루션을 보니까 그냥 내가 생각한 풀이랑 똑같았다. 이건 그나마 업솔빙을 하는데에 성공해서, 최초의 내가 푼 커넥션 프로파일 dp 문제가 되었다.

 

 오피셜 솔루션.

 일단 기본적인 문제풀이의 아이디어는 스위핑을 하며 답을 계산하는 것이다. 끝부분을 나타내는 선을 차례로 아래로 내려가는 것인데, 여기에서 중요한 관찰 하나를 해야 한다.

 우선, 시작선이 끝선이랑 동일한 경우를 생각해보자. 이 경우에는 컴포넌트가 단순히 하나의 행에 대한 것만을 고려해도 충분할 것이다.

 이제 시작선을 조금씩 위로 올려보자. 어떨 때에는, 끝선에 나타나있는 서로 다른 두 컴포넌트가 병합될 수 있을 것이다. 그런데 여기에서 중요한 것은, 끝선의 컴포넌트들은 단조적으로 병합만 한다는 점이다. 즉, 끝선의 컴포넌트 상태로 가능한 것은 많아봐야 m개이다.

 

 이런 관찰을 통해 커넥션 프로파일을 적용할 수 있는데, 굳이 어려운 용어를 쓰지 않고 쉽게 설명해보겠다.

 본 풀이에서 관리하고자 하는 것은 몇 개의 튜플들의 집합인데, 하나의 튜플은 (끝선의 연결상태,해당 연결상태를 가지는 시작선의 개수, 모든 시작선들에 대해 해당 상태에서 끝선에 있는 컴포넌트들과 연결되어있지 않은 컴포넌트들의 개수의 총합)로 구성되어있다. 이제 끝선을 한 번 아래로 내려보겠다. 이 경우, 어떤 튜플을 (P,x,y)로 표기하고, 이번 끝선에 해당되는 열을 r이라 표기할 때, 해당 튜플은 다음과 같이 갱신된다.

 (P,x,y)->((P 다음에 r이 올 때 r의 컴포넌트 연결에 따른 연결상태),x,y+x*(P,r을 병합했을 때 P에서 새롭게 나타나는 단절 컴포넌트의 개수))

 물론, r이 단일로 있을 때의 튜플도 추가할 것이다. 이렇게 모든 튜플을 추가한 다음에는, P가 같은 것들끼리 병합한다. 만약 r이 단일로 있는 경우의 튜플을 맨 처음에 더한다면, P들에 대해 단조성이 성립하기 때문에 굳이 모든 튜플의 쌍에 대해 시도할 필요 없이, 두 튜플의 P가 같다면 튜플들끼리 인접할수밖에 없어서 편리하다.

 

음 사실 이렇게 설명하면 혹자는 무슨 소리인지 못 알아먹을수도 있을 것이다. 그래서 주어진 예제를 통해 설명을 보강해보겠다.

1101
1111
1010
1011

 예제 1이다. 여기에서 답을 구하는 과정을 전부 서술해보겠다.

1. 첫 번째 행을 탐색한다. 이 경우 튜플은 다음과 같이 나타난다: ({1,1,0,2},1,0) 전체 답에는 해당 연결상태의 컴포넌트의 수인 2와, 개수인 1을 곱해서 더한다. ans+=2;

2. 두 번째 행을 탐색한다. 이 경우 튜플은 다음과 같이 나타난다: ({1,1,1,1},2,0)  ans+=2;

3. 세 번째 행을 탐색한다. 이 경우 튜플은 다음과 같이 나타난다: ({1,0,2,0},1,0), ({1,0,1,0},2,0) ans+=4;

4. 네 번째 행을 탐색한다. ({1,0,2,2},2,0),({1,0,1,1},2,0) ans+=6;

 

따라서 답이 14가 된다. 이 예제는 안타깝게도 y에 대한 좋은 예시가 되진 못하지만, 아마 위의 설명을 읽고 간단히, 혹은 곰곰히 생각해보면 이해할 수 있을 것이다.

 

짜는데에는 조금 걸렸지만, 그래도 1번처럼 빡빡한 상수 커팅을 요구하지는 않는다. 다만, 메모리 초과가 날 가능성이 없지 않으므로 토글링을 추천한다.

 

 또한, 이것은 내가 짠 함수 목록인데 있으면 편할 것 같아서 써본다.

 newprofile(vector<ll> v): v행만 있을때의 연결상태를 계산한다.

 sumprofile(profil a,profil b): a,b를 이었을 때 b의 연결상태를 계산한다.

 음 또 뭐 짰더라 대충 프로필 두개 주어지면 새로 단절되는 컴포넌트 수 세는 함수도 짰던 것 같고 아무튼 다양하게 짰는데 그냥 취향껏 짜면 될 것 같다.

 

3. 던짐

4. Zagrade

이 문제는 보자마자 풀이가 대략적으로 구상되어서 그냥 짜고 100점 받았다. 아무래도 트리 위에서 할 수 있는 연산들이 그렇게 다양하진 않아서 몇가지 시도해보면 된다. 내가 듣기론 작큰으로도 풀리고, 센트로이드로도 풀리는데, 나는 센트로이드를 짰다. 귀찮아서 오피셜은 안읽어봤다.

 

 내 솔루션.

 핵심은 센트로이드이다. 이건 조금 웰노운 아이디어인데, 어떤 괄호문자열이 올바르다는 것은 (를 1로, )를 -1로 치환한 상태에서 모든 누적합이 0 이상이며, 전체합이 0임과 동치라는 것이다. 따라서 내가 구상한 풀이는 센트로이드에서 시작해서 뻗어나가거나, 혹은 센트로이드에 도달하기 직전까지 뻗어오는 모든 경로들을 전부 구한 다음에, 만약 그것이 올바를 수 있는 경로의 조각이라면 맵의 역할을 수행할 수 있는 배열에 해당 누적합?의 값을 표기해준 다음, 각각의 합들에 대해 매칭을 진행하는 것이다. 뭐 작큰이어도 어차피 비슷하게 할 순 있겠지

 

리뷰: 음...구현이 대체로 무진장 빡센 셋이었다. 1번은 아무리 짜도 tle 뜨고 2번은 커넥션 프로파일, 3번은 잘 모르겠는데 일단 미친 비트마스킹 dp라는건 대략 알고 있다. 4번이 그나마 교육적인 문제라고 생각된다. 물론, 그걸 제외하면 문제들의 퀄 자체는 굉장히 좋은 것 같다. coi 많이 애용해야겠네

 근데 흠...그냥 joi나 joisc도 아직 다 안 돌아서 이쪽을 도는게 나을 것 같다.

  음 그리고 내 태도에 대한 반성도 해야 할 것 같은데, 너무 의지없이 셋을 돈 것 같고, 진심을 발휘하지 않았던 점이 문제인 것 같다. 내일?오늘? 부턴 빡세게 돌아야지