ABC 334 Upsolving

• 대회 참가 유무: Y
• 최종 Performance: 1206 (Rank: 1807 / 11231)
• Round 링크: Top / Tasks
• 문제별 결과

A	B	C	D	E	F	G
AC	AC	WA	AC	AC	-	-

B, C에서 WA, TLE를 많이 헀고, 최종적으로 C는 WA. 업솔빙 필요하다. F, G 도 업솔빙 필요해보인다. 그래도 망한거 치고는 D, E를 흔들리지 않고 풀 수 있었어서 다행.

A - Christmas Present

• 문제 링크: https://atcoder.jp/contests/abc334/tasks/abc334_a
• Score: 100점
• 문제 예상 티어: Bronze V

Do you know 비교문? 여기까진 좋았다..

B - Christmas Trees

• 문제 링크: https://atcoder.jp/contests/abc334/tasks/abc334_b
• Score: 250점
• 문제 예상 티어: Silver V

여기부터 말렸다. 사실 지금 생각해보면 $M$ 범위가 $M \le 10^9$라서 절대 1씩 증가시켜서는 시간내에 안들어오는건데.. 왜 잘못된 생각을 했는지 모르겠다. 수식을 차분히 전개하는 문제.

• $\displaystyle \frac {L - A} M \le k \le \frac {R - A} M$

이라는 것에 주목해서 풀면 되겠다. C++에서는 MOD 연산이 음수에 적용되면 음수가 나오므로, MOD만큼 더해주어야 한다.

C - Socks 2 (To be upsolved..)

• 문제 링크: https://atcoder.jp/contests/abc334/tasks/abc334_c
• Score: 350점
• 문제 예상 티어: Gold IV

말린 문제 2. 업솔빙 해야한다. 익숙치 않은 양방향 Greedy.

D - Reindeer and Sleigh

• 문제 링크: https://atcoder.jp/contests/abc334/tasks/abc334_d
• Score: 400점
• 문제 예상 티어: Gold V

너무 전형적이라 오히려 C보다 쉬웠다. 누적합을 구해준 뒤 이분탐색을 때리면 된다.

E - Christmas Color Grid 1

• 문제 링크: https://atcoder.jp/contests/abc334/tasks/abc334_e
• Score: 450점
• 문제 예상 티어: Gold III

엄청 전형적이진 않았지만, 그래도 풀이를 떠올리기는 어렵지 않았다. BFS로 각 컴포넌트들에 id를 부여해준 뒤, 빈칸에서 인접한 곳에 컴포넌트가 몇개 있는지 보면 된다.

그리고 역시나 아래 글은 앳코더 할거면 다시 봐야..

• 빠른 거듭제곱과 모듈로 역원

F - Christmas Present 2 (To be upsolved…)

• 문제 링크: https://atcoder.jp/contests/abc334/tasks/abc334_f
• Score: 550점
• 문제 예상 티어: ?

Deque DP라고 한다. 백준 5977랑 비슷하다고 하니 DP 연습겸 여유되면 살펴볼 예정

G - Christmas Color Grid 2 (To be upsolved…)

• 문제 링크: https://atcoder.jp/contests/abc334/tasks/abc334_g
• Score: 650점
• 문제 예상 티어: ?

E의 정반대 버전. 컴포넌트를 중간을 끊는다. 뭔가 전형적인 문제같은데 아직은 잘 모르겠다.