--- id: "imported/blog/history/at/abc-331" title: "AtCoder Beginner Contest 331" description: "저번주 ABC에서 E번을 1분차로 제출 못한 이후로 또 고질병(경계선을 못넘는 병)이 도지나 했는데, 다행히 그린에 안착했다." kind: "record" published: "2023-12-02T00:00:00.000Z" tags: ["PS","atcoder"] url: "https://www.readiz.com/blog/history/at/abc-331/" markdownUrl: "https://www.readiz.com/blog/history/at/abc-331/index.md" --- # AtCoder Beginner Contest 331 # ABC 331 Upsolving ![원문에 첨부된 이미지](https://www.readiz.com/assets/2023-12-02-23-30-30.png) 저번주 ABC에서 `E`번을 1분차로 제출 못한 이후로 또 고질병(경계선을 못넘는 병)이 도지나 했는데, 다행히 그린에 안착했다. - 대회 참가 유무: Y - 최종 Performance: 1353 (Rank: 1461 / 10520) - Round 링크: [Top](https://atcoder.jp/contests/abc331) / [Tasks](https://atcoder.jp/contests/abc331/tasks) - 문제별 결과 | A | B | C | D | E | F | G | | :-: | :-: | :-: | :-: | :-: | :-: | :-: | | AC | AC | AC | AC | AC | - | - | `C` 에서 `upper_bound` 사용시 `end` check를 하지 않아서 3틀을 했다. `CPH`가 갑자기 동작하지 않아서 좀 멘붕이었는데, 그런거 치고 잘 쳤다는 개인적인 평가. ## A - Tomorrow - 문제 링크: - Score: 100점 - 문제 예상 티어: Bronze IV 하루 뒤의 날짜를 출력하는 문제. 다음 달로 넘어가는 case, 다음 해로 넘어가는 case 모두 빼먹지 말아야 한다. ## B - Buy One Carton of Milk - 문제 링크: - Score: 200점 - 문제 예상 티어: Silver V 정해는 $O(100*100*100)$의 브루트포스. 나는 아래 형태의 `DP`로 풀었다. (Knapsack) ```cpp int dp[200]; memset(dp, 0x3F, sizeof(int) * 200); dp[0] = 0; for(int i = 1; i <= 6; ++i) dp[i] = S; for(int i = 6; i <= 100; ++i) { if (i >= 6) { dp[i] = min(dp[i], dp[i - 6] + S); } if (i >= 8) { dp[i] = min(dp[i], dp[i - 8] + M); } if (i >= 12) { dp[i] = min(dp[i], dp[i - 12] + L); } } int ans = 0x7FFFFFFF; for(int i = N; i <= N + 12; ++i) { if (dp[i] < ans) ans = dp[i]; } printf("%d\n", ans); ``` ## C - Sum of Numbers Greater Than Me - 문제 링크: - Score: 300점 - 문제 예상 티어: Gold V 여기서 구현 이슈로 3틀을 했다. `upper_bound` 에서 결과가 없으면, `end()` iterator로 위치하고, 여기에는 쓰레기값이 들어가 있음에 유의하도록 하자. ## D - Tile Pattern - 문제 링크: - Score: 450점 - 문제 예상 티어: Gold I 정해는 2차원 `Prefix Sum` + Case work 였다. 나는 `2D Fenwick` 으로 처리했다. 그렇지만 중간에 board가 업데이트 되는 쿼리가 없기 때문에 정해가 더 좋아보인다. 타일이 반복된다는 것이 구현을 복잡하게 만들었다. 따져야할 케이스가 많기 때문에, `D`를 건너뛴 사람들도 많이 보였고, 결론만 놓고 보면 `D` 풀 시간에 `E`와 `F`를 푸는 것이 정배 였던 것 같다. 다행히 시간 내에 `AC`를 받아서 다행이지만, 만약 구현하다가 시간을 초과했다면 저번주의 악몽이 되풀이 되었을 듯.. 개인적으로는 구현 연습에 상당히 도움이 되는 문제였다고 생각한다. 다음에 비슷한 유형이 나오면 좀 더 빨리 풀 수 있지 않을까.. ## E - Set Meal - 문제 링크: - Score: 450점 - 문제 예상 티어: Gold IV 정해는 이것저것 체크하면서 시간복잡도를 많이 줄인 것으로 보이는데($O(L(\log N + \log L) + N + M \log M)$), 나는 그냥 $O(NM)$ 베이스 솔루션에 정렬 후 적당한 커팅을 붙여서 통과시켰고, 이 방법이 더 간단한듯 하다. 브루트포스로 $O(10^{10})$ 정도 되는 솔루션의 경우에는 주로 커팅을 하면 시간 내에 잘 들어오는 것 같다. ## F - Palindrome Query (To be upsolved...) - 문제 링크: - Score: 525점 - 문제 예상 티어: ? Segment Tree를 활용해서 풀 수 있다고 한다. 추후 다시 풀어볼 예정. ## G Skip