A. 백준 33990번 3대 512
- 단순 구현
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
using namespace std; | |
const int TARGET = 512; | |
int main() | |
{ | |
ios::sync_with_stdio(false); | |
cin.tie(0); | |
int N; | |
cin >> N; | |
int best = 1e9; | |
for (int i = 0; i < N; i++) | |
{ | |
int A, B, C; | |
cin >> A >> B >> C; | |
int sum = A + B + C; | |
if (sum >= TARGET && sum < best) | |
{ | |
best = sum; | |
} | |
} | |
if (best == 1e9) | |
{ | |
cout << -1 << "\n"; | |
} | |
else | |
{ | |
cout << best << "\n"; | |
} | |
return 0; | |
} |
B. 백준 33991번 전철 통학
- 민수가 역 i에 걸어가서 도착하는 데 걸리는 시간은 맨해튼 거리 공식에 따라 |X − X_i∣+ |Y −Y_i| 분
- 역 i의 전철은 0, Ti, 2Ti, 3Ti,…분에 도착하므로, 민수가 도착 시간 Ai분에 가장 가까우면서도 그 이후 도착하는 전철 시각 K_i는 ⌈T_i / A_i⌉ * T_i
- 세 개의 역에 대해 각각 이 값을 계산한 뒤 이 가장 빠른 탑승 시간
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <cmath> | |
#include <algorithm> | |
using namespace std; | |
long long boardingTime(long long d, long long t) | |
{ | |
if (d % t == 0) | |
{ | |
return d; | |
} | |
return (d / t + 1) * t; | |
} | |
int main() | |
{ | |
ios::sync_with_stdio(false); | |
cin.tie(0); | |
long long x1, y1, x2, y2, x3, y3; | |
cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3; | |
int Q; | |
cin >> Q; | |
while (Q--) | |
{ | |
long long x, y, t1, t2, t3; | |
cin >> x >> y >> t1 >> t2 >> t3; | |
long long d1 = llabs(x - x1) + llabs(y - y1); | |
long long d2 = llabs(x - x2) + llabs(y - y2); | |
long long d3 = llabs(x - x3) + llabs(y - y3); | |
long long result = min({ boardingTime(d1, t1), boardingTime(d2, t2), boardingTime(d3, t3) }); | |
cout << result << "\n"; | |
} | |
return 0; | |
} |
C. 백준 33992번 사막 탐험
- 두 가지 방법 중 소모 체력이 더 작은 쪽이 답
- 직접 경로: 원과 선분이 교차한다면 “전체 거리 – 원 내부 구간 길이”만큼 소모하고, 교차하지 않으면 전체 거리만큼 소모
- 오아시스 우회 경로: A에서 원 경계까지, B에서 원 경계까지 각각 최단 거리만큼 걸어서 오아시스 안으로 들어가고, 내부에서는 체력이 전혀 소모되지 않은 뒤 다시 나와 B로 이동하는 방식
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
using namespace std; | |
int main() | |
{ | |
ios::sync_with_stdio(false); | |
cin.tie(0); | |
double ax, ay, bx, by, px, py, r; | |
cin >> ax >> ay >> bx >> by >> px >> py >> r; | |
auto dist = [&](double x1, double y1, double x2, double y2) { | |
return sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2)); | |
}; | |
double dAB = dist(ax, ay, bx, by); | |
double dAP = dist(ax, ay, px, py); | |
double dBP = dist(bx, by, px, py); | |
double viaOasis = max(0.0, dAP - r) + max(0.0, dBP - r); | |
double answer = min(dAB, viaOasis); | |
cout << fixed << setprecision(10) << answer << "\n"; | |
return 0; | |
} |
D. 백준 33993번 지정좌석제
- 강의실을 R×C 크기의 2차원 그리드로 생각하고, 친구가 이미 앉은 좌표 (x_i, y_i)에는 1을, 그렇지 않은 빈 칸에는 0을 표시한 뒤 2차원 누적합 적용
- 는 그리드의 (1,1)부터 (i,j)까지 사각형 영역 내에 있는 1의 합
- 를 중심으로 한 W * W 영역은 x1 = max(1, x − k), x2 = min(R, x + k), y1 = max(1, y − k), y2=min(C, y + k)로 경계를 정할 수 있고, 이 영역 안의 친구 수는 S[x2][y2]−S[x1 − 1][y2]−S[x2][y1 − 1]+S[x1 − 1][y1−1]
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
using namespace std; | |
int main() | |
{ | |
ios::sync_with_stdio(false); | |
cin.tie(0); | |
int N, R, C, W; | |
cin >> N >> R >> C >> W; | |
int k = (W - 1) / 2; | |
vector<vector<char>> grid(R + 1, vector<char>(C + 1, 0)); | |
for (int i = 0; i < N; i++) | |
{ | |
int x, y; | |
cin >> x >> y; | |
grid[x][y] = 1; | |
} | |
vector<vector<int>> S(R + 1, vector<int>(C + 1, 0)); | |
for (int i = 1; i <= R; i++) | |
{ | |
for (int j = 1; j <= C; j++) | |
{ | |
S[i][j] = grid[i][j] + S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1]; | |
} | |
} | |
int bestCount = -1; | |
int bestX = 0, bestY = 0; | |
for (int x = 1; x <= R; x++) | |
{ | |
for (int y = 1; y <= C; y++) | |
{ | |
if (grid[x][y] == 0) | |
{ | |
int x1 = max(1, x - k); | |
int x2 = min(R, x + k); | |
int y1 = max(1, y - k); | |
int y2 = min(C, y + k); | |
int cnt = S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] + S[x1 - 1][y1 - 1]; | |
if (cnt > bestCount | |
|| (cnt == bestCount | |
&& (x < bestX || (x == bestX && y < bestY)))) | |
{ | |
bestCount = cnt; | |
bestX = x; | |
bestY = y; | |
} | |
} | |
} | |
} | |
cout << bestCount << "\n"; | |
cout << bestX << " " << bestY << "\n"; | |
return 0; | |
} |
E. 백준 33994번 Magical Trees
- N이 홀수일 때만 가능하므로, 먼저 홀짝을 판별
- 홀수인 경우에는 near-perfect matching 3개를 만든 뒤, 이들을 두 개씩 합쳐서 스패닝 트리를 구성하는 기법을 적용
- 정점 1부터 N까지 있고, 가상의 정점 (N + 1)을 하나 더 추가하여 전체를 짝수 개로 만든 뒤 원형 라운드로빈 방식의 1-factorization 알고리즘으로 3라운드 실행
- 각 라운드에서 dummy 정점과 매칭된 간선을 제외하면, 남은 (N − 1) / 2개의 간선이 near-perfect matching
- 이렇게 얻은 매칭을 M₀, M₁, M₂라 할 때, T_0 = M_1 ∪ M_2, T_1 = M_0 ∪ M_2, T_2 = M_0 ∪ M_1로 정의하면, 각 T_i는 간선 개수 N − 1개로 스패닝 트리 조건 (연결+무사이클)을 만족하고 동일한 간선은 정확히 두 트리에 속하게 됨
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
#include <algorithm> | |
using namespace std; | |
int main() | |
{ | |
ios::sync_with_stdio(false); | |
cin.tie(0); | |
int N; | |
cin >> N; | |
if (N % 2 == 0) | |
{ | |
cout << "No\n"; | |
return 0; | |
} | |
cout << "Yes\n"; | |
int Np = N + 1; | |
int dummy = Np; | |
vector<int> players(Np); | |
for (int i = 0; i < Np; i++) | |
{ | |
players[i] = i + 1; | |
} | |
vector<vector<pair<int, int>>> M(3); | |
for (int r = 0; r < 3; r++) | |
{ | |
for (int i = 0; i < Np / 2; i++) | |
{ | |
int u = players[i]; | |
int v = players[Np - 1 - i]; | |
if (u == dummy || v == dummy) | |
{ | |
continue; | |
} | |
if (u > v) | |
{ | |
swap(u, v); | |
} | |
M[r].emplace_back(u, v); | |
} | |
int tmp = players[Np - 1]; | |
for (int i = Np - 1; i > 1; i--) | |
{ | |
players[i] = players[i - 1]; | |
} | |
players[1] = tmp; | |
} | |
vector<vector<pair<int, int>>> T(3); | |
for (auto e : M[1]) | |
{ | |
T[0].push_back(e); | |
} | |
for (auto e : M[2]) | |
{ | |
T[0].push_back(e); | |
} | |
for (auto e : M[0]) | |
{ | |
T[1].push_back(e); | |
} | |
for (auto e : M[2]) | |
{ | |
T[1].push_back(e); | |
} | |
for (auto e : M[0]) | |
{ | |
T[2].push_back(e); | |
} | |
for (auto e : M[1]) | |
{ | |
T[2].push_back(e); | |
} | |
for (int t = 0; t < 3; t++) | |
{ | |
for (auto e : T[t]) | |
{ | |
cout << e.first << ' ' << e.second << "\n"; | |
} | |
} | |
return 0; | |
} |
F. 백준 34000번 취향 변화
- 주어진 수열에서 각 물건에 대해 좋아하면 +1, 싫어하면 –1의 값을 부여하여 C_1, C_2, …, C_n 이라는 +1, -1 시퀀스를 얻음
- dong_gas가 왼쪽에서부터 k개를 가져갈 때의 행복도 S(k) = C_1 + ... + C_k
- shandy5833은 나머지로 전체 - S(k)
- 두 사람 행복도의 곱 f(k) = S(k) * (전체 −S(k))로 S(k)가 T / 2에 가까울수록 커짐
- C_i는 1 혹은 -1이고 0에서 출발해 T에 이르는 과정에서 중간의 모든 정수 값을 반드시 한 번 이상 통과한다는 성질에 따라 S(k) = ⌊T / 2⌋ 혹은 ⌈T / 2⌉를 만족하는 k가 항상 존재함을 알 수 있음
- 따라서 가능한 최대 행복도 곱은 s가 ⌊T / 2⌋, ⌈T / 2⌉일 때 T^2 / 4
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
using namespace std; | |
int main() | |
{ | |
ios::sync_with_stdio(false); | |
cin.tie(0); | |
int N, Q; | |
cin >> N >> Q; | |
vector<int> a(N + 1); | |
for (int i = 1; i <= N; i++) | |
{ | |
cin >> a[i]; | |
} | |
vector<int> typeSign(N + 1); | |
for (int t = 1; t <= N; t++) | |
{ | |
int b; | |
cin >> b; | |
typeSign[t] = (b == 1 ? 1 : -1); | |
} | |
vector<int> count(N + 1, 0); | |
for (int i = 1; i <= N; i++) | |
{ | |
count[a[i]]++; | |
} | |
long long totalHappiness = 0; | |
for (int t = 1; t <= N; t++) | |
{ | |
totalHappiness += 1LL * count[t] * typeSign[t]; | |
} | |
while (Q--) | |
{ | |
int type; | |
cin >> type; | |
if (type == 1) | |
{ | |
int i, j; | |
cin >> i >> j; | |
int oldType = a[i]; | |
int newType = j; | |
if (oldType != newType) | |
{ | |
int oldSign = typeSign[oldType]; | |
int newSign = typeSign[newType]; | |
totalHappiness += (newSign - oldSign); | |
count[oldType]--; | |
count[newType]++; | |
a[i] = newType; | |
} | |
} | |
else | |
{ | |
int t; | |
cin >> t; | |
int oldSign = typeSign[t]; | |
int cnt = count[t]; | |
totalHappiness -= 2LL * oldSign * cnt; | |
typeSign[t] = -oldSign; | |
} | |
long long T = totalHappiness; | |
long long answer = (T * T) / 4; | |
cout << answer << '\n'; | |
} | |
return 0; | |
} |
G. 백준 33995번 LCS Making
- S에 빠진 글자가 하나라도 있을 경우 빠진 글자를 T의 글자로 마음껏 사용할 수 있음
- S에 빠진 글자는 LCS에 기여 X
- 따라서 원하는 K만큼만 S에 실제로 등장하는 어떤 문자로 매칭시키고 나머지 (N – K) 자리를 모두 빠진 문자로 채우면 정확히 LCS 길이 K를 만들 수 있음
- S가 알파벳 26글자를 전부 포함하는 경우에는 빠진 글자가 존재하지 않음
- 이때는 T에 어느 글자를 넣더라도 S에 해당 글짜가 최소 한 번 이상 나타나므로 LCS는 최소값 f_min 이상이 됨 (여기서 f_min은 S에 등장하는 26개 문자 중 가장 적게 등장한 문자의 빈도)
- 최소 LCS 길이 = f_min
- 최대 LCS 길이는 T = S일 때이므로 N
- 최종 판정 조건은 다음과 같음
- S가 26글자 전부를 포함하지 않는다면, K가 1 이상 N 이하일 때 항상 가능 → 출력 1
- S가 26글자를 전부 포함한다면, K가 f_min <= K <= N인 경우에만 가능 → K >= f_min이면 1, 그렇지 않으면 0
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <string> | |
#include <algorithm> | |
using namespace std; | |
int main() | |
{ | |
std::ios::sync_with_stdio(false); | |
std::cin.tie(0); | |
int N, K; | |
cin >> N >> K; | |
string s; | |
cin >> s; | |
int freq[26] = { 0 }; | |
for (char c : s) | |
{ | |
freq[c - 'a']++; | |
} | |
int uniqueCount = 0; | |
for (int i = 0; i < 26; i++) | |
{ | |
if (freq[i] > 0) | |
{ | |
uniqueCount++; | |
} | |
} | |
if (uniqueCount < 26) | |
{ | |
cout << 1 << "\n"; | |
} | |
else | |
{ | |
int minFreq = freq[0]; | |
for (int i = 1; i < 26; i++) | |
{ | |
minFreq = min(minFreq, freq[i]); | |
} | |
cout << (K >= minFreq ? 1 : 0) << "\n"; | |
} | |
return 0; | |
} |
H. 백준 33996번 점진적인 수열
- 점진적인 수열이란 길이가 3 이상인 수열 A_1, A_2, …, A_k에 대해 diff_j = A_(j+1) − A_j라 할 때, 모든 j = 1, 2, …, k−2에 대하여 diff_(j+1) ∈ { diff_j − 1, diff_j, diff_j + 1}를 만족하는 것
- 각 위치 j에 대해, 앞선 모든 위치 k < j와의 차이 S_j - S_k를 계산하여 정렬된 리스트 diffList[j]에 저장
- 해당 리스트를 이용하면 이후 특정 차이값을 이분 탐색으로 찾아낼 수 있음
- “끝나는 위치와 그전 위치 사이의 차이”를 기준으로 같은 종류의 부분 수열을 한데 모아 두고, 그 묶음에 대해 몇 개나 있는지와 그들의 길이를 모두 더한 값을 기록
- diffList[i]: k < i인 모든 k에 대해 S_i - S_k를 모아 정렬해 둔 목록
- cntList[i][idx]: 차이 diffList[i][idx]를 가진 부분 수열의 개수
- lenList[i][idx]: 위 부분 수열들의 길이 합
- 각 쌍 (i, j)에 대하여,
- (S_j − S_i)에 대해, diffList[i]에서 {S_j − S_i - 1, S_j − S_i, S_j − S_i + 1}을 이분 탐색으로 찾아 집계된 (cnt, len)을 꺼내고 newCnt = 1 + ∑cnt, newLen = 2 + ∑(len + cnt)으로 갱신
- 길이 3 이상이 된 부분 수열에서 늘어난 길이 합 ∑(len + cnt)을 정답에 누적
- 마지막으로 cntList[j]와 lenList[j]의 (S_j − S_i) 위치를 newCnt, newLen으로 업데이트
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
#include <algorithm> | |
using namespace std; | |
const int MOD = 1e9 + 7; | |
int main() | |
{ | |
ios::sync_with_stdio(false); | |
cin.tie(0); | |
int N; | |
cin >> N; | |
vector<long long> seq(N); | |
for (int i = 0; i < N; i++) | |
{ | |
cin >> seq[i]; | |
} | |
vector<vector<int>> diffList(N); | |
for (int i = 0; i < N; i++) | |
{ | |
for (int j = 0; j < i; j++) | |
{ | |
diffList[i].push_back(int(seq[i] - seq[j])); | |
} | |
sort(diffList[i].begin(), diffList[i].end()); | |
} | |
vector<vector<int>> cntList(N), lenList(N); | |
for (int i = 0; i < N; i++) | |
{ | |
int sz = diffList[i].size(); | |
cntList[i].assign(sz, 0); | |
lenList[i].assign(sz, 0); | |
} | |
long long answer = 0; | |
for (int i = 0; i < N; i++) | |
{ | |
auto& curDiff = diffList[i]; | |
auto& curCnt = cntList[i]; | |
auto& curLen = lenList[i]; | |
for (int j = i + 1; j < N; j++) | |
{ | |
int delta = int(seq[j] - seq[i]); | |
int aggCnt = 0, aggLen = 0; | |
for (int k = -1; k <= 1; k++) | |
{ | |
int target = delta + k; | |
auto it = lower_bound(curDiff.begin(), curDiff.end(), target); | |
if (it != curDiff.end() && *it == target) | |
{ | |
int idx = int(it - curDiff.begin()); | |
aggCnt = (aggCnt + curCnt[idx]) % MOD; | |
aggLen = (aggLen + curLen[idx]) % MOD; | |
} | |
} | |
int newCnt = aggCnt + 1; | |
if (newCnt >= MOD) | |
{ | |
newCnt -= MOD; | |
} | |
int newLen = (aggLen + aggCnt) % MOD; | |
newLen = (newLen + 2) % MOD; | |
int addValue = (aggLen + aggCnt) % MOD; | |
answer = (answer + addValue) % MOD; | |
auto& nextDiff = diffList[j]; | |
auto& nextCnt = cntList[j]; | |
auto& nextLen = lenList[j]; | |
int idx2 = int(lower_bound(nextDiff.begin(), nextDiff.end(), delta) - nextDiff.begin()); | |
nextCnt[idx2] = (nextCnt[idx2] + newCnt) % MOD; | |
nextLen[idx2] = (nextLen[idx2] + newLen) % MOD; | |
} | |
} | |
cout << answer << "\n"; | |
return 0; | |
} |
I. 백준 33997번 광부가 될 수 있다면
- 각 행 간 이동은 “한 칸만 아래로 내려간 후 그 행에서 좌우로 자유롭게 이동”하는 과정
- 같은 행에서 열 k에서 열 j로 이동하며 얻는 값은 구간 합으로 간단히 표현할 수 있지만, 모든 쌍을 직접 계산하면 O(N^2)이 되어 시간 초과가 발생
- 구간 합을 최적화하기 위해 “구간 최소값”과 “구간 최대값”을 미리 구해 두고, DP를 활용하면 각 행을 O(N)에 처리 가능
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
#include <algorithm> | |
#include <limits> | |
using namespace std; | |
int main() | |
{ | |
ios::sync_with_stdio(false); | |
cin.tie(0); | |
int N, M; | |
cin >> N >> M; | |
vector<long long> dpPrev(M, 0), dpCur(M); | |
vector<long long> rowValues(M); | |
vector<long long> prefixSum(M + 1); | |
vector<long long> leftMin(M), rightMax(M); | |
vector<long long> prefixMaxU(M), suffixMaxV(M); | |
for (int i = 0; i < N; i++) | |
{ | |
for (int j = 0; j < M; j++) | |
{ | |
cin >> rowValues[j]; | |
} | |
prefixSum[0] = 0; | |
for (int j = 0; j < M; j++) | |
{ | |
prefixSum[j + 1] = prefixSum[j] + rowValues[j]; | |
} | |
leftMin[0] = prefixSum[0]; | |
for (int j = 1; j < M; j++) | |
{ | |
leftMin[j] = min(leftMin[j - 1], prefixSum[j]); | |
} | |
rightMax[M - 1] = prefixSum[M]; | |
for (int j = M - 2; j >= 0; j--) | |
{ | |
rightMax[j] = max(rightMax[j + 1], prefixSum[j + 1]); | |
} | |
for (int j = 0; j < M; j++) | |
{ | |
long long uVal = dpPrev[j] - leftMin[j]; | |
if (j == 0) | |
{ | |
prefixMaxU[j] = uVal; | |
} | |
else | |
{ | |
prefixMaxU[j] = max(prefixMaxU[j - 1], uVal); | |
} | |
} | |
for (int j = M - 1; j >= 0; j--) | |
{ | |
long long vVal = dpPrev[j] + rightMax[j]; | |
if (j == M - 1) | |
{ | |
suffixMaxV[j] = vVal; | |
} | |
else | |
{ | |
suffixMaxV[j] = max(suffixMaxV[j + 1], vVal); | |
} | |
} | |
for (int j = 0; j < M; j++) | |
{ | |
long long candA = prefixMaxU[j] + rightMax[j]; | |
long long candB = suffixMaxV[j] - leftMin[j]; | |
dpCur[j] = max(candA, candB); | |
} | |
dpPrev.swap(dpCur); | |
} | |
long long answer = *max_element(dpPrev.begin(), dpPrev.end()); | |
cout << answer << "\n"; | |
return 0; | |
} |
J. 백준 33998번 거의 같은 문자열
에디토리얼 해설 + gpt 합작품
- 모든 쿼리를 그 길이에 따라 queriesByLength 맵에 저장
- 원본 문자열 S에 대해 26글자의 문자별 누적 빈도 prefixCounts[i][c]를 미리 계산
- 구간일 때, 각 문자 의 개수는prefixCounts[pos + L][c] − prefixCounts[pos][c]
- 각 쿼리 문자열에 대해 26차원 벡터 형태의 서명을 만들고, unordered_map으로 고유 ID를 부여
- S에서 길이 인 모든 윈도우를 순회하며 앞서 만든 서명과 비교
- 일치하는 서명이 존재하면 해당 ID의 카운터를 증가
- 각 쿼리에 대응하는 ID의 집계 값을 정답 배열에 채워 출력
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
#include <string> | |
#include <unordered_map> | |
#include <array> | |
using namespace std; | |
struct signature | |
{ | |
array<int, 26> a; | |
bool operator==(signature const& other) const | |
{ | |
return a == other.a; | |
} | |
}; | |
struct signatureHash | |
{ | |
size_t operator()(signature const& sig) const noexcept | |
{ | |
size_t h = 0; | |
for (int c = 0; c < 26; c++) | |
{ | |
h = h * 1000003 + sig.a[c]; | |
} | |
return h; | |
} | |
}; | |
int main() | |
{ | |
ios::sync_with_stdio(false); | |
cin.tie(0); | |
int N, M; | |
cin >> N >> M; | |
string s; | |
cin >> s; | |
vector<string> queries(M); | |
for (int i = 0; i < M; i++) | |
{ | |
cin >> queries[i]; | |
} | |
unordered_map<int, vector<int>> queriesByLength; | |
for (int i = 0; i < M; i++) | |
{ | |
queriesByLength[queries[i].size()].push_back(i); | |
} | |
vector<array<int, 26>> prefixCounts(N + 1); | |
for (int c = 0; c < 26; c++) | |
{ | |
prefixCounts[0][c] = 0; | |
} | |
for (int i = 0; i < N; i++) | |
{ | |
prefixCounts[i + 1] = prefixCounts[i]; | |
prefixCounts[i + 1][s[i] - 'a']++; | |
} | |
vector<long long> answer(M, 0); | |
for (auto& entry : queriesByLength) | |
{ | |
int len = entry.first; | |
auto& indices = entry.second; | |
if (len > N) | |
{ | |
continue; | |
} | |
unordered_map<signature, int, signatureHash> signatureToId; | |
signatureToId.reserve(indices.size() * 2); | |
vector<int> signatureIdForQuery(indices.size()); | |
int idCount = 0; | |
for (int j = 0; j < (int)indices.size(); j++) | |
{ | |
signature querySignature; | |
querySignature.a.fill(0); | |
for (char ch : queries[indices[j]]) | |
{ | |
querySignature.a[ch - 'a']++; | |
} | |
auto it = signatureToId.find(querySignature); | |
if (it == signatureToId.end()) | |
{ | |
signatureToId[querySignature] = idCount; | |
signatureIdForQuery[j] = idCount; | |
++idCount; | |
} | |
else | |
{ | |
signatureIdForQuery[j] = it->second; | |
} | |
} | |
vector<long long> countForSignature(idCount, 0); | |
signature windowSignature; | |
for (int pos = 0; pos + len <= N; pos++) | |
{ | |
for (int c = 0; c < 26; c++) | |
{ | |
windowSignature.a[c] = prefixCounts[pos + len][c] - prefixCounts[pos][c]; | |
} | |
auto it = signatureToId.find(windowSignature); | |
if (it != signatureToId.end()) | |
{ | |
++countForSignature[it->second]; | |
} | |
} | |
for (int j = 0; j < (int)indices.size(); j++) | |
{ | |
answer[indices[j]] = countForSignature[signatureIdForQuery[j]]; | |
} | |
} | |
for (auto val : answer) | |
{ | |
cout << val << '\n'; | |
} | |
return 0; | |
} |
개발환경:Visual Studio 2022
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
백준 Hello, AlKon! 2025 (0) | 2025.05.17 |
---|---|
백준 2025 중앙대학교 프로그래밍 경진대회 (1) | 2025.04.13 |
백준 월간 향유회 2025. 01. (0) | 2025.02.02 |
백준 7469번 K번째 수 (1) | 2025.01.18 |
백준 1017번 소수 쌍 (0) | 2024.10.30 |