Educational Codeforces Round 48 (Div. 2)

A - Death Note

한 페이지에 m개의 이름을 적을 수 있으며 매일 이름을 이어서 적을 때,

하루마다 몇페이지를 넘기는 지를 구하는 문제이다.

이전까지 이 페이지에 적었던 이름이 sum개, 이 날 적어야 하는 이름이 X개라면

(sum + X) / m개의 페이지를 넘겨야 하며 마지막 페이지에는 (sum + X) % m개의 이름이 있다는 것을 알 수 있다.

매번 sum값을 업데이트 해주며 (sum + X) / m값을 출력하면 풀 수 있는 문제이다.

B - Segment Occurrences

q개의 쿼리동안 문자열 s[l ... r]에 문자열 t가 몇 번 나타나는 지를 출력하는 문제이다.

n, m이 10^3로 비교적 작기에 완전탐색으로 O(nm)에 문자열 s에서 t가 어느 인덱스부터 등장하는 지 찾아낼 수 있다.

이후 쿼리동안 l과 r-t.size()+1사이에 등장했다고 할 경우 이 개수들을 모두 더해 답을 출력해주면 된다.

좀 더 시간복잡도를 줄이고 싶다면 부분합을 구하여 값을 계산해주면 되는 문제이다.

 

C - Vasya And The Mushrooms

2*N칸의 growth rate가 주어질 때, (1, 1)부터 minute마다 한 칸 씩 상하좌우 방향으로 이동하여

중복하지 않고 모든 칸을 거치면서 growth rate * minute의 합이 최대가 되는 값을 구하는 문제이다.

자세히 살펴보면 방법이 처음에는 위아래로 지그재그로 움직이면서 이동하다가

어느 열 c에서부터 끝 열까지, 끝 열에서 c까지 움직이는 방법만 존재한다.

이를 빠르게 구하기 위해 미리 일부의 값을 구해놓는 전처리 작업을 한 뒤 문제에 맞게 계산해주면 풀 수 있는 문제이다.

D - Vasya And The Matrix

모든 행, 열마다의 XOR값이 주어질 때 이를 만족하는 행렬을 구하는 문제이다.

XOR의 특징인 1의 개수가 짝수이면 0, 1의 개수가 홀수이면 1임을 이용하여 문제에 좀 더 쉽게 접근 할 수 있다.

a0 a1 a2 a3 ... b0 b1 b2 b3 ..를 XOR한 값이 0이 아닐 경우 1이 남게 되므로 NO를 출력하면 되며,

아닐 경우 mat[i][0] (i >= 1)의 값은 ai, mat[0][i] (i >= 1)의 값은 bi을 채워주고

채운 값과 mat[0][0]을 제외한 곳을 0으로 하게 되면 a0, b0를 제외한 모든 행, 열이 성립하는 것을 알 수 있다.

이후 mat[0][0]는 mat[0][i] (i >= 1)에 들어있는 b1 b2 b3 ...의 XOR값과 mat[0][0]의 XOR값이 a0가 되어야하므로

a0 b1 b2 b3 ...를 XOR한 값을 mat[0][0]로 하여 출력해주면 되는 문제이다.

E - Rest In The Shades

X

F - Road Projects

X

G - Appropriate Team

X