Hashing

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/24945 🧐 관찰 및 접근 # 서브태스크가 상당히 많고, 문제가 쉽지 않아보인다. 차근차근 해보자. $N = 3$ 브루트포스에 가깝게 풀 수 있을 것 같다. 문자는 어차피 최대 3개 존재하므로, 3개에 대해 $X$가 가질 수 있는 경우의 수 $3^3$가지, $Y$가 가질 수 있는 경우 $3^3$가지를 전이하면서 다익스트라로 풀 수 있을 것 같다. ㅇㅋ 된당 $S_i = a$ 모든 문자가 a라면? $X$에 들어있는 문자 개수, $Y$에 들어있는 문자 개수 두가지를 이용해서 $N^2$ 정점 다익스트라가 가능해보인다. $N \leq 30$ 이제부터 진짜로 어떻게풀어야하는지 고민해봐야할 것 같은데… 일단 복사할 문자 $Y$는 $X$의 substr이어야할 것이다. 그럼 $Y$가 될 수 있는 경우의수는 $O(N^2)$이고 $X$를 만들때든, $Y$를 만들기위해 빌드업하고 있을때든 결국 $X$도 $X$의 substr로 존재해야한다. 이것도 경우의수가 $O(N^2)$ 인 것 같다. $Y$를 붙일 수 있는지 검사하는? 그런것들이 전처리를 안하면 $O(N)$쯤 되어보이니, 아마 종합해서 $O(N^5)$정도로 풀 수 있지 않나? 근데 DP 전이식이 헷갈린다. 이게 상호 참조가 없나? 비용들이 달라서 다익으로 해야될 것 같은데. $\text{DP}[x][y]$: 현재 $X$에 $x$, $Y$에 $y$가 들어있다고 하자. $A$ 연산을 거치면 $x$에 한개가 붙고, $y$는 그대로다. $B$ 연산을 거치면 $x$가 빈 문자열이 되고, $y$는 $x$의 값으로 갱신된다. $C$연산을 거치면 $x = x + y$가 되고, $y$는 그대로다. 아하, 생각보다 $y$가 갱신될일이 없다. 그리고 $y$가 갱신된다면 $x$가 빈 문자열이 된 상태에서 시작한다! 복사하고 붙여넣는 과정을 그냥 해버렸다고 생각하는게 더 쉬울 것 같다. $\text{DP}[i][j]$ : $S_i$~$S_j$까지 만드는 최소비용이라고 하자. 이건 $\text{DP}[i][j-1]$ 후 $A$연산을 하거나 어떤 $i \leq i', j' \leq j$가 있어서 그친구를 복사한 후 붙여넣기를 여러번 하거나. 이건 그리디하게 되는듯? 한번 짜보자. 오!!! 이걸로 대충 $30^5$정도는 성공했다! $N \leq 200$ 이제 $O(N^4)$는 16억이니 빡세고, $O(N^3\log{N})$쯤 까지는 줄여야하는데… 섭태 5는 세제곱, 섭태 6은 제곱로그겠다. 음, 위에서 했던 관찰대로 $Y$에 복사해서 넣으면 $X$는 초기화돼서 시작하므로, DP를 $B$연산으로 $Y$에 복사한거까지 했을 때를 기준으로 하자. 젤 중요한거는 저 그리디하게 비교하면서 뒤로 슝슝슝 가는 파트인 것 같다. 💻 풀이 # 코드 (C++): void solve(){ cin >> N >> S >> A >> B >> C; if(N >= mxN) { cout << -1 << "\n"; return; } rep(i, 0, N+1) rep(j, 0, N+1) DP[i][j] = LLONG_MAX; rep(i, 0, N+1) rep(j, i+1, N+1) DP[i][j] = A * (j-i) + B; const mint base = 131; const mint2 base2 = 137; vector<mint> hsh(N+1), pw(N+1); vector<mint2> hsh2(N+1), pw2(N+1); hsh[0] = 0; pw[0] = 1; hsh2[0] = 0; pw2[0] = 1; rep(i, 0, N){ hsh[i+1] = hsh[i] * base + S[i]; pw[i+1] = pw[i] * base; hsh2[i+1] = hsh2[i] * base2 + S[i]; pw2[i+1] = pw2[i] * base2; } auto getHash = [&](int l, int r) -> pair<ll, ll>{ ll ret1 = (hsh[r] - hsh[l] * pw[r-l]).get(); ll ret2 = (hsh2[r] - hsh2[l] * pw2[r-l]).get(); return {ret1, ret2}; }; ll ans = N*A; rep(L, 1, N+1){ // A 연산 앞뒤에 붙여서 전이할 때 if(L >= 2) rep(s, 0, N){ if(s+L > N) break; int e = s+L; DP[s][e] = min(DP[s][e], DP[s+1][e]+A); DP[s][e] = min(DP[s][e], DP[s][e-1]+A); } // 해당 문자열을 복사하는 최소 비용 map<pair<ll,ll>, vector<int>> mp; rep(s, 0, N){ if(s+L > N) break; int e = s+L; mp[getHash(s, e)].push_back(s); } // 복사 연산으로 전이 for(auto& [_, v]: mp){ int sz = v.size(); ll mn = 1e18; for(auto s: v) mn = min(mn, DP[s][s+L]); // 다음에 갈 수 있는 위치 vector<int> nxt(sz, sz); for(int i = 0, j = 0; i < sz; i++){ while(j < sz && v[j] < v[i]+L) j++; nxt[i] = j; } rep(i, 0, sz){ int s_pos = v[i]; int cidx = i; int cnt = 0; while(cidx < sz){ cnt++; int e_pos = v[cidx]+L; if(e_pos > N) break; DP[s_pos][e_pos] = min(DP[s_pos][e_pos], mn + (C * cnt) + ((e_pos - s_pos) - (L * cnt)) * A + B); cidx = nxt[cidx]; } } } } ans = min(ans, DP[0][N] - B); cout << ans << "\n"; } 🔒 구현 코드 잠금