AtCoder Beginner Contest #247

Tasks - AtCoder Beginner Contest 247

 

 

A. Move Right

 

A - Move Right

 

0과 1로만 되어있는 길이 4의 문자열이 주어진다.

 

오른쪽으로 한 칸 움직였을 때의 문자열을 구하여라

 

4칸을 벗어나는 경우 사라지고 빈 칸의 경우 0으로 채워진다.

 

 

0을 출력한 다음 0, 1, 2번째 문자를 차례대로 출력하면 된다.

 

 

 

B. Unique Nicknames

 

B - Unique Nicknames

 

\( N \) 사람의 성과 이름이 주어진다.

 

그 사람들의 nickname을 각각 부여하려고 한다.

 

\( i \)번째 사람의 nickname은 그 사람의 성 또는 이름이어야하고 다른 사람의 성이나 이름이면 안된다.

 

모든 사람들에게 nickname을 부여할 수 있는지 구하여라.

 

 

\( N \leq 100 \)으로 그냥 brute force를 사용하여도 된다.

 

아니면 map을 만들어서 성과 이름을 counting한 뒤 i번째 사람의 nickname을 고를 때 성과 이름을 counting에서 제외한 뒤 성과 이름 둘다 count가 1 이상이면 불가능하다.

 

 

 

C. 1 2 1 3 1 2 1

 

C - 1 2 1 3 1 2 1

 

sequence \( S_n \)을 다음과 같이 정의하자.

 

- \( S_1 \)은 1만 가지고 있는 길이가 1인 sequence다.

 

- \( S_n \) ( \( n \geq 2 \) )은 \( S_{n - 1} \), n, \( S_{n - 1} \)을 순서대로 concatenating하여 얻은 sequence다.

 

예를 들어 \( S_3 \)은 \( S_2 \), 3, \( S_2 \) = \( S_1 \), 2 \( S_1 \), 3, \( S_1 \), 2, \( S_1 \) = 1, 2, 1, 3, 1, 2, 1 이다.

 

\( N \) ( \( 1 \leq N \leq 16 \) ) 이 주어질 때, \( S_N \)을 출력하여라.

 

 

dynamic programming을 이용하여 구하면 된다.

 

 

 

D. Cylinder

 

D - Cylinder

 

원통 하나가 있을 때 주어진 query를 순서대로 수행하여라.

 

query의 종류는 다음과 같다.

 

- "1 x c": x라고 적혀진 공을 c개 원통의 오른쪽 끝에 넣는다.

 

- "2 c": 왼쪽 끝에서 공 c개를 꺼내 합을 출력한다.

 

 

deque를 이용하면 된다.

 

 

 

E. Max Min

 

Tasks - AtCoder Beginner Contest 247

 

길이 \( N \) sequence \( A \)와 정수 \( X \), \( Y \)가 주어진다.

 

다음 조건을 만족하는 pair ( \( L \), \( R \) )의 갯수를 구하시오.

 

- \( 1 \leq L \leq R \leq N \)

 

- \( A_L, A_{L + 1}, ..., A_R \)의 최댓값은 \( X \), 최솟값은 \( Y \)다.

 

 

상당히 구현을 더럽게 했었는데 맞아서 신기했다.

 

잘 구현한 코드를 찾아서 링크를 걸어본다.

 

Submission #30857197 - AtCoder Beginner Contest 247

 

진짜 이런식으로 짜야하는데,,

 

 

 

F. Cards

 

F - Cards

 

카드 \( N \)개가 있다.

 

각각의 카드 앞, 뒷면에는 \( P_i \), \( Q_i \)라는 수가 적혀있다.

 

\( P_1, P_2, ..., P_N \)과 \( Q_1, Q_2, ..., Q_N \)은 \( 1, 2, ..., N \)의 permutation이다.

 

다음과 같은 조건을 만족시키는 카드 고르는 방법은 몇 가지인가.

 

- 모든 수 \( 1, 2, ..., N \)이 고른 카드들 중 적어도 하나에 적혀있어야 한다.

 

 

각 숫자 \( 1, 2, ..., N \)을 vertex로, 카드를 쓰여진 두 숫자를 잇는 edge로 봤을 때 결국 그래프로 나타낼 수 있다.

 

그래프의 모양을 대충 생각해보자면 cycle으로 이루어진 여러 component 형태를 띌 것이다.

 

따라서 각 cycle마다 모든 vertex를 cover하는 edge들을 선택하는 경우의 수를 구해서 곱해주면 된다.

 

한 cycle에 대하여 길이가 \( k \)라고 했을 때, cycle을 모두 cover하는 edge의 경우의 수를 dp로 구해보자.

 

cycle을 도는 순서대로 edge를 정렬했다고 가정하였을 때,

 

- dp[k][0]: \( k \) 길이의 cycle에서 첫 번째 edge를 선택하지 않고 마지막 edge를 선택한 경우

 

- dp[k][1]: \( k \) 길이의 cycle에서 첫 번째 edge를 선택하고 마지막 edge를 선택하지 않은 경우

 

- dp[k][2]: \( k \) 길이의 cycle에서 첫 번째 edge와 마지막 edge 모두 선택한 경우

 

 

점화식은 다음과 같이 나온다.

 

- dp[k][0] = dp[k - 2][0] + dp[k - 1][0]

 

- dp[k][1] = dp[k - 1][2]

 

- dp[k][2] = dp[k - 1][1] + dp[k - 1][2]

 

 

이를 이용하여 답을 계산해주면 된다.