ABC 328 Upsolving

~~파멸적 떡상~~

대회 참가 유무: Y
최종 Performance: 1319 (Rank: 1639 / 10710)
Round 링크: Top / Tasks
문제별 결과

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

상당히 웰논들이었다. F번도 웰논이라는데 못풀어서 아쉽다. 저번주 D번이랑도 느낌은 비슷했는데, 복기를 안해서 좀 아쉬웠다.

A - Not Too Hard

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

그냥 대소비교 하는 기초 문제.

B - 11/11

문제 링크: https://atcoder.jp/contests/abc328/tasks/abc328_b
Score: 200점
문제 예상 티어: Silver II

제목만 보고 빼빼로 데이 기념 문제인가 했는데 그건 전혀 아니었고, 월 / 일이 모두 같은 숫자로 구성되는 경우들을 세는 문제였다. 조건 찾는게 좀 빡치는 문제. 요구사항의 복잡성만으로 Silver 2를 줄만한 문제인거 같다.

C - Consecutive

문제 링크: https://atcoder.jp/contests/abc328/tasks/abc328_c
Score: 300점
문제 예상 티어: Gold V

$N, Q \le 3 \times 10^5$ 인 조건으로, 무조건 전처리가 필요함을 알 수 있다. 다행히도, 조금 읽어보면 빈출 유형인 Prefix Sum임을 알 수 있고, 쉽게 풀 수 있었다. Prefix Sum을 사용하면 각 쿼리를 $O(1)$ 로 처리할 수 있으므로, TLE를 피할 수 있다.

D - Take ABC

문제 링크: https://atcoder.jp/contests/abc328/tasks/abc328_d
Score: 425
문제 예상 티어: Gold IV

백준이 비슷한 문제가 있다고 한다. 정해는 여러가지가 있을 수 있겠는데, 나는 Linked List로 풀었다. Stack 써도 될듯 하다.

문자열 폭발 문제: https://www.acmicpc.net/problem/9935

E - Modulo MST

문제 링크: https://atcoder.jp/contests/abc328/tasks/abc328_e
Score: 475
문제 예상 티어: Gold II

MST는 크루스칼 알고리즘 등을 사용하면 쉽게 구할 수 있는데, 문제는 Modulo 결과를 최소화 해야 한다. 따라서, PQ를 사용한 풀이는 불가하다. 다행히도, $N \le 8$ 이라서, 완전 탐색이 가능하다. MST에서 했던대로, 간선을 $N-1$ 개만 사용하면서, Cycle이 없도록 하는 것들을 완전 탐색 해서 최소가 되는 값을 구해주면 되겠다.

Cycle 판정은 아래처럼 한다.

if (uf.findRoot(c.s) != uf.findRoot(c.e)) {
    // no cycle: 비용을 더해준다.
    uf.merge(c.s, c.e);
    csum += c.weight;
    csum %= K;
} else {
    // cycle
    flag = false;
    break;
}

F - Good Set Query (To be upsolved…)

문제 링크: https://atcoder.jp/contests/abc328/tasks/abc328_f
Score: 525
문제 예상 티어: ???

풀이 실패. 어디서 틀리는지는 알았지만 해결을 못했다. 이거도 백준에 비슷한 문제가 있다고 한다. 에디토리얼 보지 않고 한번 풀어볼 예정.

교수님은 기다리지 않는다 문제: https://www.acmicpc.net/problem/3830

G - Cut and Reorder (To be upsolved?)

문제 링크: https://atcoder.jp/contests/abc328/tasks/abc328_g
Score: 575
문제 예상 티어: ???

업솔빙 할지 안할지 잘 모르겠다. 나름 전형적인 DP 문제이지만, 문제 조건 때문에 DP 최적화가 붙어야 한다고 한다. 연습삼아 한번 풀어볼까… (비트 DP?)