AtCoder Beginner Contest #241

 

AtCoder Beginner Contest 241（Sponsored by Panasonic） - AtCoder

 

 

A. Digit Machine

 

A - Digit Machine

 

 

한 자리 수를 보여주는 스크린과 버튼이 있다.

 

스크린에 보이는 수가 \(k\)라고 할 때, 버튼을 누르면 \(a_k\)로 바뀐다.

 

처음 보여지는 수는 0이다.

 

버튼을 누르면 바뀌는 수가 제시될 때 (0부터 9까지), 버튼을 3번 눌렀을 때 보이는 수를 구하라.

 

 

\( 0 \) -> \( a_0 \) -> \( a_{a_0} \) -> \( a_{a_{a_0}} \) 를 구현하면 된다.

 

 

 

B. Pasta

 

B - Pasta

 

 

\( N \) 종류의 면이 있고 각각 면의 길이는 \( A_i \)이다.

 

\( M \)일동안 정확히 \( B_i \) 길이를 가진 면을 사용하여 파스타를 만드려고 한다.

 

같은 면을 2일 이상 사용할 수 없다.

 

가능한지를 구하여라.

 

 

\( N \)과 \( M \)이 최대 1000이기 때문에 단순히 완전 탐색을 해도 된다.

 

\( B_i \)와 같은 값을 가진 \( A_j \)를 찾아 boolean 배열로 면을 사용했는지를 확인한다.

 

아니면 map을 이용하여 카운팅을 해도 되고, 배열 \( A \)를 오름차순으로 정렬한 뒤 뒤에서부터 같은 길이의 면을 카운팅하고 \( b_i \)에 대하여 같은 길이를 가진 \( a_j \)를 이분탐색하여 카운트한 수를 줄인다.

 

그러한 \( a_j \)가 없거나 카운트 수가 0이라면 불가능하다.

 

 

 

C. Connect 6

 

C - Connect 6

 

 

\( N \) x \( N \) grid가 있다.

 

각각의 칸은 흰색이거나 검은색이다.

 

최대 2번 흰색 칸을 검은색 칸으로 칠하여 연속적으로 6칸 이상을 검은색 칸으로 만드려고 한다.

 

여기서 연속적이란 가로, 세로, 대각선으로 연속된 칸을 의미한다.

 

가능한지 구하시오.

 

 

결국 6칸 중 4칸 이상이 검은색 칸이라면 가능하다.

 

\( N \)이 최대 1000이기 때문에 완전 탐색을 해도 상관없다.

 

여기서 주의할 점은 '6칸' 중에서 검은색 4칸 이상을 찾는 것이기 때문에 6칸이 연속적으로 있는지를 확인해야한다는 점이다.

 

연속적인 검은색 4칸이 대각선으로 모서리에 딱 붙어있다면 6칸을 만드는 것은 불가능하다.

 

 

 

D. Sequence Query

 

D - Sequence Query

 

 

빈 sequence \( A \)가 있다.

 

주어진 쿼리 \( Q \)개를 순서대로 처리하여라.

 

쿼리의 타입은 다음과 같이 3종류가 있다.

 

• 1 x : \( x \)를 \( A \)에 넣어라 
• 2 x k : \( x \)보다 작거나 같은 \( A \)의 원소들 중 \( k \)번째 큰 수를 구하여라. 
  그런 수가 없다면 -1을 출력하여라.
• 3 x k : \( x \)보다 크거나 같은 \( A \)의 원소들 중 \( k \)번째 작은 수를 구하여라.  
  그런 수가 없다면 -1을 출력하여라.

 

 

map을 이용하였다.

 

key로 \( x \)를, value로 \( A \) 안에 있는 \( x \)의 개수를 카운트해주었다.

 

type 1은 그냥 map에 수를 추가시켜준다.

 

type 2와 3은 lower_bound, begin, end를 적절히 이용하여 코드를 짰다.

 

답지에는 multiset을 쓰는 방법과 segment tree, Fenwick tree를 사용하는 방법이 제시되어 있다.

 

 

 

E. Putting Candies

 

E - Putting Candies

 

 

\( N \)길이의 배열 \( A \)가 있다.

 

빈 접시가 있다.

 

다음과 같은 operation을 \( K \)번 반복하였을 때 몇 개의 사탕이 있는지 구하여라.

 

• 접시에 \( X \)개의 사탕이 있다고 할 때, \( A_{ X mod N } \) 사탕을 접시에 더 둔다.

 

 

추상 대수학, 정수론에서 얼핏 배운 기억으로 periocity가 있을것이라는 추측을 했다.

 

근데 거기서 더 나아가지는 못했다.

 

 

\(f^0(0) = 0 \) 이라고 했을 때, \( f^k(0) = ( A_{f^0(0)} + A_{f^1(0)} + ... + A_{f^{k - 1} (0)} ) % N \) 으로 정의하자.

 

\( f^0(0), f^1(0), ..., f^N(0) \) 는 모두 \( 0 \)에서 \( N - 1 \) 사이의 정수이다.

 

