AtCoder Beginner Contest 286

https://atcoder.jp/contests/abc286/tasks

간만에 풀었는데 조금 쉬운 셋 같다.

EX의 난이도는 2500으로 실제로 좀 쉬웠다

 

A. Range Swap

 

문제에서 하라는 대로 그대로 구현한다.

 

B. Cat

 

마찬가지로 문제에서 하라는 그대로 구현한다.

물론 방식은 다양할 수 있다. 

S 자체를 수정한다거나, 글자 하나씩 보면서 출력한다거나... 등등

 

C. Rotate and Palindrome

 

A엔을 사용하는 방식이 0번부터 n - 1번일 때까지 모두 그냥 해보면 된다.

 

D. Money in Hand

 

냅색 비스무레 한 것이다.

사실 제한이 만만해서 O(NXB)로 그냥 단순히 (A, A*2, A*3, ... A*B)로 냅색을 굴려도 된다.

하지만 '잘' 하면 O(NX)로도 가능하다.

dp : dp[i] = i엔을 만들 수 있다. 

nxt : A를 최대 B번까지 사용하였을 때 새로운 dp

tmp : tmp[i] = (dp[j] = 1이며, A로 나눈 나머지가 i인 숫자 j 중 최댓값)

그러면 nxt[j] = (tmp[j % A] >= j - A*B)를 주면 된다.

 

E. Souvenir

 

단순하게 {방문한 도시 수, 기념품의 가치}로 플로이드 와샬을 굴려주면 된다.

 

F. Guess The Number 2

 

f(i) = i + 1인 함수 f를 생각해보자. 

그렇다면 f^2(i) = i + 2가 될 것이고 f^n(i) = i + n이 될 것이다.

하지만 n <= 1e9으로 상당히 커질 수 있기에 f의 크기가 110으로 한정된 지금은 사용할 수 없다.

 

편의를 위해서 0-based index를 쓰자

f(i) = i + 1인 함수에서 f(m) = 0이라고 생각해보자.

그러면 f^n(i) = (i + n) % m이 된다.

즉 n을 m으로 나눈 나머지를 구할 수 있다.

 

따라서 함수를 여러 구역으로 나누고, 여러 숫자에 대한 나머지를 구하면 적당히 큰 n을 구할 수 있다.

예를 들어 {2, 1, 4, 5, 3}는 {2, 1}과 {4, 5, 3}으로 나뉘어 있다.

첫 번째 구역에서는 n을 2로 나눈 나머지를, 두 번째 구역에서는 3으로 나눈 나머지를 구할 수 있다.

 

G. Unique Walk

 

우선 S에 포함되지 않은 애들은 자유롭게 이동 가능하니 (u, v)가 있으면 union-find로 u와 v를 merge 시킨다.

그렇다면 S에 포함된 edge들과 merge된 vertex들로 이루어진 그래프가 생겨난다.

이 그래프가 오일러 경로를 가지면 된다.

-> 홀수 차수인 vertex가 0개거나 2개인 그래프이면 된다.

 

Ex. Don't Swim

 

S와 T를 포함시켜서 새로운 convex hull을 만들자.

그 convex hull에 S와 T가 포함되어 있다면 S -> T로의 두 경로(시계/반시계) 중 짧은 것을 선택하면 된다.

만일 포함되어 있지 않다면 S에서 T로 그냥 가도 기존의 Edge와 만나지 않음을 의미하니 선분 ST가 답.