AtCoder Beginner Contest 257

A. A to Z String 2

code

1. 문제 설명

a부터 z까지의 글자가 \( N \) 개씩 있는 문자열이 있다. 이 문자열의 \(K\)번째 글자를 구해야 한다.

2. 알고리즘

\( K\)에서 \(N\)씩 빼나가면서 몇 번째 글자인지 확인하면 된다.

B. 1D Pawn

code

1. 문제 설명

1차원 배열에 폰이 몇 개 있다. 여기에 총 \(Q\) 개의 명령을 내린다.

각 명령은 특정 폰을 오른쪽으로 한 칸 옮긴다. 이때 폰이 맨 오른쪽에 있거나 옆에 다른 폰이 있으면 움직일 수 없다.

\(Q\) 개의 명령을 내린 후 각 폰의 위치를 출력해야 한다.

2. 알고리즘

문제에 주어진대로 시뮬레이션을 진행한 후, 시뮬레이션 결과를 출력하면 된다.

C. Robot Takahashi

code

1. 문제 설명

총 \(N\) 명의 사람이 주어진다. \(N\) 명의 사람은 어른이거나 아이이며 각 사람의 몸무게가 주어진다.

로봇은 몸무게를 바탕으로 주어진 사람이 아이인지 어른인지 예측하려고 한다.

특정 숫자 \(X\)를 정해 \(X\)보다 가벼우면 아이, 그렇지 않으면 어른으로 예측한다.

\(X\)를 정한 후, 바르게 예측한 사람의 수를 \(f(X)\)라 하자.

\(f(X)\)의 최댓값을 구해야 한다.

2. 알고리즘

먼저 편의상 사람들을 몸무게로 정렬을 하고, \(i\) 번째 사람의 몸무게를 \(W_i\)라 하자.

그렇다면 \(X=W_i\)인 경우들과 \(X = 0\)인 경우에 대해서만 고려를 해도 모든 경우를 고려하는 것과 동일하다.

먼저 \(X=0\)인 경우는 모든 사람을 어른으로 예측하는 것이므로 \(f(X)\)는 어른의 수가 된다.

그 후, \(X\)값을 \(W_1\)부터 \(W_N\)까지 바꿔나가면서 \(f(X)\)를 계산해나간다.

\(X\)를\(W_i\)로 바꿨을 때, \(i\) 번째 사람이 아이이면 \(f(X)\)가 1 증가하고,

\(i\) 번째 사람이 어른이면 \(f(X)\)가 1 감소한다.

따라서 \(O(N)\)안에 \(f(X)\)의 최댓값을 구할 수 있다.

원래는 \(W_i\)가 같은 사람들을 \(f(X)\)를 계산할 때 한 번에 계산해줘야 하지만, 사람을 정렬할 때 같은 몸무게일 경우 어른이 앞으로 아이가 뒤로 가도록 정렬하면 그렇게 하지 않아도 된다.

D. Jumping Takahashi 2

code

1. 문제 설명

총 \(N \le 200 \)개의 트램펄린이 주어진다. \(i\) 번째 트램펄린의 위치는 \((x_i, y_i)\)이고, 파워는 \(P_i\)이다.

타카하시의 처음 점프능력은 \(S=0\) 이고, 한 번 훈련을 할 때마다 점프 능력 \(S\)는 1 증가한다.

타카하시는 \(i\)번째 트램펄린에서 \(j\) 번째  트램펄린으로 점프하기 위해서는 아래 조건을 만족해야 한다.

\(P_i S \ge |x_i - x_j| + |y_i - y_j|\)

타카하시는 아무 시작 트램펄린을 하나 정하고 모든 트램펄린을 여러 번의 점프를 거쳐 갈 수 있는지 확인하고 싶다.

모든 트램펄린을 거칠 수 있는 시작점이 존재하기 위해 훈련해야 하는 최소 횟수를 구해야 한다.

2. 알고리즘

먼저 \(S\)가 고정되어 있다고 가정하자. 그렇다면 시작점을 정하고 BFS를 돌려 모든 트램펄린을 거쳐갈 수 있는지 \(O(N)\)으로 확인할 수 있다.

따라서 총 \(N\)개의 시작점에 대해서 BFS를 돌려 \(S\)로 모든 트램펄린을 거칠 수 있는 점이 있는지 확인할 수 있다.

\(S\)로 모든 트램펄린을 거칠 수 있다면, \(S\)가 커지도 모든 트램펄린을 거칠 수 있고,

\(S\)로 모든 트램펄린을 거칠 수 없다면, \(S\)가 작아져도 모든 트램펄린을 거칠 수 없다.

따라서 이분 탐색을 이용하여 모든 트램펄린을 거칠 수 있는 최소한의 \(S\)를 구할 수 있다.

\(S\)의 가능한 최솟값은 1이고, 가능한 최댓값은 트램펄린 긴 길이의 최댓값인 \(Gap_{max}\)이다.

따라서 \(O(N^2 \log Gap_{max})\) 안에 해결할 수 있다.

E. Addition and Multiplication 2

code

1. 문제 설명

총 \(N\)원이 있고, 숫자 \(i\)를 \(C_i)\) 원에 구매할 수 있다.

이 구매한 숫자들을 나열하여 수를 만들 때, 최대로 만들 수 있는 수를 구해야 한다.

