AGC001
B - 신비한 빛
문제에서 설명하는 그림을 통해, 빛에 의해 형성된 첫 번째 큰 삼각형의 변의 길이는 \(x\), 다음에 형성되는 작은 삼각형의 변의 길이는 \( (n-2x) \)로 관찰됩니다.
분할 정복 접근법으로, 각 단계에서 큰 삼각형의 변 길이를 \( n \), 현재 삼각형의 변 길이를 \( x \)로 설정하면 다음 삼각형의 변 길이는 \( (n - 2x) \)로 계산됩니다. 이는 두 수의 차이로 계산되는데, 이 과정은 변형된 유클리드 알고리즘(Modified Euclidean Algorithm)과 동일합니다:
여기서 붉은 경로의 길이는 정답으로 나타나며, 최종적으로 남는 작은 조각의 변 길이는 유클리드 알고리즘의 원리를 따르므로 \( gcd(n - x, x) = gcd(n, x) \)이며, 평행 이동을 통해 붉은 경로의 길이는 \( n - gcd(n, x) \)임을 알 수 있습니다. 따라서 최종 정답은 \( 3(n - gcd(n, x)) \) 입니다.
#include <cstdio>
#include <algorithm>
#define lint long long
using namespace std;
lint 전체길이, 시작값, 임시변수;
int main() {
scanf("%lld%lld", &전체길이, &시작값);
임시변수 = __gcd(전체길이, 시작값);
printf("%lld", 3 * (전체길이 - 임시변수));
}
AGC002
C - 매듭 퍼즐
연속된 두 밧줄의 길이 합이 \( L \) 이상인 구간을 기준으로 설정하고, 앞쪽(뒤쪽) 밧줄들을 차례로 연결해 나가면서 마지막에 기준 구간을 분리하는 방식으로 모든 밧줄을 제거할 수 있습니다.
만약 연속된 밧줄 조합 중 길이 합이 \( L \) 이상인 것이 없다면, Impossible을 출력합니다.
#include <cstdio>
using namespace std;
int 밧줄개수, 최소길이, 밧줄길이[100005];
inline int ReadInt() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
int main() {
밧줄개수 = ReadInt(), 최소길이 = ReadInt();
for (int i = 1; i <= 밧줄개수; i++) 밧줄길이[i] = ReadInt();
for (int i = 1; i < 밧줄개수; i++) {
if (밧줄길이[i] + 밧줄길이[i + 1] >= 최소길이) {
printf("가능\n");
for (int j = 1; j < i; j++) printf("%d\n", j);
for (int j = 밧줄개수; j > i + 1; j--) printf("%d\n", j - 1);
printf("%d", i);
return 0;
}
}
printf("불가능");
}
AGC003
B - 간단 마작
각 카드는 자기 자신 및 인접한 카드와 짝을 이룰 수 있습니다. 자체 짝을 우선 형성하는 것이 이후 조합 구성에 영향을 최소화하므로, 먼저 각 카드에 대해 \( ans \leftarrow ans + \frac{a_i}{2} \) 및 \( a_i \leftarrow a_i \mod 2 \)로 처리합니다. 이후 남은 \( a_i = 1 \)인 경우 다음 카드와 짝을 이루며, 다음 카드의 수량을 하나 줄이고 답변을 더합니다.
#include <cstdio>
#define lint long long
using namespace std;
int n;
lint 답, 카드수[100005];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &카드수[i]);
for (int i = 1; i <= n; i++) {
if (카드수[i]) {
답 += 카드수[i] / 2, 카드수[i] %= 2;
if (카드수[i] && 카드수[i + 1]) 카드수[i]--, 카드수[i + 1]--, 답++;
}
}
printf("%lld", 답);
}
C - BBuBBBlesort!
먼저 유용한 속성 탐색: 연산 2만 사용할 경우 모든 숫자의 위치 홀짝성은 변하지 않습니다. 따라서 각 숫자가 원본 배열에서 위치 \(i\) 정렬된 위치 \(j\)일 때 \( (i \text{ 홀짝}) \oplus (j \text{ 홀짝}) \)이 참인 경우, 최소 한 번의 연산 1이 필요함을 의미합니다.
홀짝성 변경은 한 번의 연산 1로 최대 두 숫자의 상태를 변경할 수 있습니다. 정답은 다음과 같습니다: [ \sum_{i=1}^{n} [(i & 1) \oplus (id(i) & 1)] ] 여기서 \( id(i) \)는 정렬된 위치이며, 시간 복잡도는 \( \Theta(n \log_2 n) \)입니다.
#include <cstdio>
#include <algorithm>
using namespace std;
struct Node {
int 값, 원본위치;
bool operator<(const Node &A) const { return 값 < A.값; }
};
int n, 답;
Node 배열[100005];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &배열[i].값), 배열[i].원본위치 = i;
sort(배열 + 1, 배열 + n + 1);
for (int i = 1; i <= n; i++)
답 += ((i & 1) ^ (배열[i].원본위치 & 1));
printf("%d", 답 >> 1);
}
AGC004
C - AND 그리드
경계가 채워지지 않는다는 조건을 활용하여 첫 번째 격자는 왼쪽 경계를, 두 번째 격자는 오른쪽 경계를 채웁니다. 이는 연결성과 주어진 격자의 중첩 영역을 충족시킵니다.
#include <cstdio>
using namespace std;
int 행, 열;
bool 격자[505][505];
inline char GetChar() {
char ch = getchar();
while (ch != '.' && ch != '#') ch = getchar();
return ch;
}
int main() {
scanf("%d%d", &행, &열);
for (int i = 1; i <= 행; i++)
for (int j = 1; j <= 열; j++)
격자[i][j] = getchar() == '#';
for (int i = 1; i <= 행; i++) {
putchar('#');
for (int j = 2; j < 열; j++)
putchar((i % 2 || 격자[i][j]) ? '#' : '.');
putchar('.'), putchar('\n');
}
putchar('\n');
for (int i = 1; i <= 행; i++) {
putchar('.');
for (int j = 2; j < 열; j++)
putchar((!(i % 2) || 격자[i][j]) ? '#' : '.');
putchar('#'), putchar('\n');
}
}
D - 순간이동장치
노드 1에 자체 루프를 필수로 추가해야 합니다. 깊이 \( \ge K \)인 노드들은 주의 깊게 처리해야 하며, 깊이 \( \geq K \)인 노드들에 대해 깊이 제약 해결 알고리즘을 적용합니다.
탐색 전략: 현재 노드 \( u \)에서 가장 깊은 후손 깊이를 \( maxdeep \) 추적. \( maxdeep - deep(u) + 1 = K \)일 때 노드 \( u \)를 노드 1에 연결하는 것이 최적입니다.
#include <cstdio>
using namespace std;
struct Edge { int to, next; };
int n, k, 답;
int 총간선수, 부모[100005], 헤드[100005];
Edge 간선[100005];
inline signed read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
inline void 연결(int u, int v) {
간선[++총간선수] = (Edge){v, 헤드[u]};
헤드[u] = 총간선수;
}
inline int DFS(int u, int 깊이) {
int 최대깊이 = 깊이;
for (int i = 헤드[u]; i; i = 간선[i].next)
최대깊이 = max(최대깊이, DFS(간선[i].to, 깊이 + 1));
if (부모[u] != 1 && 최대깊이 - 깊이 + 1 == k) 답++, 0;
return 최대깊이;
}
int main() {
n = read(), k = read();
for (int i = 1; i <= n; i++) 부모[i] = read();
if (부모[1] != 1) 부모[1] = 1, 답++;
for (int i = 2; i <= n; i++) 연결(부모[i], i);
DFS(1, 0);
printf("%d", 답);
}
AGC005
B - 최소 합
각 \( a_i \)가 구간 \( [l_i, r_i] \)의 최소값일 때의 기하적 해석: 두 인덱스 쌍 \( (i - l_i) \)과 \( (r_i - i) \)의 곱으로 기여도 계산. 단조 스택을 사용해 \( l_i, r_i \) 구하고 정답 공식 적용: [ \sum_{i=1}^N a_i (i - l_i) (r_i - i) ] 시간 복잡도 \( \Theta(n) \)입니다.
#include <cstdio>
#include <algorithm>
#define lint long long
using namespace std;
int n, l[200005], r[200005];
lint 답, 배열[200005];
int top, 스택[200005];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) r[i] = n + 1;
for (int i = 1; i <= n; i++) {
while (top && 배열[스택[top]] > 배열[i])
r[스택[top--]] = i;
l[i] = 스택[top], 스택[++top] = i;
}
for (int i = 1; i <= n; i++)
답 += 1ll * (i - l[i]) * (r[i] - i) * 배열[i];
printf("%lld", 답);
}
AGC006
B - 평균 피라미드 쉬움
구성 핵심: \( n=2 \)의 \( X \)를 기준으로 트리 구조 확장. \( n \)차원 초입방체 구조를 활용한 패턴화.
특히 \( A_{n,n-1} < A_{n,n} < A_{n,n+1} \)을 보장하는 경우, 최상위 수가 \( A_{n,n} \)이 됨. \( X = 1 \) 또는 \( X = 2n-1 \)일 때는 예외 처리합니다.
#include <cstdio>
using namespace std;
int n, x;
int main() {
scanf("%d%d", &n, &x);
if (x == 1 || x == (n << 1) - 1) return puts("아니오"), 0;
puts("예");
for (int i = 1, now = 1; i <= (n << 1) - 1; i++) {
while (now >= x - 1 && now <= x + 1) now++;
if (i >= n - 1 && i <= n + 1) printf("%d\n", x - n + i);
else printf("%d\n", now), now++;
}
}
AGC007
A - Shik와 돌
걸음 수 \( = n + m - 1 \) 공식 활용. '#' 갯수가 이 값과 일치하면 성공.
#include <cstdio>
using namespace std;
int n, m, total;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
char s[505]; scanf("%s", s + 1);
for (int j = 1; j <= m; j++) if (s[j] == '#') total++;
}
puts((total == n + m - 1) ? "예" : "아니오");
}
B - 수열 구성
조건 충족을 위한 두 수열 분리 전략: \( S = 30000 \) 기준 설정. \( a_i = \delta \times i \), \( b_i = \delta \times (n - i) \) 초기화하고 \( X \) 기준 조정.
#include <cstdio>
using namespace std;
int n, 배열A[200005], 배열B[200005];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) 배열A[i] = 2e4 * i, 배열B[i] = 2e4 * (n - i) + 1;
for (int j = 1; j <= n; j++) {
int pos; scanf("%d", &pos);
배열A[pos] += j - 1;
}
for (int j = 1; j <= n; j++) printf("%d ", 배열A[j]);
putchar('\n');
for (int j = 1; j <= n; j++) printf("%d ", 배열B[j]);
}
AGC008
A - 간단 계산기
기호와 영점 기반 분기 처리:
- \( x = y \): 연산 불필요
- \( x=0 \) 또는 \( y=0 \): 조건별 \( z \) 처리
- 부호 동일: \( x<y \)와 크기에 따른 최소 연산 계산
- 부호 반대: 한 회 반전 필수
#include <cstdio>
#include <cmath>
using namespace std;
int x,y,z;
int main() {
scanf("%d%d", &x, &y);
z = abs(x - y);
if (x == y) return printf("0"), 0;
if (!(x && y)) return printf("%d", (x > y) ? (z + 1) : (z)), 0;
if ((x > 0 && y > 0) || (x < 0 && y < 0)) return printf("%d", (x < y) ? (z) : (z + 2)), 0;
return printf("%d", abs(x + y) + 1), 0;
}
B - 연속 도색
누적합을 활용한 최적화: 양수 값만 가산하여 계산하되 부분 구간 분할 관리.
#include <cstdio>
#include <algorithm>
#define lint long long
using namespace std;
int n, k;
lint ans, a[100005], pred[2][100005];
int main() {
scanf("%d%d%d", &n, &k);
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
for (int i = 1; i <= n; i++) {
pred[0][i] = pred[0][i - 1] + max(a[i], 0ll);
pred[1][i] = pred[1][i - 1] + a[i];
}
for (int i = 1; i <= n - k + 1; i++) {
ans = max(ans, pred[0][n] - (pred[0][i + k - 1] - pred[0][i - 1]) + max(pred[1][i + k - 1] - pred[1][i - 1], 0ll));
}
printf("%lld", ans);
}
D - K번째 K
그리디 구성:
- \( p_i \) 위치에 \( i \) 입력
- 앞쪽부터 \( i \) 개수 충족을 우선 수행
- \( p_i \) 기준 좌우 이동 규칙 확립
#include <cstdio>
#include <algorithm>
using namespace std;
int n, now, a[505], pos[505], ans[250005];
inline int Read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
inline bool cmp(const int A, const int B) { return a[A] < a[B]; }
int main() {
n = Read();
for (int i = 1; i <= n; i++) a[i] = Read(), pos[i] = ans[a[i]] = i;
sort(pos + 1, pos + n + 1, cmp);
for (int i = 1; i <= n; i++) {
for (int j = 1; j < pos[i]; j++) {
now++;
while (ans[now]) now++;
ans[now] = pos[i];
if (now > a[pos[i]]) return puts("아니오"), 0;
}
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n - pos[i]; j++) {
now++;
while (ans[now]) now++;
ans[now] = pos[i];
if (now < a[pos[i]]) return puts("아니오"), 0;
}
puts("예");
for (int i = 1; i <= n * n; i++) printf("%d ", ans[i]);
}
AGC009
A - 중복 배열
역순 처리 전략: 현재값 \( (a_i + x) \)에서 \( b_i \) 배수 만들기 위한 연산 횟수 \( y \) 계산하여 누적.
#include <cstdio>
#define lint long long
using namespace std;
int n;
lint ans, now, a[100005], b[100005];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%lld%lld", &a[i], &b[i]);
for (int i = n; i >= 1; i--) {
if ((a[i] + now) % b[i]) {
lint tmp = b[i] - (a[i] + now) % b[i];
ans += tmp, now += tmp;
}
}
printf("%lld", ans);
}
AGC010
A - 합산
홀수 개수 판별: 두 홀수 합은 짝수이므로 홀수 개수의 총합은 홀수 개수의 기우성으로 계산.
#include <cstdio>
using namespace std;
int n, cnt;
int main() {
scanf("%d", &n);
for (int i = 1, tmp; i <= n; i++)
scanf("%d", &tmp), cnt += tmp % 2;
printf((cnt % 2) ? "아니오" : "예");
}
AGC011
A - 공항 버스
활동 선택 문제 변형: 각 점을 처리 가능 시간 간격으로 추상화, 시간별로 처리 최적화.
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, k, ans, a[100005];
int main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
sort(a + 1, a + n + 1);
for (int i = 1, cnt = 0, last = 0; i <= n; i++) {
if (a[i] > last + m) cnt = 0, last = a[i];
cnt++;
if (cnt == k) cnt = 0, ans++;
}
printf("%d", ans);
}
B - 다채로운 생물
정렬 후 누적 합 기반 조건 판별: \( \sum_{j=1}^i (a_j \times 2) \geq a_{i+1} \) 여부로 생성 가능성 결정.
#include <cstdio>
#include <algorithm>
#define lint long long
using namespace std;
int n, ans;
lint a[100005];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
sort(a + 1, a + n + 1);
for (int i = 1; i < n; i++) {
a[i] += a[i - 1], ans++;
if (a[i] << 1 < a[i + 1]) ans = 0;
}
printf("%d", ans);
}
AGC012
A - 그룹 콘테스트
정렬 및 간격 선택: 매 세 번째 값 선택하여 최대값 집계.
#include <cstdio>
#include <algorithm>
#define lint long long
using namespace std;
int n;
lint ans, a[300005];
int main() {
scanf("%d", &n); n *= 3;
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
sort(a + 1, a + n + 1);
for (int i = n - 1; i >= n / 3 + 1; i -= 2) ans += a[i];
printf("%lld", ans);
}
AGC013
B - 해밀턴 경로
단순 연결 그래프 기반 BFS/DFS: 시작점에서 탐색하며 연결 가능 노드 추적.
#include <queue>
#include <cstdio>
using namespace std;
struct Edge { int to, next; };
int n, m;
deque<int> ans;
int total = 0, head[100005];
bool visit[100005];
Edge edge[200005];
inline int Read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
inline void Link(int u, int v) {
edge[++total] = (Edge){v, head[u]};
head[u] = total;
}
inline void DFS(int type, int u) {
visit[u] = true;
if (type == 1) ans.push_back(u);
if (type == 2 && u != 1) ans.push_front(u);
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].to;
if (!visit[v]) {
DFS(type, v);
break;
}
}
}
int main() {
n = Read(), m = Read();
for (int i = 1, u, v; i <= m; i++) {
u = Read(), v = Read();
Link(u, v); Link(v, u);
}
DFS(1, 1); DFS(2, 1);
printf("%d\n", (int)ans.size());
for (int i = 0; i < ans.size(); i++) printf("%d ", ans[i]);
}
AGC014
C - 닫힌 방
최단 경로 기반 계산: 출발점에서 벽 치우기 가능 영역 도달까지 \( k \) 단위 시간으로 묶음 처리.
#include <queue>
#include <cstdio>
#include <algorithm>
using namespace std;
const int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
struct Node { int x, y, step; };
int n, m, k, ans = 1e9;
char Map[805][805];
bool visit[805][805];
queue<Node> q;
int main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++) {
scanf("%s", Map[i] + 1);
for (int j = 1; j <= m; j++)
if (Map[i][j] == 'S') {
visit[i][j] = true;
q.push((Node){i, j, 0});
}
}
while (!q.empty()) {
Node tmp = q.front(); q.pop();
ans = min(ans, min(min(tmp.x - 1, tmp.y - 1), min(n - tmp.x, m - tmp.y)));
if (tmp.step == k) continue;
for (int i = 0; i < 4; i++) {
int nx = tmp.x + dx[i], ny = tmp.y + dy[i];
if (nx < 1 || nx > n || ny < 1 || ny > m || Map[nx][ny] == '#' || visit[nx][ny]) continue;
visit[nx][ny] = true;
q.push((Node){nx, ny, tmp.step + 1});
}
}
printf("%d", (ans + k - 1) / k + 1);
}
AGC015
C - 나무 대 미스테리
모든 연결 요소가 트리 → 구성요소 수 = 정점 수 - 간선 수. 2D 누적 합으로 각 질의 처리. 시간 복잡도 \( \Theta(NM + Q) \).
#include <cstdio>
using namespace std;
int n, m, q;
int 점갯수[2005][2005], 행간선갯수[2005][2005], 열간선갯수[2005][2005];
char Map[2005][2005];
int main() {
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= n; i++) scanf("%s", Map[i] + 1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
Map[i][j] -= '0';
점갯수[i][j] = (int)Map[i][j] + 점갯수[i - 1][j] + 점갯수[i][j - 1] - 점갯수[i - 1][j - 1];
if (Map[i][j]) {
if (Map[i - 1][j]) 행간선갯수[i][j] = 1;
if (Map[i][j - 1]) 열간선갯수[i][j] = 1;
}
행간선갯수[i][j] += 행간선갯수[i - 1][j] + 행간선갯수[i][j - 1] - 행간선갯수[i - 1][j - 1];
열간선갯수[i][j] += 열간선갯수[i - 1][j] + 열간선갯수[i][j - 1] - 열간선갯수[i - 1][j - 1];
}
}
while (q--) {
int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
int ans = 0;
ans += 점갯수[x2][y2] - 점갯수[x2][y1 - 1] - 점갯수[x1 - 1][y2] + 점갯수[x1 - 1][y1 - 1];
ans -= 행간선갯수[x2][y2] + 행간선갯수[x1][y1 - 1] - 행간선갯수[x2][y1 - 1] - 행간선갯수[x1][y2];
ans -= 열간선갯수[x2][y2] + 열간선갯수[x1 - 1][y1] - 열간선갯수[x2][y1] - 열간선갯수[x1 - 1][y2];
printf("%d\n", ans);
}
}
AGC016
C - 플러스/마이너스 사각형
충족 조건: \( h|H \) 및 \( w|W \) 일 때 무조건적으로 불가능. 그 외에는 주기적으로 값을 설정.
#include <cstdio>
using namespace std;
int 행, 열, h단위, w단위;
int main() {
scanf("%d%d%d%d", &행, &열, &h단위, &w단위);
if (!(행 % h단위) && !(열 % w단위)) return puts("아니오"), 0;
puts("예");
for (int i = 1; i <= 행; i++) {
for (int j = 1; j <= 열; j++) {
int val = (i % h단위 && j % w단위) ? 777 : -(((h단위 * w단위 - 1) * 777 + 1));
printf("%d ", val);
}
putchar('\n');
}
}
AGC019
B - 반전 및 비교
기하적 해석: 반전 중복 계산. 시작하는 문자열의 문자별 중복 제거.
#include <cstdio>
#include <cstring>
#define lint long long
using namespace std;
int n;
lint ans, alphaCount[26], suffix[500005];
char s[200005];
int main() {
scanf("%s", s + 1); n = strlen(s + 1);
for (int i = n; i >= 1; i--) {
suffix[i] = suffix[i + 1] + alphaCount[s[i] - 'a'];
ans += suffix[i];
alphaCount[s[i] - 'a']++;
}
printf("%lld", 1ll * n * (n - 1) / 2 - ans + 1);
}
AGC020
B - 아이스 링크 게임
역추적 및 범위 설정: \( t_0 = -xB + yD \) 형식의 해 존재 여부로 가능성 판단.
#include <cstdio>
#include <cmath>
#define lint long long
using namespace std;
int T;
inline lint gcd(lint A, lint B) {
while (B) A %= B, B ^= A ^= B ^= A;
return A;
}
inline lint floor(lint A, lint B) {
return (!((A > 0) ^ (B > 0))) ? (A / B) : (A / B - (A % B != 0));
}
int main() {
scanf("%d", &T);
while (T--) {
lint A, B, C, D, GCD;
scanf("%lld%lld%lld%lld", &A, &B, &C, &D);
GCD = gcd(B, D);
if (A < B || D < B) puts("아니오");
else if (C > B) puts("예");
else puts((floor(B - A - 1, GCD) > floor(C - A, GCD)) ? "아니오" : "예");
}
}
AGC021
A - 자릿수 합 2
최대 자릿수 합 검증: 선행 자리 조정 가능성 고려.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char s[20];
int ans[2];
int main() {
scanf("%s", s + 1);
for (int i = 1, len = strlen(s + 1); i <= len; i++) {
ans[0] += (i == 1) ? (s[i] - '0' - 1) : 9;
ans[1] += s[i] - '0';
}
printf("%d", max(ans[0], ans[1]));
}
AGC022
A - 다양한 단어
두 가지 전략:
- 문자 길이 < 26: 부재한 최소 문자 추가
- 길이 = 26: 특정 위치 문자 변경 후 재배열
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
char s[30], maxChar = 'a' - 1;
bool used[30];
int main() {
scanf("%s", s + 1);
n = strlen(s + 1);
if (n < 26) {
for (int i = 1; i <= n; i++) used[s[i] - 'a'] = true, putchar(s[i]);
for (int i = 0; i < 26; i++) if (!used[i]) return putchar(i + 'a'), 0;
}
for (int i = n; i >= 1; i--) {
if (s[i] < maxChar) {
for (int j = 1; j < i; j++) putchar(s[j]);
for (int j = s[i] - 'a' + 1; j < 26; j++) if (used[j]) return putchar(j + 'a'), 0;
}
maxChar = max(maxChar, s[i]);
used[s[i] - 'a'] = true;
}
return puts("-1"), 0;
}
B - GCD 수열
조건 별도 충족 후 병합: 인접 토큰 그룹의 상호 배제 관계 활용.
#include <cstdio>
using namespace std;
int n;
int main() {
scanf("%d", &n), n -= 3;
printf("2 3 29995 ");
if (n & 1) printf("30000 "), n--;
for (int i = 4, j = 29996; i < j && n; i += 2, j -= 2, n -= 2)
printf("%d %d ", i, j);
for (int i = 9, j = 29991; i < j && n; i += 6, j -= 6, n -= 2)
printf("%d %d ", i, j);
if (n) printf("25 29975");
}
AGC023
A - 0의 합 구간
누적 합 동일 지점 개수로 결과 도출: \( \sum_{j=1}^i a_j = \sum_{j=1}^k a_j \)일 때 \( (i,k) \) 쌍 카운트.
#include <map>
#include <cstdio>
#define lint long long
using namespace std;
int n;
lint sum, ans;
map<lint, lint> cnt;
int main() {
scanf("%d", &n);
cnt[0] = 1;
for (int i = 1; i <= n; i++) {
lint num; scanf("%lld", &num);
sum += num;
ans += cnt[sum];
cnt[sum]++;
}
printf("%lld", ans);
}
AGC024
B - 백프론트
최소 제거 횟수 → 최장 증가 부분 수열 \( (LIS) \) 길이 기반 반전.
#include <cstdio>
#include <algorithm>
using namespace std;
int n, tmp = 1, ans, a[200005];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) {
if (a[i] < a[i + 1]) tmp++;
else ans = max(ans, tmp), tmp = 1;
}
printf("%d", n - ans);
}
C - 순열 성장 쉬움
범위 종류 연산 결과 분석:
- 단순 구간: \( ans \leftarrow ans + 1 \)
- 멱급 구간: \( ans \leftarrow ans + A_i \)
#include <cstdio>
#include <algorithm>
#define lint long long
using namespace std;
int n;
lint ans, a[200005];
int main() {
scanf("%d", &n);
for (int i = 2; i <= n; i++) {
scanf("%lld", &a[i]);
if (a[i] <= a[i - 1]) ans += a[i];
else ans += 1;
}
printf("%lld", ans);
}
D - 그라달고리안 분류
루트 선정 최적화: 트리 구조에서 레이어별 최대 자식 수 기반 분기 계산.
#include <cstdio>
#include <algorithm>
#define lint long long
using namespace std;
int n;
lint ans1, ans2;
int arr[100005];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &arr[i]);
if (i > 1 && arr[i] != arr[i - 1] + 1) ans1 += arr[i], ans2 += i;
}
printf("%d %lld", ans1, ans2);
}
AGC025
B - RGB 색칠하기
조건 충결: \( \sum_{i=0}^n C_n^i \times C_n^j , [j = \frac{K-iA}{B}] \) 이중계산.
#include <cstdio>
#define lint long long
using namespace std;
const lint mod = 998244353;
lint n, m, a, b, ans, f[300005] = {1}, g[300005];
inline lint pow(lint base, lint power) {
lint value = 1;
while (power) {
if (power & 1) value = value * base % mod;
base = base * base % mod, power >>= 1;
}
return value;
}
inline lint Comb(lint n, lint r) {
return (n < r || n < 0 || r < 0) ? 0 : f[n] * g[r] % mod * g[n - r] % mod;
}
int main() {
scanf("%lld%lld%lld%lld", &n, &a, &b, &m);
for (lint i = 1; i <= n; i++) f[i] = f[i - 1] * i % mod;
g[n] = pow(f[n], mod - 2);
for (lint i = n - 1; i >= 0; i--) g[i] = g[i + 1] * (i + 1) % mod;
for (lint i = 0; i <= n; i++) {
if (m < a * i) continue;
if ((m - a * i) % b) continue;
lint j = (m - a * i) / b;
ans = (ans + Comb(n, i) * Comb(n, j) % mod) % mod;
}
printf("%lld", ans);
}
AGC026
B - rng10s
정수론적 검증: \( t_0 \equiv 0 \pmod{ \gcd(B, D) } \) 해의 존재 범위 판정.
#include <cstdio>
#include <cmath>
#define lint long long
using namespace std;
int T;
inline lint gcd(lint A, lint B) {
while (B) A %= B, B ^= A ^= B ^= A;
return A;
}
inline lint floor(lint A, lint B) {
return (!((A > 0) ^ (B > 0)) ? (A / B) : (A / B - (A % B != 0)));
}
int main() {
scanf("%d", &T);
while (T--) {
lint A, B, C, D, GCD;
scanf("%lld%lld%lld%lld", &A, &B, &C, &D);
GCD = gcd(B, D);
if (A < B || D < B) puts("No");
else if (C > B) puts("Yes");
else puts((floor(B - A - 1, GCD) > floor(C - A, GCD)) ? "No" : "Yes");
}
}
C - 문자열 채색
반분 기법: 두 산출 값의 기수 분석을 병해 일관성 유지.
#include <cstdio>
#include <map>
#define lint long long
using namespace std;
int n;
lint ans;
char s[40];
map<pair<lint, lint>, lint> hashMap;
inline lint Hash(lint val, char ch) {
return (val * 131 + ch - 'a' + 1) % 1000000007;
}
inline void DFS(int pos, lint h1, lint h2, int dir) {
if (dir == 1 && pos > n / 2) {
hashMap[make_pair(h1, h2)]++;
return;
}
if (dir == -1 && pos <= n + 1 - n / 2) {
ans += hashMap[make_pair(h1, h2)];
return;
}
DFS(pos + dir, Hash(h1, s[pos]), h2, dir);
DFS(pos + dir, h1, Hash(h2, s[pos]), dir);
}
int main() {
scanf("%d%s", &n, s + 1);
n *= 2; // Because string length
DFS(1, 0, 0, 1);
DFS(n, 0, 0, -1);
printf("%lld", ans);
}
AGC027
C - AB랜드 마당
삭제 기반 순환 자식 체크: 각 노드 별 'A','B' 연접 노드 정보 유지, 불가능 노드 축제.
#include <queue>
#include <cstdio>
using namespace std;
struct Edge { int to, next; };
int n, m, degree[200005][2];
bool visit[200005];
Edge edge[400005];
queue<int> q;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
char s[200005]; scanf("%s", s + 1);
for (int j = 1; j <= m; j++) {
if (s[j] == 'A') degree[i][0]++;
else if (s[j] == 'B') degree[i][1]++;
}
}
for (int i = 1; i <= n; i++)
if (degree[i][0] == 0 || degree[i][1] == 0)
visit[i] = true, q.push(i);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = 0; i < 2; i++) {
if (degree[u][i] == 0) continue;
for (int j = 1; j <= m; j++) {
int v = edge[j].to;
if (--degree[v][i^1] == 0 && !visit[v])
visit[v] = true, q.push(v);
}
}
}
int remain = 0;
for (int i = 1; i <= n; i++) remain += !visit[i];
puts(remain ? "Yes" : "No");
}
AGC029
B - 2의 멱승들
2의 거듭제곱 값 별 정렬 및 쌍 맞춤: 우선 크기 순 배열 후 정렬 대상 추출.
#include <cstdio>
#include <algorithm>
using namespace std;
int n, ans, a[200005];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
sort(a + 1, a + n + 1);
for (int i = 1 << 30; i >= 1; i >>= 1) {
int l = 1, r = n;
while (l < r) {
if (a[l] == -1 || (a[r] != -1 && a[l] + a[r] < i)) l++;
else if (a[r] == -1 || a[l] + a[r] > i) r--;
else {
ans++;
a[l] = a[r] = -1;
l++, r--;
}
}
}
printf("%d", ans);
}
AGC031
A - 다채로운 부분수열
조합 수학: 각 문자의 등장 분포에 따른 조합 가능 개수 생성.
#include <cstdio>
#define lint long long
using namespace std;
const lint mod = 1e9+7;
int n;
lint ans = 1, alphaCount[30];
char s[100005];
int main() {
scanf("%d%s", &n, s + 1);
for (int i = 1; i <= n; i++) alphaCount[s[i] - 'a']++;
for (int i = 0; i < 26; i++) ans = ans * (alphaCount[i] + 1) % mod;
printf("%lld", (ans + mod - 1) % mod);
}
B - 반전 순열
동적 계획법 + 누적: 이전 위치 값과의 기반으로 현재 위치 색인 결정.
#include <cstdio>
using namespace std;
const int mod = 1e9+7;
int n, dp[200005] = {1}, bucket[30];
char s[200005];
inline void Add(int &a, int b) { a = (a + b >= mod) ? (a + b - mod) : (a + b); }
int main() {
scanf("%d", &n);
scanf("%s", s + 1);
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1];
int c = s[i] - 'a';
Add(dp[i], bucket[c]);
bucket[c] = (bucket[c] + dp[i - 1]) % mod;
}
printf("%d", dp[n]);
}
AGC041
B - 투표 심사원
기준 충족 기반 순차 선택: 각 위치별 상대적 수용력 계산.
#include <cstdio>
#include <algorithm>
#define lint long long
using namespace std;
int n, m, v, p, ans, a[100005];
lint sum;
int main() {
scanf("%d%d%d%d", &n, &m, &v, &p);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
sort(a + 1, a + n + 1);
ans = p;
for (int i = p + 1; i <= n; i++) {
if (a[i] + m < a[p]) break;
if (v <= p + n - i || (1ll * (v - p - n + i) * m <= 1ll * a[p] * (i - p) - sum)) {
ans++;
}
sum += a[i] - a[p];
}
printf("%d", ans);
}
AGC043
A - 범위 뒤집기 경로
회색 비용 추가: '#' 타일 이동 시 비용 증가, DP 갱신.
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, f[105][105];
char Map[105][105];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%s", Map[i] + 1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (i == 1 && j == 1) {
f[i][j] = Map[i][j] == '#' ? 1 : 0;
continue;
}
int fromLeft = j > 1 ? f[i][j - 1] + (Map[i][j - 1] == '.' && Map[i][j] == '#') : 1e9;
int fromUp = i > 1 ? f[i - 1][j] + (Map[i - 1][j] == '.' && Map[i][j] == '#') : 1e9;
f[i][j] = min(fromLeft, fromUp);
}
}
printf("%d", f[n][m]);
}
AGC055
B - ABC 최상
특수 상태 정규화 함수: 시작과 종료 상태를 정규 형변환 후 비교.
#include <cstdio>
#include <vector>
using namespace std;
int n;
char a[500005], b[500005];
vector<int> x, y;
inline void Transform(char *s, vector<int> &result) {
for (int i = 1; i <= n; i++) {
int mod = (s[i] - 'A' + n - i) % 3;
if (result.size() >= 2 && result.back() == mod && result[result.size() - 2] == mod) {
result.pop_back(); result.pop_back();
} else {
result.push_back(mod);
}
}
}
int main() {
scanf("%d%s%s", &n, a + 1, b + 1);
Transform(a, x); Transform(b, y);
if (x.size() != y.size()) return puts("아니오"), 0;
for (int i = 0; i < x.size(); i++) {
if (x[i] != y[i]) return puts("아니오"), 0;
}
puts("예");
}