--- id: "imported/blog/history/at/abc-328" title: "AtCoder Beginner Contest 328" description: "상당히 웰논들이었다. F번도 웰논이라는데 못풀어서 아쉽다. 저번주 D번이랑도 느낌은 비슷했는데, 복기를 안해서 좀 아쉬웠다." kind: "record" published: "2023-11-11T00:00:00.000Z" tags: ["PS","atcoder"] url: "https://www.readiz.com/blog/history/at/abc-328/" markdownUrl: "https://www.readiz.com/blog/history/at/abc-328/index.md" --- # AtCoder Beginner Contest 328 # ABC 328 Upsolving ![원문에 첨부된 이미지](https://www.readiz.com/assets/2023-11-11-23-23-30.png) ~~파멸적 떡상~~ - 대회 참가 유무: Y - 최종 Performance: 1319 (Rank: 1639 / 10710) - Round 링크: [Top](https://atcoder.jp/contests/abc328) / [Tasks](https://atcoder.jp/contests/abc328/tasks) - 문제별 결과 | A | B | C | D | E | F | G | | :-: | :-: | :-: | :-: | :-: | :-: | :-: | | AC | AC | AC | AC | AC | WA | - | 상당히 웰논들이었다. `F`번도 웰논이라는데 못풀어서 아쉽다. 저번주 `D`번이랑도 느낌은 비슷했는데, 복기를 안해서 좀 아쉬웠다. ## A - Not Too Hard - 문제 링크: - Score: 100점 - 문제 예상 티어: Bronze V 그냥 대소비교 하는 기초 문제. ## B - 11/11 - 문제 링크: - Score: 200점 - 문제 예상 티어: Silver II 제목만 보고 빼빼로 데이 기념 문제인가 했는데 그건 전혀 아니었고, 월 / 일이 모두 같은 숫자로 구성되는 경우들을 세는 문제였다. 조건 찾는게 좀 빡치는 문제. 요구사항의 복잡성만으로 `Silver 2`를 줄만한 문제인거 같다. ## C - Consecutive - 문제 링크: - Score: 300점 - 문제 예상 티어: Gold V $N, Q \le 3 \times 10^5$ 인 조건으로, 무조건 전처리가 필요함을 알 수 있다. 다행히도, 조금 읽어보면 빈출 유형인 `Prefix Sum`임을 알 수 있고, 쉽게 풀 수 있었다. `Prefix Sum`을 사용하면 각 쿼리를 $O(1)$로 처리할 수 있으므로, `TLE`를 피할 수 있다. ## D - Take ABC - 문제 링크: - Score: 425 - 문제 예상 티어: Gold IV 백준이 비슷한 문제가 있다고 한다. 정해는 여러가지가 있을 수 있겠는데, 나는 `Linked List`로 풀었다. `Stack` 써도 될듯 하다. - 문자열 폭발 문제: ## E - Modulo MST - 문제 링크: - Score: 475 - 문제 예상 티어: Gold II `MST`는 `크루스칼 알고리즘` 등을 사용하면 쉽게 구할 수 있는데, 문제는 `Modulo` 결과를 최소화 해야 한다. 따라서, `PQ`를 사용한 풀이는 불가하다. 다행히도, $N \le 8$이라서, 완전 탐색이 가능하다. `MST`에서 했던대로, 간선을 $N-1$개만 사용하면서, `Cycle`이 없도록 하는 것들을 완전 탐색 해서 최소가 되는 값을 구해주면 되겠다. `Cycle` 판정은 아래처럼 한다. ```cpp 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...) - 문제 링크: - Score: 525 - 문제 예상 티어: ??? 풀이 실패. 어디서 틀리는지는 알았지만 해결을 못했다. 이거도 백준에 비슷한 문제가 있다고 한다. 에디토리얼 보지 않고 한번 풀어볼 예정. - 교수님은 기다리지 않는다 문제: ## G - Cut and Reorder (To be upsolved?) - 문제 링크: - Score: 575 - 문제 예상 티어: ??? 업솔빙 할지 안할지 잘 모르겠다. 나름 전형적인 `DP` 문제이지만, 문제 조건 때문에 `DP 최적화`가 붙어야 한다고 한다. 연습삼아 한번 풀어볼까... (비트 DP?)