Educational Codeforces Round 47 (Div. 2)

A - Game Shopping

간단한 구현 문제로, 게임의 가격을 보면서 지갑에 있는 돈으로 게임을 살 수 있을 경우 지갑의 인덱스를 증가시킨다.

이 때 지갑의 인덱스가 최대 인덱스만 넘어가지 않도록 처리해주면 풀 수 있는 문제이다.

B - Minimum Ternary String

0과 1, 1과 2만 위치를 바꿀 수 있으며 이 때의 사전 순으로 가장 앞에 있는 문자열을 출력하는 문제로

1은 무조건 바꿀 수 있다는 아이디어를 이용하여 1의 개수와 첫 2 뒤에 있는 0의 개수를 세어준 뒤,

첫 2 뒤에 있는 0의 개수만큼의 '0' +  전체 문자열에서의 1의 개수만큼의 '1' + 남은 문자열을 출력해주면 되는 문제이다.

 

C - Annoying Present

처음에 0으로 초기화된 n개의 칸으로 구성된 배열로 시작하여 모든 칸에 x + d * dist(i, j)를 더해주는 수식을

m번 반복했을 때의 각 칸 값들의 평균의 최대값을 묻는 문제이다.

먼저 매 수식마다 모든 칸에 x를 더해주기에 x*n을 더해주며 d * dist(i, j)의 값은 임의의 i의 위치에 따라 달라지는데

d가 양수일 때는 모든 칸의 dist(i, j)값의 합이 최대, d가 음수일 때는 모든 칸의 dist(i, j)값의 합이 최소여야 한다.

최대일 때는 n이 6일 때 0,1,2,3,4,5와 같이 i가 1이나 n일 때가 되고

최소일 때는 n이 5일 때 2,1,0,1,2,3과 같이 i가 n/2이거나 n/2+1일 때가 된다.

이를 이용하여 가능한 총 합의 최댓값을 탐욕법 기법을 이용하여 구한 뒤 평균을 구하기 위하여 n으로 나누어주면 된다.

이 때 총합을 구할 때 int 자료형의 범위를 벗어날 수도 있으므로 long long 자료형으로 표현해주면 풀 수 있는 문제이다.

D - Relatively Prime Graph

정점 u와 v의 GCD가 1일 때 간선으로 이을 수 있는 그래프에서 정점과 간선의 수가 주어졌을 때

이러한 그래프를 만들 수 있는 지 묻는 문제이다.

대회 내에서 오일러 피함수를 이용하여 문제를 푸는 방법을 여럿 고민해보았다.

이 때 오일러 피함수란 1부터 n까지의 정수 중 서로소의 개수를 뜻하며

n이 소수인 경우 서로소의 개수는 n-1이고 소인수분해를 하여 소인수의 값으로 빠르게 서로소의 개수를 알아낼 수 있다.

(관련문제 : BOJ 11689번: GCD(n, k) = 1)

이 오일러 피함수를 n이 600일때까지의 모든 값을 더하면 m의 최댓값인 100000을 넘어가게 되어

이 중 포문으로 i, j의 GCD가 1인지 매번 반복해주기만 하여도 시간 내에 풀 수 있는 문제이다.

E - Intercity Travelling

모든 점에 rest sites가 있을 수 있을 때의 difficulty의 기대값에 2^n-1을 곱한 값을 출력해주는 문제이다.

이 때 출력해주는 값은 즉 모든 difficulty의 합이 된다.

n이 4일 때의 더해줘야 할 kilometer별 모든 difficulty를 나타내보면

a1 a2 a3 a4

a1 a2 a3 a1

a1 a2 a1 a2

a1 a2 a1 a1

a1 a1 a2 a3

a1 a1 a2 a1

a1 a1 a1 a2

a1 a1 a1 a1

이 되고 kilometer 별 개수를 잘 살펴보면 이는 처음에는 a1이 8개였다가 그다음에는 a1의 절반이 a2가 된다.

그 다음에는 a2의 절반이 a3의 절반이 되며 마지막에는 a3의 절반이 a4가 되는 것을 알 수 있다.

이를 이용하여 처음 초기값은 a1 * 2^n-1로 시작하여

매 다음 kilometer마다 이전 kilometer difficulty의 절반을 빼주고 이번 difficulty의 절반을 더해주는 과정을

반복하면서 그 결과 값을 모두 더해준 값을 나머지 연산을 잘 적용하여 출력해주면 풀 수 있는 문제이다.

F - Dominant Indices

X

G - Allowed Letters

X