Educational Codeforces Round 103 (Rated for Div. 2)

 

 

 

A K-divisible Sum  [ 4분 ]

 

내가 제일 싫어하는 수학 문제다.

$ N $ 이라는 사원을 $ K $ 부서에 고르게 배치할 때 각 부서에 몇 명이 배치될 지를 생각하면 된다.

$ N  < K $ 일 때 조심!

 

B. Inflation [ 16분 ]

 

이분 탐색을 안쓰는 풀이도 있지만 난 이분 탐색을 썼다.

이분 탐색을 해서 고정된 $ x $ 란 값을 $ a_{1} $ 에다 넣은 뒤 조건을 만족하는 지 판단하면 된다.

 

C. Longest Simple Cycle [ 35분 ]

 

$ a_{i} $ 와 $ b_{i} $ 가 같은 거 일 땐 $ simple \, cycle $ 이 새롭게 만들어져야 한다는 것이 중요한 관찰이다.

$ a_{i} $ 와 $ b_{i} $ 가 다르면 그 전 $ simple \, cycle $ 에서 이어질 수 있으나 새롭게 $ simple \, cycle $ 이 만들어지는게 이득일 수도 있다는 것을 주의하자.

 

D. Journey [ 42분 ]

 

어떤 $ i $ 지점에서 출발해서 다시 그 지점으로 돌아오는 길이는 짝수이므로 각 $ i  $ 지점에서 왼쪽으로 갈 수 있는 최대값 오른쪽으로 갈 수 있는 최대값을 구한 뒤 더해주면 된다.

$ dp $ 를 사용하면 간단하게 구할 수 있다.

 

E. Pattern Matching [ 106 분 ]

 

모든 패턴이 $ distinct $ 하다는 것을 너무 늦게 알아서 아예 못 풀 뻔 했다...

각 쿼리에 나오는 $ string $ 이 배정될 수 있는 패턴은 최대 $ 2^{4} $ 이므로 각 쿼리에서 주어진 $ pos $  값에서 배정 될 수 있는 패턴 $ index $  로 간선을 연결해준다.

그렇게 만들어준 그래프에 $ cycle $ 이 있으면 답을 구할 수 없는 경우이다.

왜냐하면 어느 것이라도 제일 상위 층에 놓을 수가 없기 때문이다.

즉 사이클이 없어야 하고 사이클이 없으면 위상 정렬을 할 수 있다.

위상 정렬하면서 만나는 정점 순서대로 답을 구해주면 된다.

 

 

 

 

### 후기

 

F 는 아예 풀리지도 않았고 G번도 매우 적은 사람밖에 못풀었다.

그러다 푼 사람의 G번 코드를 봤는데 $ query\,mo's\,alogrithm $ 에서 업데이트 연산을 하고 있었다.

그게 가능한가...? 오늘이나 내일 날 잡고 한번 풀어봐야겠다.

만약 이 문제 뿐만 아니라 범용적으로 사용할 수 있는 아이디어라면 매우매우매우 유용할 듯.. ( 그럴 일 없겠지만.. )