2. 알고리즘

먼저 최대로 만들 수 있는 수의 길이를 쉽게 구할 수 있다.

\(N\)을 \(C_i\)의 최솟값으로 나눈 값이다. 가장 싼 것을 선택했으므로 이것보다 긴 수를 만들 수 없고, 이것보다 짧은 길이의 수는 무조건 이 수보다 작기 때문이다.

이제 가장 싼 가격을 가진 숫자만 구매해서 수를 만든다.

이제 남은 돈을 사용하여 더 큰 수로 만들어가면 된다.

가장 앞자리를 크게 만드는 것이 최고이므로, 첫 번째 자리부터 마지막 자리 순서로

남은 돈을 사용하여 가장 큰 수로 바꿔주면 된다.

F. Teleporter Setting

code

1. 문제 설명

\(N\)개의 도시와 \(M\) 개의 방향이 없는 텔레포터가 존재한다.

\(i\) 번째 텔레포터는 도시 \(u_i\)와 도시 \(v_i\)를 연결하며 방향은 존재하지 않는다.

텔레포트를 사용하여 1분 만에 연결된 도시로 이동할 수 있다.

\(M\) 개의 텔레포터 중 일부 텔레포터는 한 도착지가 연결되어 있지 않다. \(u_i = 0\)

이 텔레포터의 한 끝점을 \(A\)로 정했을 때, 1번 도시에서 \(N\) 번 도시까지 가는데 걸리는 최소 시간을 알고 싶다.

모든 \(1 \le A \le N\)에 대해서 최소 시간을 구해야 한다.

2. 알고리즘

먼저 모든 텔레포터의 이용시간이 1로 같으므로 단순 BFS로 1번 도시에서 N번 도시까지의 최소 시간을 알 수 있다.

일단 한 도시만 연결된 텔레포터를 가진 도시들을 black이라 칭하자.

그렇다면 \(A\)번\(A\) 번 도시를 텔레포터의 한 끝점으로 정한다는 것은 black 도시를 \(A\) 번 점과 연결한다는 것과 같다.

1번에서 \(N\)번 도시까지 가는 방법은 아래의 네 가지만 존재한다.

1. 1 \(\rightarrow N\)

2. 1 \(\rightarrow\) black \(\rightarrow A\) \(\rightarrow N\)

3. 1 \(\rightarrow\) \(A\) \(\rightarrow\) black \(\rightarrow\) \(N\)

4. 1 \(\rightarrow\) black \(\rightarrow\) \(A\) \(\rightarrow\) black \(N\)

 

1., 4. 방법으로 가는 경우는 \(A\) 값에 관계없이 항상 동일하고,

2., 3. 방법으로 가는 경우는 1번 도시에서 다른 각 도시까지 가는 데 걸리는 시간과, \(N\) 번 도시에서 다른 각 도시까지 가는 데 걸리는 시간을 구해두면 \(O(1)\)로 구할 수 있다.

 

이때 한 방향이 지정되지 않은 텔레포터는 \(N+1\)번째 도시를 임의로 만들어 연결한 뒤 BFS를 이용해 4. 방법으로 가는 경우를 구할 수 있다.

 

모든 \(A\)에 대해 네 경우중 최단 거리를 구해주면 된다.

G. Prefix Concatenation

code

1. 문제 설명

두 문자열 \(S, T\)가 주어진다.

문자열 \(T\)를 \(S\)의 prefix로 분해하려고 한다.

이때, 최소한의 prefix만 이용해서 \(T\)를 분해할 때 prefix의 개수를 구해야 한다.

2. 알고리즘

먼저 \(cnt[i]\)를 \(T [1:i]\)의 suffix와 \(S\)의 prefix가 최대로 일치하는 개수로 정의하자.

일치하는 경우가 없으면 \(cnt[i]=0\)이다.

예를 들어, \(T=ababaab\), \(S=aba\)인 경우, \(cnt=[1,2,3,2,3,1,2]\)이다.

이제 \(dp [i]\)는 \(T [1:i]\)를 쪼개기 위해 사용하는 \(S\) prefix의 최소 개수라 정의하자.

먼저 \(dp [0]=0\) 라고 초기화를 하면 아래의 식이 성립한다.

\(dp [i]=\begin {cases} dp [i] = dp[i-cnt [i]] + 1,\space if \space cnt[i] \ne 0 \\dp [i] = 0,\space if \space cnt = 0\end {cases}\)

 

\(i\)가 증가하면 \(dp [i]\)도 증가해야 한다는 것은 자명하다.

만약 \(T [1:i]\)를 \(dp [i]\) 개로 분해할 수 있다면, \(T[1:i-1]\)은 이 분해의 마지막 prefix를 한 글자만 지우면 똑같이 \(dp[i]\)개 이하로 분해할 수 있기 때문이다. 즉 \(dp [i]\)는 오름차순이다.

따라서 만약 \(T [1:i]\)의 마지막을 \(cnt [i]\) 개보다 작은 길이\(K\)로 분해하면 분해하는 prefix의 개수가 \(dp [i-K]+1\) 로 \(dp [i]\)는 오름차순이라는 성질에 의해 \(dp [i-cnt [i]]+1\) 보다 같거나 크다.

따라서 단순히 최대한 긴 조각으로 분해하는 것이 이득이므로, 위의 식이 성립한다.