지금까지의 삶 + 12/25 PS

입시가 끝났다. 서울대학교 컴퓨터공학부에 입학하게 되었다.

이제 다시 PS를 시작해야 한다.

 

내 큰 계획은 다음과 같다.

 

1. PS 재활 + 코드포스 기초 쌓기

2. 백준 기초부터 다시 풀기

3. 흥미로운 것들 학습. 지금은 가우스 소거법과 hld를 배우고 싶다.

4. 코드포스 블루 찍기

 

일단 코드포스에서 쉬운 문제들을 잡고 풀어보았다.

실력이 처참함을 다시 깨닫는다.

 

Codeforces 1620B. Triangles on a rectangle

간단한 문제이다. 삼각형의 넓이는 밑변과 높이에 의존한다. 최소한 두 점이 같은 변 위에 존재하므로 높이가 최대일 때는 나머지 한 점이 반대편에 존재할 때이다.따라서 네 변 각각에 대해 거리가 최대인 점의 쌍을 찾아서 높이를 곱해주면 된다.

 

Codeforces 1618D. Array and Operations

간단한 문제인데 생각하지 못했다;; 오랜만이라 어쩔 수 없는듯.

일단 배열을 정렬하자.

분모가 최대인 게 당연히 이득이다. exchange argument로 쉽게 증명 가능하다.

이제 분자에 뭐가 오느냐가 중요한데.. 놀랍게도 n-2k+1번째에서 n-k번째까지를 고르면 된다.

만약 저들보다 작은 걸 골라서, 가우스값을 1에서 0으로 만들었다면,

결국 마지막에  남은 값들을 더할 때 1보다 크거나 같은 값을 더하게 되므로 최적이 아니다. 

따라서 그냥 가장 큰 값들을 분자에 넣는 게 최적해이다.

 

이제 적절히 배열해주면 된다. 분모와 분자가 같은 게 가장 적게 만드려면 n-i와 n-k-i를 매칭해주면 된다.

이게 왜 그런지는..모르겠다. PS 고수들은 다 아나 보다.

사실 어느 정도는 직관적인데, 같은 숫자들은 연속적으로 나타날 테니까 최대한 멀리 떨어트려 놓는게 이득일거라는 느낌은 든다.

 

분모가 가장 커야 한다는 사실을 빨리 캐치하는게 중요한 것 같다. 나는 저 사실을 몰라서 한참 고민했다.

 

Codeforces 1617C. Paprika and Permutation

문제를 관찰하다 보면 알 수 있는 사실)

1. 어떤 n에 대해 나머지를 a가 되도록 만들고 싶다면, 나눌 숫자를 n-a의 약수로 잡으면 된다.

단, 이때 그 약수는 a보다 커야 한다. 따라서 n-a>a를 만족해야 한다.

 

2. 보통 작은 숫자부터 관찰하면서 현재 존재하지 않는 숫자로 만드는 것이 이득이다.

 

결론)

i) 작은 숫자부터 iterating한다. 만들고 싶은 숫자를 i라고 하자.

ii) 현재 iterate하는 숫자를 a라 하자. a가 1부터 n 사이라면 vis에 추가한다.

iii) 아니면 a를 이용해 i를 만들 수 있는지 확인한다.(a>2i) 불가능하다면 i 이상의 숫자를 절대 만들 수 없으므로 답은 -1이다.iv) 가능하다면 i를 만들고, 아직 만들어지지 않은 다음 숫자를 찾는다. (vis 이용하면 됨)

 

나는 투포인터 느낌으로 했는데 이분 탐색도 가능한 것 같다.

**궁금한 것: 투포인터와 이분탐색이 함께 사용 가능한 경우가 많다. 문제 상황이 어떻게 돼야 두 알고리즘을 동시에 쓸 수 있을까?

 

Codeforces 1613B. Absent Remainder

문제를 잘못 읽었다. 이런 실수를 하면 그 때 코드포스는 멸망한다.

아무 쌍이나 상관없으므로 가장 작은 수로 나누면 나머지가 자신보다 작아서 무조건 성립한다.

 

Codeforces 1610B. Kalindrome Array

양쪽에서 한 칸씩 검사하면서 팰린드롬을 만족하지 않는 첫 지점을 찾는다.

그러면 캘린드롬을 만들기 위한 $x$의 후보가 두 개 나온다.

각각에 대해 테스트해보면 된다.