https://codeforces.com/contest/1644
Dashboard - Educational Codeforces Round 123 (Rated for Div. 2) - Codeforces
codeforces.com
A. Doors and Keys
더보기
풀이
- 각 키와 그에 맞는 도어에 대해 키 -> 도어 순서로 되어있지 않으면 NO
코드
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int TC; cin >> TC;
while (TC--) {
string s;
cin >> s;
set<int> key;
bool answer = true;
for (auto e: s) {
if ('a' <= e && e <= 'z') {
key.insert(e);
} else {
if (!key.count(e - 'A' + 'a')) {
answer = false;
break;
}
}
}
if (answer) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
}
B. Anti-Fibonacci Permutation
더보기
풀이
- 피보나치 수열이 증가수열이므로 내림차순으로 순열을 정렬하면 뭔가 되지 않을까부터 생각
- 맨 뒤의 1을 앞으로 하나씩 옮기면 된다.
- $[N, N - 1, ... 2, 1], [N, N - 1, ..., 1, 2], ..., [1, N, N - 1, ..., 2]$
코드
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int TC; cin >> TC;
while (TC--) {
int N;
cin >> N;
vector<int> a(N - 1);
for (int i = 0; i < N - 1; ++i) {
a[i] = i + 2;
}
sort(rall(a));
for (int i = 0; i < N; ++i) {
bool did = false;
for (int j = 0; j < N; ++j) {
if (!did && i == j) {
cout << "1 ";
did = true;
} else {
cout << a[j - did] << ' ';
}
}
cout << '\n';
}
}
}
C. Increase Subarray Sums
더보기
풀이
- 길이 1, 2, ..., N 부분수열에 대해서 길이에 대한 maxSum 값을 구해둔다
- 그 maxSum 부분 수열의 원소들에 최대한 X 를 더하는게 이득
- 곱하는 위치수 k 에 대한 길이 d 부분수열의 합의 최댓값은 $maxSum[d] + min(d, k), * X$
코드
- 시간복잡도: $O(N^2)$
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int TC; cin >> TC;
while (TC--) {
int N, X;
cin >> N >> X;
vector<long long> a(N);
vector<long long> pa(N, 0);
for (int i = 0; i < N; ++i) {
cin >> a[i];
pa[i] = a[i];
if (i) pa[i] += pa[i - 1];
}
vector<long long> maxSum(N + 1, -1e18);
maxSum[0] = 0;
for (int d = 1; d <= N; ++d) {
long long maxSum_ = -1e18;
for (int i = 0; i + d - 1 < N; ++i) {
long long sum = pa[i + d - 1];
if (i) sum -= pa[i - 1];
maxSum_ = max(maxSum_, sum);
}
maxSum[d] = maxSum_;
}
for (int k = 0; k <= N; ++k) {
long long answer = 0;
for (int d = 0; d <= N; ++d) {
answer = max(answer, maxSum[d] + 1LL * min(d, k) * X);
}
cout << answer << ' ';
}
cout << '\n';
}
}
D. Cross Coloring
더보기
풀이
- 각 칸에 대해서 가장 마지막으로 행한 operation 의 번호를 매기고 모든 칸에서 distinct 한 operation 번호의 수를 p 라 하면 각 p 개의 그룹에 색의 개수 k 개씩 칠하는 경우가 있으므로 답은 $k^p$ 이다
- operation 의 역순으로 생각해보자
- 이전에 칠해진거 밑에 칠해진다
- 다 채워진 뒤에는 더 이상 칸들의 마지막 operation 번호에 변화가 있을 수 없다.
- $r[x], c[y]$ 각각 x행/y열 이 이미 다른 번호에의해 칠해졌는가 라고 정의하면
- 지금 수행할 operation 의 x, y 에 대해
- r[x] = true && c[y] = true 이면 변화가 없음
- 하나라도 false 면 가능
- 또한 전체행이나 전체열이 채워지면 더 해볼 필요가 없음
- 지금 수행할 operation 의 x, y 에 대해
코드
- 시간복잡도: $O(Q)$
- 주의할점: testcase 에 대한 n, m 의 제한이 없어서 testcase 마다 vector r, c 를 잡으면 이거때문에 시간초과남
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int TC; cin >> TC;
vector<int> r(2e5 + 1, -1), c(2e5 + 1, -1);
while (TC--) {
int N, M, K, Q;
cin >> N >> M >> K >> Q;
vector<pair<int, int> > operation(Q);
for (int i = 0; i < Q; ++i) {
cin >> operation[Q - 1 - i].first >> operation[Q - 1 - i].second;
}
int rr, cc;
rr = cc = 0;
long long answer = 1;
long long MOD = 998244353;
for (auto [x, y]: operation) {
if (rr == N || cc == M) break;
if (r[x] == TC && c[y] == TC) continue;
answer = answer * K % MOD;
if (r[x] != TC) r[x] = TC, rr++;
if (c[y] != TC) c[y] = TC, cc++;
}
cout << answer << '\n';
}
}
E. Expand the Path
더보기
풀이
- 움직이는 칸의 범위는 처음 R, 처음 D 를 duplicate 한 칸들로 둘러 싸여있는 형태
- 한 종류만 있는 경우에는 그냥 N
- 칸 범위 구하기
- 초기 칸 수
- 아래로 한칸씩 내릴때(duplicate D) 추가되는 칸 수(정사영 내렸을때 칸 수) * (내릴 수 있는 칸 수)
- 추가되는 칸 수 계산할 때 처음 R, D 에 유의
- 아래로 다 내린상태에서 옆으로 옮길때 추가되는 칸 수 * 옆으로 옮길수 있는 칸 수
코드
- 시간복잡도: $O(s.size())$
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int TC; cin >> TC;
while (TC--) {
long long N;
cin >> N;
string s;
cin >> s;
long long r, d, fr, fd;
r = d = fr = fd = 0;
for (int i = 0; i < s.size();) {
if (s[i] == 'R') {
int tmp = 0;
while (i < s.size() && s[i] == 'R') ++tmp, ++i;
r += tmp;
if (fr == 0) fr += tmp;
} else {
int tmp = 0;
while (i < s.size() && s[i] == 'D') ++tmp, ++i;
d += tmp;
if (fd == 0) fd += tmp;
}
}
if (r == 0 || d == 0) {
cout << N << '\n';
continue;
}
long long answer = 0;
if (s[0] == 'D') {
answer = (r + d + 1);
answer += (r + 1) * (N - d - 1);
answer += (d - fd + 1 + N - d - 1) * (N - r - 1);
} else {
answer = (r + d + 1);
answer += (r - fr + 1) * (N - d - 1);
answer += (d + 1 + N - d - 1) * (N - r - 1);
}
cout << answer << '\n';
}
}
728x90
'PS > Codeforces' 카테고리의 다른 글
| [코드포스] Codeforces Round #774 (Div. 2) (코포 774 딥2) 풀이 (0) | 2022.03.19 |
|---|---|
| [코드포스] Codeforces Round #773 (Div. 2) (코포 773 딥2) 풀이 (0) | 2022.02.27 |
| [코드포스] Codeforces Round #772 (Div. 2) 풀이 (0) | 2022.02.22 |
| [코드포스] Codeforces Round #771 (Div. 2) 풀이 (0) | 2022.02.22 |
| [코드포스] Codeforces Global Round 19 풀이 (0) | 2022.02.17 |