비둘기집의 원리에 의해 \( f^k(0) = f^{k'}(0) \) 을 만족하는 \( 0 \leq k < k' \leq N \) 이 있음이 분명하다.

 

따라서 \( f^s(0) = f^t(0) \)와 \( 0 \leq s < t \)를 만족하는 가장 작은 수 \( t \)를 생각해보자.

 

\( p = t - s \) 라 정의한다면, \( s \leq k \) 에 대하여 \( f^{k + p}(0) = f^k(0) \) 은 자명하다.

 

\( k < s \) 라면 naive하게 그냥 구하면 된다. ( \( k < N \) 이기 때문 )

 

\( k \geq s \) 라면 \( k - x(t - s) < s \) 를 만족하는 가장 큰 \( x \)를 찾아서 \( (f^{k - x(t - s)}(0) - f^{k - (x + 1)(t - s)} (0)) * x + f^{k - (x + 1)(t - s)} (0) \)을 구해준다.

 

(이걸 contest에서 어떻게 생각해서 푸는건지... 대단하다)

 

 

sparse table을 사용하는 방법도 있다.

 

\( dp[i][j] = f^0(j) + f^1(j) + ... + f^{2^i - 1}(j) \) 로 정의하자.

 

\( K = 2^{c_1} + 2^{c_2} + ... + 2^{c_k} \) ( \ 0 \leq c_1 < c_2 < ... < c_k \) ) 라고 표현한다면,

\( f^K(0) = dp[c_1][0] + dp[c_2][dp[c_1][0]] + ... \) 으로 표현할 수 있다.

 

따라서 dp로 풀수 있음.

 

\( N \)의 최댓값이 \( 2 x 10^5 \) 이라 가능한 방법인데, sparse table을 이런식으로 활용할 수 있는지 알게되었다.

 

 

 

F. Skate

 

F - Skate

 

 

\( H x W \) 크기의 스케이트장이 있다.

 

스케이트장에는 \( N \)개의 장애물이 있고 Takahashi는 한 방향으로 직진을 하다 장애물을 만났을 때에만 멈추고 방향 전환을 할 수 있다.

 

시작 지점과 목표 지점이 있고 목표 지점에 도달하기 위해 직진하는 최소 횟수를 구하라.

 

만약 목표 지점에 도달할 수 없다면 -1을 출력해라.

 

 

bfs로 풀수 있는 문제가 아니냐고 생각할 수 있지만 naive하게 짠다면 \( H \)와 \( N \)의 최댓값이 \( 10^9 \)이기에 불가능하다.

 

결국 Takahashi가 멈출 수 있는 지점은 시작 지점과 장애물의 사방이다.

 

따라서 이 지점들을 vertex로 하는 새로운 graph를 만들어서 bfs를 해준다.

 

이를 어떻게 구현하는가가 핵심인 듯 한데, vertex의 number, x, y 좌표를 저장하는 자료구조를 만들어서 y축과 x축으로 각각 sorting을 하여 순회하며 edge를 이어주면 되지 않을까 싶다.

 

 

 

G. Round Robin

 

G - Round Robin

 

 

\( 1 \)부터 \( N \)까지 넘버링 된 \( N \)명의 선수가 있다.

 

각각의 선수는 자신을 제외한 모든 선수들과 한 번씩 대결을 한다.

 

따라서 대결은 총 \( frac{N(N - 1)}{2} \)회 이루어지며, 각 대결은 승자와 패자가 갈린다.

 

이미 \( M \)회 대결을 한 상태이며 각각 대결의 승자와 패자는 주어진다.

 

어떤 선수가 다른 선수들보다 이긴 횟수가 더 많을 때 우승자가 된다.

 

모든 대결이 끝났을 때 우승자가 될 수 있는 선수들을 구하여라.

 

 

해설에는 maximum flow 문제처럼 풀 수 있다고 하는데 한 번 공부해봐야겠다.

 

greedy로 풀수 있지 않을까라는 생각을 하였다.

 

선수 \( i \)가 우승자가 되는지를 판별하기 위해, 선수 \( i \)가 남은 대결에서 모두 이겼다고 가정한다.

 

그리고 다른 선수들을 이긴 횟수가 적은 순서대로 sorting을 한다.

 

그리고 첫번째 선수가 남은 경기들을 최대한 이기도록 만든다.

 

주어진 첫번째 선수의 이긴 횟수가 선수 \( i \)의 이긴 횟수와 같거나 크다면 선수 \( i \)가 이기는 것은 불가능하고, 가정 후 이긴 횟수가 같거나 크다면 작도록 만들어주는데, 두번째 선수부터 차례대로 첫번째 선수와 대결이 있었는지 확인하며 없었다면 그 선수가 이기도록 만든다.

 

이 과정에서 각 선수들의 이긴 횟수가 선수 \( i \)와 같거나 크다면 선수 \( i \)가 우승하는 일은 불가능하다.

 

첫번째 선수에 대하여 위 과정이 끝난다면 첫번째 선수들을 뺀 나머지 선수들에 대해 위 과정을 반복한다. (정렬부터 반복)

 

시간복잡도를 계산해보았을 때, 선수 \( i \)에 대하여 위 과정을 반복하여야 하기 때문에

 

\( O(N * N * N log N) = O(N^3 log N) \) 정도로 가능하지 않을까 싶다.

 

 

 

Ex. Card Deck Score

 

Ex - Card Deck Score

 

\( N \) 종류의 카드가 있다.

 

\( A_i \) 가 적혀있는 카드 \( B_i \) 장이 있다.

 

여기서 \( M \)장의 카드를 뽑으려 한다.

 

뽑은 카드들의 score는 뽑은 카드에 적혀있는 숫자들의 곱이다.

 

모든 가능한 조합의 합을 구하여라.

 

 

너무 복잡해서 나중에 다시 try