10/18~10/19 AtCoder 연습

10/18~10/19 AtCoder 연습

/*

수업시간에 몰래 풀어서 시간을 안쟀다.

약간의 실력 차이가 있다 보니 스터디가 실력 향상에 도움이 그다지 되는 것 같지 않다..

그래도 많은 문제를 접할 수 있다는 점은 좋다.

*/

AtCoder Regular Contest 081

C - Make a Rectangle

큰 수부터 2개/4개 이상 있는지 확인해주면 된다.

D - Coloring Dominoes

string을 한 줄만 읽어도 된다.

맨 처음에 오는 세로 타일은 3가지, 가로 타일은 6가지 경우가 있으며

그 이후는 직전것에 따라 달라지는데,

가로->가로: x3

가로->세로: x1

세로->가로: x2

세로->세로: x2

를 해주면 된다.

무작정 곱하기가 성립할 수 있는 이유는 색깔에 따른 특수성이 없기 때문.

E - Don't Be a Subsequence

주어진 string의 subsequence가 되지 않는 최소 길이의 string을 출력해주어야 한다.

접근이 상당히 난해한데, 각 알파벳별로 그 알파벳으로 끝나는 subsequence가 모두 존재하는 최대 길이를 저장해주면 된다.

a~z까지 모든 알파벳이 위 길이가 l을 만족할 때, 그 다음에 오는 알파벳은 l+1 길이의 모든 subsequence를 가질 수 있다. 말로 표현하기가 상당히 난해하다..

문제는 위 방법으로 길이는 쉽게 구할 수 있는데, 이 문제는 알파벳을 출력해주는 문제라는 점이다.

각 길이를 확인해줄 때마다, 길이 정보를 업데이트하지 못하게 하는 알파벳이 존재할 것인데, 그 알파벳들을 기록해주자.

사전순으로 가장 빠르게 오는 string을 출력해야하는데, 이는 맨 처음에 알파벳을 reverse시킨 뒤 확인하면 간단하게 해결 가능하다.

c.cpp

d.cpp

e.cpp

AtCoder Regular Contest 075

C - Bugged

합에서 10의 배수가 아닌 가장 작은 수를 빼면 된다.

D - Widespread

Binary Search 문제.

n번의 폭발로 몬스터를 다 제거시킬 수 있는지는

모든 몬스터에게 n * b의 데미지를 주고, 살아남은 몬스터들은 a - b의 데미지로 제거할 때,

a - b를 n번 이상 사용하는가로 간단히 확인 가능하다.

E - Meaningful Mean (추천)

상당히 흥미로운 문제. 평균이 K 이상인 구간의 갯수를 찾는 문제이다.

인덱스를 1~n이라 두었을 때,

배열 s[t]를 1~t까지 더한 합이라 두었을 때,

l번~r번까지의 평균은 $\frac{s[r] - s[l - 1]}{r - l + 1} >= K$를 만족해야 한다.

위 식을 정리하면 $s[r] - rK >= s[l - 1] - (l - 1)K$이다. 놀랍게도 양변의 형태가 동일하다.

따라서 각 인덱스 i별로 s[i] - iK값을 구해놓은 뒤, 그보다 작은 인덱스 중 저 값이 같거나 작은 것의 갯수를 더해주면 된다.

펜윅 트리를 이용하면 쉽게 구현 가능하다. 다만, 값의 범위가 크므로 값을 크기순으로 1, 2, ...로 바꾸어주는 과정을 추가하였다.

c.cpp

d.cpp

e.cpp