[1일차] Educational Codeforces Round 68 (Rated for Div. 2)

내가 처음으로 코포를 쳤던 라운드를 쳤다.

결과는 이렇다. 

 

A. Remove a Progression (-, 00:01)

문제의 그림을 참고해서 잘 관찰하면, 답은 무조건 2x임을 알 수 있다.

답은 쿼리당 O(1)만에 구할 수 있다.

 

코드

 

B. Yet Another Crosses Problem (-1, 00:15)

각 행과 열에 대해 '.'의 갯수를 세준 다음, 모든 행과 열 중 하나씩 골라서 '.'의 갯수의 최소를 구해준다.

이때 행과 열의 교차점에 '.'이 있을 수 있으므로 그때는 1을 빼준다.

이는 O(nm)만에 구할 수 있고, nm<=4*10^5이기 때문에 시간제한 안에 문제를 풀 수 있다.

 

코드

 

C. From S To T  (-1, 00:35)

YES인 경우는 다음과 같다.

편의상 fr(i)를 어떤 특정한 알파벳이 문자열 i에 들어간 수라고 정의하겠다.

-각 알파벳마다 fr(s)+fr(p)>=fr(t)를 만족해야 한다.

-p에 있는 문자를 t랑 비슷하게 만들기 위해 s에 끼워넣을 때, 다 끼워넣은 후 s=t를 만족해야 한다.

 

이는 각 쿼리당 O(|p|)로 판별할 수 있다.

코드

 

D. 1-2-K Game  (-, 00:59)

-K가 3의 배수가 아닌 경우

칸을 0-based라고 한다면, 항상 3의 배수인 곳에 칩이 있으면 Alice가 진다.

이때 K가 3의 배수가 아니라면 항상 3의 배수인 곳에서 K칸을 넘어간다고 해도 항상 3의 배수가 아닌 곳에 도착하게 된다.

그러므로 그냥 n이 3의 배수인지만 확인해주면 된다.

-K가 3의 배수인 경우

K가 3의 배수인 경우는 종이에 써가면서 관찰한 결과, 이러한 패턴이 반복된다는 걸 알 수 있었다. 

=편의상 B를 Bob이 이길 때, A를 Alice가 이길 때라고 하자. 그렇다면 길이가 K+1인 BAABAA....BAAA의 패턴, 즉 BAA가 계속 반복되다가 K번째에 A가 하나 더 추가된 꼴이 반복된다.

그러므로 헤당 위치가 B의 위치인지 판별하기 위해 n을 K+1로 나눈 나머지를 구하자. 나머지가 K가 아닌 3의 배수라면 B의 위치이므로 이를 판별해주면 된다.  

 

각 쿼리당 O(1)로 풀 수 있다.

코드

 

E, F는 업솔빙을 할 것이다. 완료한다면 블로그에 올리도록 하겠다.

 

하고 나서.

생각보다 만족스럽다. B,C에서 약간의 뇌절을 한 것 빼고는 말이다.

저걸 친 때가 아마 2~3년 전이었던 걸로 기억하는데 그때에 비해선(1솔, A 50분 걸렸었다..) 훨씬 나아진 걸 생각하니 기분이 좋았다.

그리고 그때 A를 50분만에 풀고 좋아하면서 충격을 먹었던 추억이 떠올라서 그때 회상하는 재미가 있었다.