--- id: "imported/blog/history/at/abc-326" title: "AtCoder Beginner Contest 326" description: "조건에 맞게 Takahashi가 계단을 탈지 엘베를 탈지 결정해주면 된다." kind: "record" published: "2023-11-14T00:00:00.000Z" tags: ["PS","atcoder"] url: "https://www.readiz.com/blog/history/at/abc-326/" markdownUrl: "https://www.readiz.com/blog/history/at/abc-326/index.md" --- # AtCoder Beginner Contest 326 # ABC 326 Upsolving ![원문에 첨부된 이미지](https://www.readiz.com/assets/2023-10-29-21-50-05.png) - 대회 참가 유무: Y - 최종 Performance: 1214 (Rank: 1852 / 11827) - Round 링크: [Top](https://atcoder.jp/contests/abc326) / [Tasks](https://atcoder.jp/contests/abc326/tasks) - 문제별 결과 | A | B | C | D | E | F | G | | :-: | :-: | :-: | :-: | :-: | :-: | :-: | | AC | AC | AC | AC | - | - | - | ## A - 2UP3DOWN - 문제 링크: - Score: 100점 - 문제 예상 티어: Bronze V 조건에 맞게 Takahashi가 계단을 탈지 엘베를 탈지 결정해주면 된다. ## B - 326-like Numbers - 문제 링크: - Score: 200점 - 문제 예상 티어: Silver V 문제에서 항상 이런 숫자가 존재한다고 했기 때문에 그냥 구현하면 되었다. 증명하라고 하면 쉽지 않을 듯. ## C - Peak - 문제 링크: - Score: 300점 - 문제 예상 티어: Gold V N의 범위가 $N \le 3 \times 10^5$ 이고, 숫자의 범위 $A_i \le 10^9$ 이기 때문에, 정렬 후 `lower_bound`를 통해 적절한 구간 $(x, x + M)$안에 속한 원소들의 수를 구해주면 되는 문제였다. 만약 숫자의 범위가 작다면 완탐이 오히려 빠를 수도 있지만 이 문제의 경우에는 아니었다. ## D - ABC Puzzle - 문제 링크: - Score: 450점 - 문제 예상 티어: Gold III 조금 까다로운 조건의 문제였다. 가지치기 dfs로 접근했는데 풀이가 뇌절의 뇌절을 거듭한 가운데 종료 5분전에 제출 할 수 있었다. 덕분에 다른 문제들도 풀만한 것들이었는데 풀 시간이 없었다.. 처음에 dfs를 2개로 나누어 생각했지만 이것은 오히려 패착이었다. 간단한 조건으로 푸는게 항상 옳다. 그냥 $x$ -> $x + 1$로 전이 시키고, $x$ == $N - 1$이 될 때 다음 row로 가게 하는 dfs가 유효했다. 다음에는 이런 유형 나올 때 너무 어렵게 접근하지 말자.. ## E - Revenge of "The Salary of AtCoder Inc." (Solved with Editorial) - 문제 링크: - Score: 450점 - 문제 예상 티어: Platinum V - 기댓값 이론 정리: [링크](https://www.readiz.com/blog/study/math/ev/) `기댓값 DP` 유형 이라고 한다. 문제 내에서 `Modular Inverse`도 요구하는 등 상당히 백준에서 일반적으로 접하기는 어려운 유형이다. 에디토리얼을 보고 풀이를 정리해본다. 우선, `기댓값`을 바로 구하기에는 난이도가 있다. `기댓값`을 구하기 이전에, 확률을 먼저 구해보도록 하자. $p_i$를 $A_i$엔이 지급되었을 때의 확률이라고 하자. 편의상 $p_0 = 1$로 정의하자. 그러면, 다음을 얻을 수 있다고 한다. - $p_i = \displaystyle \frac 1 N \sum_{j=0}^{i-1} p_j$ 위 수식을 처음부터 생각하기 어렵다. `small to large` 해보자. 만약 $N = 1$ 이라면 자명하게 $p_1 = 1$이다. $N = 2$라면 아래와 같은 경우가 있다. - $p_1 = \displaystyle \frac 1 2 (1) = \frac 1 2$ ... 처음 주사위를 던져서 1이 나왔을 확률 - $p_2 = \displaystyle \frac 1 2 (1 + \frac 1 2) = \frac 3 4$ ... (처음에 2가 바로 나왔을 확률) + (처음 주사위를 던져서 1, 그다음 2가 나왔을 확률) 모든 확률의 합이 $1$이 되지 않았다고 해서 당황할 필요는 없다. 지금 모든 확률이 독립인 경우를 다루고 있는 것이 아니다. $p_i$를 $A_i$엔이 지급되었을 때의 확률이라고 정의하고 있다. (실제 기댓값을 구하기 용이하도록) $N = 3$인 경우를 한번 더 생각해보자. - $p_1 = \displaystyle \frac 1 3 (1) = \frac 1 3$ - $p_2 = \displaystyle \frac 1 3 (1 + \frac 1 3) = \frac 4 9$ - $p_2 = \displaystyle \frac 1 3 (1 + \frac 1 3 + \frac 4 9) = \frac {16} {27}$ 여기서 $\frac 1 3$은 현재 $p_i$가 나오게 된 확률, 그리고 괄호 안에 들어간 숫자들의 합은 그 전 눈금들에 가 있는 상태들의 합이다. 수식이 어려울 뿐 `DP 상태전이`를 완벽하게 나타낸 표현이라고 볼 수 있다. 또한 위 수식은 누적합을 활용해 $O(N)$에 계산할 수 있다. 그리고 문제에서 최종적으로 우리가 구하고자 하는 값은 기댓값이고, 기댓값은 정의에 의해 아래처럼 구할 수 있다. - $E[X] = \displaystyle \sum_{i=1}^{N} x_ip_i$ 위 사실들을 조합하고, `Modular Inverse`를 이용해 최종적인 답을 구할 수 있다. 문제에서 나온 $998244353$ 라는 수는 `AtCoder`에서 좋아하는 소수인 듯 하다. 이 `체` 에서 $\displaystyle \frac 1 N$은 아래와 같이 구할 수 있다. `getInv(N)` 으로 구하면 된다. ```cpp ll fastPow(ll a, ll p) { ll res = 1LL; while (p) { if (p & 1LL) res = res * a % MOD; a = a * a % MOD; p >>= 1LL; } return res; } ll getInv(ll v) { return fastPow(v, MOD - 2); } ``` ## F - Robot Rotation (Upsolved) - 문제 링크: - Score: 525점 - 문제 예상 티어: Platinum V $N \le 80$ 조건에서 `MITM`의 냄새를 강하게 느꼈지만, 확신은 없었다. 방향이 2방향이라 양방향에서 출발하면 경우의 수가 $2^{40}$ 이고 이는 꽤 큰 수이기 때문.. 이 풀이가 유효한지 한번 도전해보려고 한다. (아니면 어쩔 수 없고..) 관찰해보면, 우선 처음 로봇의 방향의 양의 x축이다. 그리고 90도씩만 좌우로 회전을 하므로, $i$가 홀수인 항은 $y$좌표를, $i$가 짝수인 항은 $x$ 좌표를 결정짓는다는 사실을 먼저 관찰할 수 있다. 이렇게 되면 우선 각 축으로의 좌표가 $2^{40}$으로 줄어든다. 이 상태에서 `MITM`을 적용하면 $2^{20}$ 정도에 풀 수 있고 이는 해볼만 하다. 도착 좌표를 알고 있으므로 원점과, 도착 좌표 양쪽에서 `MITM`을 적용하면 풀린다. ...그런데 이렇게까지 하고 끝내면 사실 Gold I 정도의 난이도일 수 있다. 여기에 문제는 `경로 복원` 까지 요구한다. `MITM`을 하면서, 도달한 경로를 잘 저장했다가 복원해줘야 하는 로직이 추가된다. 다소 복잡한 `MITM`이고, 아래에 풀이를 정리해둔다. 시간복잡도는 $O(N 2^{N/4})$ 이 된다. (내 실제 풀이는 로그가 하나 더 붙긴하는데 대세에 지장은 없다) ```cpp ll N, X, Y; void solve() { scanf("%lld %lld %lld", &N, &X, &Y); vector dx, dy; for(int i = 0; i < N; ++i) { ll tmp; scanf("%lld", &tmp); if (i % 2 == 0) { dy.push_back(tmp); } else { dx.push_back(tmp); } } int dxsz1 = dx.size() / 2; int dysz1 = dy.size() / 2; int dxsz2 = dx.size() - dxsz1; int dysz2 = dy.size() - dysz1; // 1. 원점에서 출발하기 map px, py; int end = 1 << dxsz1; for(int cur = 0; cur < end; ++cur) { // 선택된 좌표들 ll cx = 0; for(int i = 0, p = 1; i < dxsz1; ++i, p <<= 1) { if (cur & p) { cx += dx[i]; } else { cx -= dx[i]; } } px.insert({cx, cur}); } end = 1 << dysz1; for(int cur = 0; cur < end; ++cur) { // 선택된 좌표들 ll cy = 0; for(int i = 0, p = 1; i < dysz1; ++i, p <<= 1) { if (cur & p) { cy += dy[i]; } else { cy -= dy[i]; } } py.insert({cy, cur}); } // 2. 뒤에서 출발하기 end = 1 << dxsz2; bool xflag = false; int x1, x2; for(int cur = 0; cur < end; ++cur) { // 선택된 좌표들 ll cx = X; for(int i = 0, p = 1; i < dxsz2; ++i, p <<= 1) { if (cur & p) { cx -= dx[dxsz1 + i]; } else { cx += dx[dxsz1 + i]; } } if (px.find(cx) != px.end()) { xflag = true; x1 = px[cx]; x2 = cur; break; } } end = 1 << dysz2; bool yflag = false; int y1, y2; for(int cur = 0; cur < end; ++cur) { // 선택된 좌표들 ll cy = Y; for(int i = 0, p = 1; i < dysz2; ++i, p <<= 1) { if (cur & p) { cy -= dy[dysz1 + i]; } else { cy += dy[dysz1 + i]; } } if (py.find(cy) != py.end()) { yflag = true; y1 = py[cy]; y2 = cur; break; } } if (xflag && yflag) { printf("Yes\n"); // x1: 2진수, dxsz1 // x2: 2진수, dxsz2, 거꾸로 vector x, y; for(int i = 0, p = 1; i < dxsz1; ++i, p <<= 1) { if (p & x1) x.push_back(1); else x.push_back(-1); } for(int i = 0, p = 1; i < dysz1; ++i, p <<= 1) { if (p & y1) y.push_back(1); else y.push_back(-1); } for(int i = 0, p = 1; i < dxsz2; ++i, p <<= 1) { if (p & x2) x.push_back(1); else x.push_back(-1); } for(int i = 0, p = 1; i < dysz2; ++i, p <<= 1) { if (p & y2) y.push_back(1); else y.push_back(-1); } _D("X: "); for(auto& item: x) _D("%d ", item); _D("\n"); _D("Y: "); for(auto& item: y) _D("%d ", item); _D("\n"); int last = 1; string ans = ""; bool isY = true; int cy = 0, cx = 0; for(int i = 0; i < N; ++i) { if (isY) { // y if (last > 0 && y[cy] > 0) { ans += "L"; last = 1; } else if (last > 0 && y[cy] < 0) { ans += "R"; last = -1; } else if (last < 0 && y[cy] > 0) { ans += "R"; last = 1; } else if (last < 0 && y[cy] < 0) { ans += "L"; last = -1; } ++cy; isY = false; } else { // x if (last > 0 && x[cx] > 0) { ans += "R"; last = 1; } else if (last > 0 && x[cx] < 0) { ans += "L"; last = -1; } else if (last < 0 && x[cx] > 0) { ans += "L"; last = 1; } else if (last < 0 && x[cx] < 0) { ans += "R"; last = -1; } ++cx; isY = true; } } printf("%s\n", ans.c_str()); } else { printf("No\n"); } } ``` ## G - Unlock Achievement (To be Upsolved?) - 문제 링크: - Score: 625점 - 문제 예상 티어: Platinum III Editorial을 보니 유량 문제라고 한다. Upsolving을 해볼까..?