ABC 331 Upsolving

저번주 ABC에서 E번을 1분차로 제출 못한 이후로 또 고질병(경계선을 못넘는 병)이 도지나 했는데, 다행히 그린에 안착했다.

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

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

C 에서 upper_bound 사용시 end check를 하지 않아서 3틀을 했다. CPH가 갑자기 동작하지 않아서 좀 멘붕이었는데, 그런거 치고 잘 쳤다는 개인적인 평가.

A - Tomorrow

문제 링크: https://atcoder.jp/contests/abc331/tasks/abc331_a
Score: 100점
문제 예상 티어: Bronze IV

하루 뒤의 날짜를 출력하는 문제. 다음 달로 넘어가는 case, 다음 해로 넘어가는 case 모두 빼먹지 말아야 한다.

B - Buy One Carton of Milk

문제 링크: https://atcoder.jp/contests/abc331/tasks/abc331_b
Score: 200점
문제 예상 티어: Silver V

정해는 $O(100*100*100)$ 의 브루트포스. 나는 아래 형태의 DP로 풀었다. (Knapsack)

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

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

여기서 구현 이슈로 3틀을 했다. upper_bound 에서 결과가 없으면, end() iterator로 위치하고, 여기에는 쓰레기값이 들어가 있음에 유의하도록 하자.

D - Tile Pattern

문제 링크: https://atcoder.jp/contests/abc331/tasks/abc331_d
Score: 450점
문제 예상 티어: Gold I

정해는 2차원 Prefix Sum + Case work 였다. 나는 2D Fenwick 으로 처리했다. 그렇지만 중간에 board가 업데이트 되는 쿼리가 없기 때문에 정해가 더 좋아보인다. 타일이 반복된다는 것이 구현을 복잡하게 만들었다. 따져야할 케이스가 많기 때문에, D를 건너뛴 사람들도 많이 보였고, 결론만 놓고 보면 D 풀 시간에 E와 F를 푸는 것이 정배 였던 것 같다. 다행히 시간 내에 AC를 받아서 다행이지만, 만약 구현하다가 시간을 초과했다면 저번주의 악몽이 되풀이 되었을 듯..

개인적으로는 구현 연습에 상당히 도움이 되는 문제였다고 생각한다. 다음에 비슷한 유형이 나오면 좀 더 빨리 풀 수 있지 않을까..

E - Set Meal

문제 링크: https://atcoder.jp/contests/abc331/tasks/abc331_e
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…)

문제 링크: https://atcoder.jp/contests/abc331/tasks/abc331_f
Score: 525점
문제 예상 티어: ?

Segment Tree를 활용해서 풀 수 있다고 한다. 추후 다시 풀어볼 예정.

G

Skip