Problem Solving

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/32527 🧐 관찰 및 접근 # $(0, 0) \rightarrow (X, Y)$ 로 이동해야한다. 과정을 최소화할 필요는 없는데, 4000번 안쪽으로 가야한다. 일단 음.. 다음과 같은 연산들을 추가로 정의할 수 있겠다. $a$개의 $R$을 사용해서 $x$ 좌표를 $2^a - 1$ 만큼 증가시킨다. $b$개의 $U$을 사용해서 $y$ 좌표를 $2^b - 1$ 만큼 증가시킨다. 한 연산을 반복해서 사용할 수는 없다. 위 연산을 아래에서는 각각 $A, B$ 연산이라고 하겠다. 예제 1번인 $(8, 3)$은 $(7+1, 3)$로 변환하면 된다는걸 알 수 있다. 관찰을 조금 더 해야할 것 같다. $A, B$ 연산의 횟수는 최대 1회 차이날 수 있다. 번갈아가며 사용해야하므로 $A ,B$ 연산의 결과는 언제나 홀수이다. 연산은 $a, b = 1$이 아닌 이상 3개로 쪼갤 수 있다. 연산에 2개를 더하는건 쉽게 할 수 있다는 뜻 이건 직관인데, 그리디하게 가장 큰 연산을 가져가는게 될 수도 있지 않을까 싶다. 21 = 15 + 3 + 3 = 7 + 7 + 7 43 = 31 + 7 + 3 + 1 + 1 = 15 + 15 + 7 + 3 + 3 음.. 되는거같은데 흠 이걸 어떻게 증명할 수 있지? 뭔가 위에서 3개로 쪼개진다고 했듯이 31 = 15 + 15 + 1인데, 31을 안쓰면 15를 두번쓰는건 사실상 확정이고, 이때 뒤에있는 1을 훔쳐와서 두개를 줄이고 / 뒤에 1을 훔쳐오게되면서 2개가 늘어나면 또이또이고, 만약에 뒤에 1이 남아있었다면 하나 줄고 같은 느낌으로 그리디가 증명 될 것 같다. 믿고 짜볼까? 귀찮으니 PQ로 관리하자. ㅋㅋㅋㅋ X, Y에 대해 같은 로직인데 함수화하기 귀찮아서 그대로 박았더니 코드가 더럽다… 💻 풀이 # 코드 (C++): void solve(){ vector<ll> int_to_op; int_to_op.push_back(0); while(int_to_op.back() < 1e18) int_to_op.push_back(int_to_op.back()*2 + 1); map<ll, int> op_to_int; rep(i, 0, int_to_op.size()) op_to_int[int_to_op[i]] = i; ll X, Y; cin >> X >> Y; priority_queue<ll> Xpq, Ypq; while(X){ int ok = 0, ng = int_to_op.size(); while(ng - ok > 1){ int mid = (ok + ng) >> 1; if(int_to_op[mid] <= X) ok = mid; else ng = mid; } Xpq.push(ok); X -= int_to_op[ok]; } while(Y){ int ok = 0, ng = int_to_op.size(); while(ng - ok > 1){ int mid = (ok + ng) >> 1; if(int_to_op[mid] <= Y) ok = mid; else ng = mid; } Ypq.push(ok); Y -= int_to_op[ok]; } while(abs((int)Xpq.size() - (int)Ypq.size()) > 1){ if(Xpq.size() < Ypq.size()){ if(Xpq.size() == 0 || Xpq.top() == 1){ cout << "impossible"; return; } ll top = Xpq.top(); Xpq.pop(); Xpq.push(top-1); Xpq.push(top-1); Xpq.push(1); } else{ if(Ypq.size() == 0 || Ypq.top() == 1){ cout << "impossible"; return; } ll top = Ypq.top(); Ypq.pop(); Ypq.push(top-1); Ypq.push(top-1); Ypq.push(1); } } string ans = ""; if(Xpq.size() >= Ypq.size()){ while(!Xpq.empty() || !Ypq.empty()){ rep(i, 0, Xpq.top()) ans += 'R'; Xpq.pop(); if(Ypq.empty()) break; rep(i, 0, Ypq.top()) ans += 'U'; Ypq.pop(); } } else{ while(!Xpq.empty() || !Ypq.empty()){ rep(i, 0, Ypq.top()) ans += 'U'; Ypq.pop(); if(Xpq.empty()) break; rep(i, 0, Xpq.top()) ans += 'R'; Xpq.pop(); } } if(ans.size() <= 4000) cout << ans; else cout << "impossible"; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/24535 🧐 관찰 및 접근 # 점이 500개가 주어진다. 적당한 사각형 하나를 잡아서, 사각형 위에 점이 최대로 올라가게 하자. 흠, 일단 좌표압축하면 x, y좌표 각각 500개로 줄일 수 있겠다. 나이브하게 돌리면? 대충 $O(N^4)$가 되는거같은데… 2초에 $N = 500$이니까, 세제곱까지만 줄여도 어떻게 될거같긴 하다. 변 하나를 결정하는 경우의수가 $O(N^3)$개 인거같고, 그때 나머지 변 세개 최댓값을 잘 하면 되는데.. 이것도 아래서부터 잘 긁으면서 올라오면 될거같은데? 아니 50퍼에서 틀린다고?? 머지 아하 세로 한줄로 오는거 약간 걱정했었는데 역시 오류가 있었다. 이것만 고치면 되네 가로는 잘 처리 되더라 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<pii> points(N); vector<int> xs, ys; rep(i, 0, N){ int x, y; cin >> x >> y; points[i] = {x, y}; xs.push_back(x); ys.push_back(y); } sort(all(xs)); xs.erase(unique(all(xs)), xs.end()); sort(all(ys)); ys.erase(unique(all(ys)), ys.end()); rep(i, 0, N){ points[i].first = lower_bound(all(xs), points[i].first) - xs.begin(); points[i].second = lower_bound(all(ys), points[i].second) - ys.begin(); } vector<vector<bool>> isPoint(xs.size(), vector<bool>(ys.size())); for(auto [x, y] : points) isPoint[x][y] = true; int ans = 0; vector<vector<int>> DP(ys.size(), vector<int>(ys.size())); rrep(i, 0, xs.size()){ vector<vector<int>> cur_cnt(ys.size(), vector<int>(ys.size())); // cur_cnt[j][k] = j, k 사이에 있는 점의 개수 rep(j, 0, ys.size()){ if(isPoint[i][j]) cur_cnt[j][j]++; rep(k, j+1, ys.size()) cur_cnt[j][k] = cur_cnt[j][k-1] + isPoint[i][k]; } rep(j, 0, ys.size()) rep(k, j+1, ys.size()){ ans = max(ans, cur_cnt[j][k] + DP[j][k]); DP[j][k] = max(DP[j][k] + isPoint[i][j] + isPoint[i][k], cur_cnt[j][k]); } } // 세로 한줄 처리 rep(i, 0, ys.size()){ int cnt = 0; rep(j, 0, xs.size()) if(isPoint[j][i]) cnt++; ans = max(ans, cnt); } cout << ans; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/11385 🧐 관찰 및 접근 # 그냥 FFT의 정의대로, 두 다항식의 곱을 해서 계수들을 구해야한다. 그런데 값이… 너무 많이 커질 수 있다. $N, M = 1000000$, 모든 $a, b = 1000000$이라면… $f(x) \times g(x)$의 $1000000$차항의 계수는 $10^{18}$이 되는 것 같다. 이건 FFT로 하면 실수오차가 너무 심할 것 같은데… 이럴때, NTT를 여러 소수 $p_1, p_2, \cdots$에 대해서 구해두고, 중국인의 나머지 정리를 이용해 원래 계수를 복원하는 방법을 생각할 수 있겠다. CRT를 사용하면, $\text{LCM}(m_1, m_2)$ 에 대한 모듈러 값을 얻을 수 있다. $p_1 = 998244353, p_2 = 1004535809$을 사용하면 $p_1p_2 > 10^{18}$이므로, 두개면 되겠다. 💻 풀이 # 코드 (C++): void solve(){ int N, M; cin >> N >> M; N++; M++; vector<int> f(N), g(M); rep(i, 0, N) cin >> f[i]; rep(i, 0, M) cin >> g[i]; int sz = 1; while(sz < N+M) sz <<= 1; vector<mint> A1(sz), A2(sz); rep(i, 0, N) A1[i] = f[i]; rep(i, 0, M) A2[i] = g[i]; FFT::ntt(A1); FFT::ntt(A2); rep(i, 0, sz) A1[i] *= A2[i]; FFT::ntt(A1, true); vector<mint2> B1(sz), B2(sz); rep(i, 0, N) B1[i] = f[i]; rep(i, 0, M) B2[i] = g[i]; FFT::ntt(B1); FFT::ntt(B2); rep(i, 0, sz) B1[i] *= B2[i]; FFT::ntt(B1, true); ll ans = 0; rep(i, 0, N+M-1){ ll r1 = A1[i].val, r2 = B1[i].val; auto [x, m] = EGCD::CRT(MOD, r1, MOD2, r2); ans ^= x; } cout << ans; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/14958 번역 # 문제 # 가위바위보(RPS) 기계가 있으며, 이 기계는 가위, 바위, 보 중 하나를 무작위로 생성한다. 당신도 비슷한 소형 가위바위보 기계를 가지고 있다. 게임 전에, RPS 기계는 길이 $n$의 가위바위보 선택 목록을 생성하고, 당신의 기계도 길이 $m$의 선택 목록을 생성한다. 즉, RPS 기계의 전체 선택 목록과 당신의 기계의 선택 목록을 모두 알고 있다. 물론, 각 기계의 선택은 세 가지 옵션(가위, 바위, 보) 중 하나이다.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/20176 번역 # 문제 # “바늘"은 북쪽 왕국에 사는 전설적인 암살자이다. 알다시피, 바늘은 매우 가늘고 길다. 무엇보다, 치명적으로 날카롭다. 북쪽 왕국의 왕은 바늘이 수없이 찔러 자신을 죽일지도 모른다는 생각에 사로잡혀 있다. 왕은 바늘을 체포하라는 긴급 명령을 내렸다. 그리하여 바늘은 남쪽 왕국으로 탈출하기로 결심했다.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/25456 🧐 관찰 및 접근 # 0과 1로 이루어진 두 문자열 $S, T$가 주어진다. 두 문자열에 시프트 연산이 가능하다고 할때, 합성곱의 최댓값을 구하자. 합성곱이므로 FFT를 의심해볼 수 있겠다. 0과 1로 이루어진 문자열을 다항식으로 해석하면 된다. 곱 결과가 같은 차수에 올 수 있도록 한 다항식의 계수들을 뒤집고, 시프트 연산을 위해 둘중 한 배열을 두배로 늘려서 계산하자. 💻 풀이 # 코드 (C++): void solve(){ string S, T; cin >> S >> T; int N = S.size(); int sz = 1; while(sz < 3*N) sz <<= 1; vector<cd> A(sz), B(sz); rep(i, 0, N) if(S[i] == '1') A[i] = 1; rep(i, 0, N) if(S[i] == '1') A[i+N] = 1; rep(i, 0, N) if(T[i] == '1') B[N-1-i] = 1; FFT::fft(A); FFT::fft(B); rep(i, 0, sz) A[i] *= B[i]; FFT::fft(A, true); int ans = 0; rep(i, N-1, 2*N-1) ans = max(ans, (int)round(A[i].real())); // rep(i, 0, 3*N) cout << i << ' ' << A[i] << '\n'; cout << ans << '\n'; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/32453 문제 # Barbara는 정원을 가지고 있다. 정원은 길고 좁으며, 일렬로 배치된 $m$개의 동일한 크기의 구역으로 나뉘어 있다. 그녀의 친구 Babara는 생일 선물로 $n$개의 디딤돌을 주었다. Barbara는 이 디딤돌들을 정원에 배치하여 매일 디딤돌을 밟으며 즐길 수 있게 했다. $i$번째 디딤돌은 정원의 $l_i$번째부터 $r_i$번째 구역을 완전히 차지한다. 디딤돌들은 서로 겹치지 않으며, 어떤 두 디딤돌 사이에도 최소 $d$개의 빈 구역이 있다.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/5638 🧐 관찰 및 접근 # 댐에 수문이 있고, 유량과 피해비용이 있는 것 같다. 피해비용은 여는 시간에 비례하지 않는 것 같다. 그러면 각 수문에 대해, 유량에 시간을 곱해서 각 수문이 버릴 수 있는 물의 양을 구할 수 있고, 그에 따른 가격이 나온다. 이건 그리디하게는 조금 곤란하고, 배낭 문제로 되나? 했는데, $V$가 너무 크다! 그런데 수문의 개수가 $n \leq 20$으로 유의미하게 작다. 각 테스트케이스에 대해 모든 수문을 열어보는 경우의 수를 수행할 수 있을 것 같다. 시간복잡도 $O(2^n \cdot nm)$ 정도에 동작할 것 같다. 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<pll> door(N); rep(i, 0, N) cin >> door[i].first >> door[i].second; int Q; cin >> Q; rep(q, 1, Q+1){ ll V, T; cin >> V >> T; ll ans = 1e18; rep(bit, 0, 1<<N){ ll wat = 0, cost = 0; rep(i, 0, N) if(bit & (1<<i)) wat += door[i].first*T, cost += door[i].second; if(wat >= V) ans = min(ans, cost); } cout << "Case " << q << ": "; if(ans == 1e18) cout << "IMPOSSIBLE\n"; else cout << ans << '\n'; } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/1739 🧐 관찰 및 접근 # $(1, 1) \rightarrow (6, 6)$으로 가기 위해선 어때야 하지? $r_1, c_6$이 오른쪽 / 아래이거나, $c_1, r_6$이 아래 / 오른쪽이거나.. 오른쪽 / 아래를 참, 왼쪽/위를 거짓이라고 생각하면, $(r_1 \land c_6) \lor (r_6 \land c_1)$ 같은 느낌인가? 이걸 어떻게 잘 하면 2-sat으로 바꿀 수 있을것같은데.. $r6$이 아니라면, $r1, c6$이 참이어야하고, 이런 느낌으로 되는것같다. $(\neg r_6 \rightarrow r_1) \land (\neg r_6 \rightarrow c_6)$ 이런걸 4개에 대해서 하면 될거같은데? $(r_1, c_1) \rightarrow (r_2, c_2)$ 라고 해보자. 일단 $r_1 < r_2, c_1 < c_2$라고 하자. $(\neg r_1 \rightarrow r_2) \land (\neg r_1 \rightarrow c_1)$ $(\neg c_2 \rightarrow r_2) \land (\neg c_2 \rightarrow c_1)$ $(\neg r_2 \rightarrow r_1) \land (\neg r_2 \rightarrow c_2)$ $(\neg c_1 \rightarrow r_1) \land (\neg c_1 \rightarrow c_2)$ 이렇게 할 수 있을 것 같다. 그러면 $r_1 > r_2, c_1 > c_2$라면? 똑같이 $r_1, c_2$의 경로를 이용하거나, $r_2, c_1$의 경로를 이용해야하는건 같다. 그런데 왼쪽이라서 참이어야 하는게 아니라 목적지가 거짓이어야 한다. $(\neg r_1 \land \neg c_2) \lor (\neg r_2 \land \neg c_1)$ 처럼 되어야할 것 같다. 아하, 대소관계가 바뀌면 이게 낫으로 바뀐다. 이걸 이용해서 더 쉽게 구현이 될라나? 구현 실수하지 않게 조심하자. 💻 풀이 # 코드 (C++): void solve(){ int N, M, K; cin >> N >> M >> K; DirectedGraph tsat((N+M)*2); rep(i, 0, K){ int r1, c1, r2, c2; cin >> r1 >> c1 >> r2 >> c2; r1--; c1--; r2--; c2--; r1 *= 2; r2 *= 2; c1 = (c1 + N) * 2; c2 = (c2 + N) * 2; if(r1 == r2 && c1 == c2) continue; if(r1 == r2){ if(c1 < c2) tsat.add_edge(r1^1, r1); else tsat.add_edge(r1, r1^1); continue; } if(c1 == c2){ if(r1 < r2) tsat.add_edge(c1^1, c1); else tsat.add_edge(c1, c1^1); continue; } if(c1 > c2) r1^=1, r2^=1; if(r1 > r2) c1^=1, c2^=1; tsat.add_edge(c1^1, r1); tsat.add_edge(c1^1, c2); tsat.add_edge(r2^1, r1); tsat.add_edge(r2^1, c2); tsat.add_edge(r1^1, r2); tsat.add_edge(r1^1, c1); tsat.add_edge(c2^1, r2); tsat.add_edge(c2^1, c1); } cout << (tsat.is2SAT() ? "Yes\n" : "No\n"); } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/30880 🧐 관찰 및 접근 # 누가봐도 세그먼트트리 세팅인것같다. 금광같은거죠 노드 정의를 어떻게 하면 좋을까? 부분열이니까, R / O / C / K 개수는 당연히 있어야하고.. ROCK 개수는 ROCK개수 + 왼쪽 R + 오른쪽 OCK, RO + CK, ROC + K,, 아하, R / RO / ROC / ROCK / O / OC / OCK / C / CK / K 다 세면 되나? 아 그런데, ROCK의 개수를 세는게 아니라 ROCK로 끝나는 문자열의 개수를 세야한다는건, 길이도 어떻게 잘 곱해야되는것같은데 $XRRX$ 와 $XOCK$ 를 합친다고 생각해보자. 답은 $XRROCK, XROCK, XROCK, RROCK, ROCK, ROCK$로 6개인것 같다. 뒤에 $OCK$근처에서는 별 감흥이 없는 것 같고, 앞에있는 $R$들에 대해서만 상관이 있는 것 같다. 그 위치들에 대해, $2 + 4$ 해서 6이 나온 것 같다. 노드 안에서 $R$에 대해, $R$의 개수가 아니라 $R$로 끝나는 부분 문자열의 개수를 저장하는게 좋겠다. R, RO, ROC, ROCK에 대해서 그렇게 해주면 충분하다! 💻 풀이 # 코드 (C++): struct Node{ mint R = 0, RO = 0, ROC = 0, ROCK = 0, O = 0, OC = 0, OCK = 0, C = 0, CK = 0, K = 0; mint len = 0; mint ans = 0; Node(){}; Node(char c){ if(c == 'R') R += 1; if(c == 'O') O += 1; if(c == 'C') C += 1; if(c == 'K') K += 1; len = 1; }; }; Node pull(Node a, Node b){ Node ret; ret.R = a.R + mint(2).pow(a.len.val)*b.R; ret.O = a.O + b.O; ret.C = a.C + b.C; ret.K = a.K + b.K; ret.RO = a.RO + mint(2).pow(a.len.val)*b.RO + a.R*b.O; ret.OC = a.OC + b.OC + a.O*b.C; ret.CK = a.CK + b.CK + a.C*b.K; ret.ROC = a.ROC + mint(2).pow(a.len.val)*b.ROC + a.RO*b.C + a.R*b.OC; ret.OCK = a.OCK + b.OCK + a.OC*b.K + a.O*b.CK; ret.ROCK = a.ROCK + mint(2).pow(a.len.val)*b.ROCK + a.ROC*b.K + a.RO*b.CK + a.R*b.OCK; ret.len = a.len + b.len; return ret; } void solve(){ int N; cin >> N; string S; cin >> S; vector<Node> v(N); rep(i, 0, N) v[i] = Node(S[i]); SegmentTreeNode ST(N, v); int Q; cin >> Q; while(Q--){ int op; cin >> op; if(op == 1){ int idx; cin >> idx; char c; cin >> c; ST.set(idx-1, Node(c)); } else{ int l, r; cin >> l >> r; l--; r--; cout << ST.query(l, r).ROCK << '\n'; } } } 🔒 구현 코드 잠금