티스토리 뷰
A. Spell Check
문제 :
길이가 $n$인 문자열이 $s$가 있다. $s$에 $T, i, m, u, r$이 한 번씩만 있으면서 다른 나머지 문자가 없는지 알아보면 된다.
풀이 :
문자열의 각 문자들의 개수를 세주고 $T,i,m,u,r$이 한 번씩만 있는지 보면 된다.
코드 :
<hide/>
#include<bits/stdc++.h>
using namespace std;
void solve() {
string str;
int n;
cin >> n >> str;
int A[30] = { 0, }, a[30] = { 0, };
for (int i = 0; i < n; i++) {
if ('a' <= str[i] && str[i] <= 'z') a[str[i] - 'a']++;
else A[str[i] - 'A']++;
}
if (n == 5 && A['T' - 'A'] && a['i' - 'a'] && a['m' - 'a'] && a['u' - 'a'] && a['r' - 'a']) cout << "YES\n";
else cout << "NO\n";
return;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t;
for (cin >> t; t--;) solve();
return 0;
}
B. Colourblindness
문제 :
$2\times n$크기의 판에 3개의 색 r, g, b으로 채워져 있다. g와 b를 같은 색으로 볼 때 두 행이 같은지 알아보면 된다.
풀이 :
1행의 $i$번째 값이 r이면 $1$, g이거나 b이면 $2$라 하고,
2행의 $i$번째 값이 r이면 $1$, g이거나 b이면 $2$라 할 때 각 행의 $i$번째 값이 같은지 비교해 보면 된다.
코드 :
<hide/>
#include<bits/stdc++.h>
using namespace std;
void solve() {
int n;
string s1, s2;
cin >> n;
cin >> s1 >> s2;
bool st = true;
for (int i = 0; i < n; i++) {
int t1 = s1[i] == 'R' ? 1 : 2;
int t2 = s2[i] == 'R' ? 1 : 2;
if (t1 != t2) {
st = false;
break;
}
}
if (st) cout << "YES\n";
else cout << "NO\n";
return;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t;
for (cin >> t; t--;) solve();
return 0;
}
C. Word Game
문제 :
3명의 사람이 단어를 $n$번 입력한다. 만약 입력한 단어가 한 번만 있었다면(3명 중 한 명만 단어를 입력) 3점을 얻고 두 번 있었다면(3명 중 2명이 단어를 입력) 1점을 얻고 3명 모두가 입력한 단어라면 점수를 얻지 못한다. 이때 각 3명의 사람이 얻은 점수를 구하면 된다.
풀이 :
map을 사용해서 한번 단어가 입력될 때마다 value값을 1씩 증가시켜 단어가 몇 번 입력됐는지를 알아보고 각 사람들의 점수를 구하면 된다.
코드 :
<hide/>
#include<bits/stdc++.h>
using namespace std;
void solve() {
map<string, int> mp;
int n;
cin >> n;
vector<vector<string>> ar(3, vector<string>(n));
for (int i = 0; i < 3; i++) {
for (int j = 0; j < n; j++) {
cin >> ar[i][j];
if (mp.find(ar[i][j]) == mp.end()) mp.insert({ ar[i][j],1 });
else mp[ar[i][j]]++;
}
}
int score[3] = { 0, };
for (int i = 0; i < 3; i++) {
for (int j = 0; j < n; j++) {
if (mp[ar[i][j]] == 1) score[i] += 3;
else if (mp[ar[i][j]] == 2) score[i]++;
}
}
for (int i = 0; i < 3; i++) cout << score[i] << ' ';
cout << '\n';
return;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t;
for (cin >> t; t--;) solve();
return 0;
}
D. Line
문제 :
$n$명의 사람이 일렬로 왼쪽 또는 오른쪽을 보고 서있다. 왼쪽을 보고 있는 사람은 첫 번째부터 자신의 바로 이전 위치까지의 사람을 볼 수 있고 오른쪽을 보고 있는 사람은 자신의 다음 사람부터 마지막 사람까지 볼 수 있다. 예를 들어 $LRRLL$이라면 각 위치에서 보이는 사람의 수는 $[0,3,2,3,4]$이고 $n$명의 사람들에 대한 값은 보이는 사람의 수의 합인 $12$가 된다. 각 사람이 바라보는 방향을 $k$번 변경할 수 있을 때 보이는 사람의 수가 최대 몇 명이 될 수 있는지 구하면 된다. $(1\leq k\leq n)$
풀이 :
$i$번째 사람이 $L$이라면 보이는 사람의 수는 $i-1$이고 $R$이라면 $n-i$이다. $L$에서 $R$로 바뀐다면 그 차이는 $(n-i)-(i-1)$이고 $R$에서 $L$로 바뀐다면 그 차이는 $(i-1)-(n-i)$이다. 이 값이 양수라면 보는 방향을 변경하는 것이 이득이고 아니라면 그냥 두는 게 낫다. 따라서 차이를 모두 우선순위 큐에 넣어서 양수일 때만 뽑아주면 된다. 처음 사람들이 볼 수 있는 사람들의 총 합에 양수일때만 값을 더하고 아니라면 이때까지 구한 값이 답이 된다.
코드 :
<hide/>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
char str[200005];
void solve() {
ll n;
priority_queue<ll, vector<ll>, less<ll>> pq;
cin >> n >> &str[1];
ll sum = 0;
for (ll i = 1; i <= n; i++) {
if (str[i] == 'L') {
pq.push((n - i) - (i - 1));
sum += i - 1;
}
else {
pq.push((i - 1) - (n - i));
sum += n - i;
}
}
while (pq.size()) {
if (pq.top() > 0) sum += pq.top();
pq.pop();
cout << sum << ' ';
}
cout << '\n';
return;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t;
for (cin >> t; t--;) solve();
return 0;
}
E. Counting Rectangles
문제 :
$n$개의 직사각형이 있다. $i$번째 사각형의 세로, 가로 크기는 $h_i, w_i$이다. $q$개의 쿼리가 주어지고 각 쿼리에서 작은 사각형과 큰 사각형의 세로, 가로 크기 $h_s, w_s, h_b, w_b$가 주어질 때 각 $n$개의 사각형들이 작은 사각형을 포함하고 큰 사각형에 포함될 수 있는지 알아보면 된다. 포함한다는 것은 변이 겹치지 않게 완전히 포함되어야 한다. 즉 $h_s < h_i < h_b$이고 $w_s < w_i < w_b$이다. 이 조건을 만족하는 모든 사각형의 넓이$(=\sum_i^n{h_i w_i})$를 구하면 된다.
풀이 :
각 쿼리마다 $n$개의 사각형을 전부 확인하면 $O(nq)$로 문제에서 $n, q$는 최대 $10^5$이므로 $O(10^{10})$이 되므로 시간 안에 구할 수 없다. $d_{i,j}$를 $1\leq$ 세로 길이 $\leq i$, $1\leq$ 가로길이 $\leq j$인 사각형들 넓이의 합이라 하면 각 쿼리에 대한 답을 $d_{h_b-1,w_b-1} - d_{h_b-1,w_s} - d_{h_s,w_b-1} + d_{h_s,w_s}$의 식을 활용하여 $O(1)$에 구할 수 있다.
예를 들어
3
2 1
2 3
3 2
1 1 3 4의 예제를 그림으로 표현해보면 아래의 그림처럼 구할 수 있다. (d와 1 1 3 4의 예제를 구하는 과정)
코드 :
<hide/>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
const int N = 1e3;
vector<vector<ll>> d(N + 2, vector<ll>(N + 2, 0));
int n, q;
cin >> n >> q;
ll x, y;
while (n--) {
cin >> x >> y;
d[x][y] += x * y;
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++)
d[i][j] = d[i][j] + d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];
}
int s1, b1, s2, b2;
while (q--) {
cin >> s1 >> b1 >> s2 >> b2;
cout << d[s2 - 1][b2 - 1] - d[s2 - 1][b1] - d[s1][b2 - 1] + d[s1][b1] << '\n';
}
return;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t;
for (cin >> t; t--;) solve();
return 0;
}
F. L-shapes
문제 :
$n\times m$크기의 판에 ㄱ자 모형의 무늬가 각 변이나 꼭짓점을 공유하지 않고 잘 배치되어 있는지 알아보면 된다.
풀이 :
판에 ㄱ자 모형으로 표시된 문자의 개수를 세주고 판을 훑으면서 ㄱ자 모형인지 확인하고 맞다면 전체 개수에서 $3$을 빼준다. 끝까지 봤을 때 $0$이라면 적절하게 잘 배치되었다고 할 수 있다. 변이나 꼭짓점을 공유하는지의 여부는 ㄱ자를 구성하는 각 문자들을 기준으로 자신의 위치와 1씩 떨어진 거리의 문자들을 확인해서 $*$의 수가 $3$인지를 확인해주면 된다.
코드 :
<hide/>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int n, m;
cin >> n >> m;
vector<vector<char>> ar(n + 3, vector<char>(m + 3, '.'));
int cc = 0;
for (int i = 1; i <= n; i++) {
cin >> &ar[i][1];
for (int j = 1; j <= m; j++) {
if (ar[i][j] == '*') cc++;
}
}
int Y[] = { -1,0,1,0 }, X[] = { 0,1,0,-1 };
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (ar[i][j] == '*') {
int cnt = 0, inx;
for (int k = 0; k < 4; k++) {
if (ar[i + Y[k]][j + X[k]] == '*' && ar[i + Y[(k + 1) % 4]][j + X[(k + 1) % 4]] == '*') cnt++, inx = k;
}
if (cnt == 1) {
queue<pair<int, int>> q;
q.push({ i,j });
q.push({ i + Y[inx],j + X[inx] });
q.push({ i + Y[(inx + 1) % 4],j + X[(inx + 1) % 4] });
while (q.size()) {
int y = q.front().first;
int x = q.front().second;
q.pop();
int temp = 0;
for (int I = -1; I <= 1; I++) {
for (int J = -1; J <= 1; J++) {
if (ar[y + I][x + J] == '*') temp++;
}
}
if (temp != 3) {
cout << "NO\n";
return;
}
}
cc -= 3;
}
}
}
}
if (cc) cout << "NO\n";
else cout << "YES\n";
return;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t;
for (cin >> t; t--;) solve();
return 0;
}
G. Even-Odd XOR
문제 :
$n$이 주어질 때 길이가 $n$인 수열에서 짝수번째 원소들의 XOR값과 홀수번째 원소들의 XOR값이 같게 하는 수열을 찾으면 된다. 수열의 원소는 모두 다르고 $2^{31}-1$보다 작은 음이 아닌 정수이다.
'ps' 카테고리의 다른 글
| codeforces round 819 (div.1 + div.2) A-C (0) | 2022.09.22 |
|---|---|
| codeforces round 818 (div.2) A-C (0) | 2022.09.21 |
| educational codeforces round 134 (div.2) (0) | 2022.09.07 |
| codeforces round 816 (div.2) (0) | 2022.09.06 |
| codeforces round 815 (div.2) (0) | 2022.08.30 |