길이가 n인 문자열이 s가 있다. s에 T,i,m,u,r이 한 번씩만 있으면서 다른 나머지 문자가 없는지 알아보면 된다.
풀이 :
문자열의 각 문자들의 개수를 세주고 T,i,m,u,r이 한 번씩만 있는지 보면 된다.
코드 :
cpp
열기
#include<bits/stdc++.h>usingnamespace std;
voidsolve(){
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;
}
intmain(){
ios::sync_with_stdio(0); cin.tie(0);
int t;
for (cin >> t; t--;) solve();
return0;
}
B. Colourblindness
문제 :
2×n크기의 판에 3개의 색 r, g, b으로 채워져 있다. g와 b를 같은 색으로 볼 때 두 행이 같은지 알아보면 된다.
풀이 :
1행의 i번째 값이 r이면 1, g이거나 b이면 2라 하고,
2행의 i번째 값이 r이면 1, g이거나 b이면 2라 할 때 각 행의 i번째 값이 같은지 비교해 보면 된다.
코드 :
cpp
열기
#include<bits/stdc++.h>usingnamespace std;
voidsolve(){
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;
}
intmain(){
ios::sync_with_stdio(0); cin.tie(0);
int t;
for (cin >> t; t--;) solve();
return0;
}
C. Word Game
문제 :
3명의 사람이 단어를 n번 입력한다. 만약 입력한 단어가 한 번만 있었다면(3명 중 한 명만 단어를 입력) 3점을 얻고 두 번 있었다면(3명 중 2명이 단어를 입력) 1점을 얻고 3명 모두가 입력한 단어라면 점수를 얻지 못한다. 이때 각 3명의 사람이 얻은 점수를 구하면 된다.
풀이 :
map을 사용해서 한번 단어가 입력될 때마다 value값을 1씩 증가시켜 단어가 몇 번 입력됐는지를 알아보고 각 사람들의 점수를 구하면 된다.
코드 :
cpp
열기
#include<bits/stdc++.h>usingnamespace std;
voidsolve(){
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;
elseif (mp[ar[i][j]] == 2) score[i]++;
}
}
for (int i = 0; i < 3; i++) cout << score[i] << ' ';
cout << '\n';
return;
}
intmain(){
ios::sync_with_stdio(0); cin.tie(0);
int t;
for (cin >> t; t--;) solve();
return0;
}
D. Line
문제 :
n명의 사람이 일렬로 왼쪽 또는 오른쪽을 보고 서있다. 왼쪽을 보고 있는 사람은 첫 번째부터 자신의 바로 이전 위치까지의 사람을 볼 수 있고 오른쪽을 보고 있는 사람은 자신의 다음 사람부터 마지막 사람까지 볼 수 있다. 예를 들어 LRRLL이라면 각 위치에서 보이는 사람의 수는 [0,3,2,3,4]이고 n명의 사람들에 대한 값은 보이는 사람의 수의 합인 12가 된다. 각 사람이 바라보는 방향을 k번 변경할 수 있을 때 보이는 사람의 수가 최대 몇 명이 될 수 있는지 구하면 된다. (1≤k≤n)
풀이 :
i번째 사람이 L이라면 보이는 사람의 수는 i−1이고 R이라면 n−i이다. L에서 R로 바뀐다면 그 차이는 (n−i)−(i−1)이고 R에서 L로 바뀐다면 그 차이는 (i−1)−(n−i)이다. 이 값이 양수라면 보는 방향을 변경하는 것이 이득이고 아니라면 그냥 두는 게 낫다. 따라서 차이를 모두 우선순위 큐에 넣어서 양수일 때만 뽑아주면 된다. 처음 사람들이 볼 수 있는 사람들의 총 합에 양수일때만 값을 더하고 아니라면 이때까지 구한 값이 답이 된다.
코드 :
cpp
열기
#include<bits/stdc++.h>usingnamespace std;
using ll = longlong;
char str[200005];
voidsolve(){
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;
}
intmain(){
ios::sync_with_stdio(0); cin.tie(0);
int t;
for (cin >> t; t--;) solve();
return0;
}
E. Counting Rectangles
문제 :
n개의 직사각형이 있다. i번째 사각형의 세로, 가로 크기는 hi,wi이다. q개의 쿼리가 주어지고 각 쿼리에서 작은 사각형과 큰 사각형의 세로, 가로 크기 hs,ws,hb,wb가 주어질 때 각 n개의 사각형들이 작은 사각형을 포함하고 큰 사각형에 포함될 수 있는지 알아보면 된다. 포함한다는 것은 변이 겹치지 않게 완전히 포함되어야 한다. 즉 hs<hi<hb이고 ws<wi<wb이다. 이 조건을 만족하는 모든 사각형의 넓이(=∑nihiwi)를 구하면 된다.
풀이 :
각 쿼리마다 n개의 사각형을 전부 확인하면 O(nq)로 문제에서 n,q는 최대 105이므로 O(1010)이 되므로 시간 안에 구할 수 없다. di,j를 1≤ 세로 길이 ≤i, 1≤ 가로길이 ≤j인 사각형들 넓이의 합이라 하면 각 쿼리에 대한 답을 dhb−1,wb−1−dhb−1,ws−dhs,wb−1+dhs,ws의 식을 활용하여 O(1)에 구할 수 있다.
예를 들어
3
2 1
2 3
3 2
1 1 3 4의 예제를 그림으로 표현해보면 아래의 그림처럼 구할 수 있다. (d와 1 1 3 4의 예제를 구하는 과정)
코드 :
cpp
열기
#include<bits/stdc++.h>usingnamespace std;
using ll = longlong;
voidsolve(){
constint 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;
}
intmain(){
ios::sync_with_stdio(0); cin.tie(0);
int t;
for (cin >> t; t--;) solve();
return0;
}
F. L-shapes
문제 :
n×m크기의 판에 ㄱ자 모형의 무늬가 각 변이나 꼭짓점을 공유하지 않고 잘 배치되어 있는지 알아보면 된다.
풀이 :
판에 ㄱ자 모형으로 표시된 문자의 개수를 세주고 판을 훑으면서 ㄱ자 모형인지 확인하고 맞다면 전체 개수에서 3을 빼준다. 끝까지 봤을 때 0이라면 적절하게 잘 배치되었다고 할 수 있다. 변이나 꼭짓점을 공유하는지의 여부는 ㄱ자를 구성하는 각 문자들을 기준으로 자신의 위치와 1씩 떨어진 거리의 문자들을 확인해서 ∗의 수가 3인지를 확인해주면 된다.
코드 :
cpp
열기
#include<bits/stdc++.h>usingnamespace std;
using ll = longlong;
voidsolve(){
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;
}
intmain(){
ios::sync_with_stdio(0); cin.tie(0);
int t;
for (cin >> t; t--;) solve();
return0;
}
G. Even-Odd XOR
문제 :
n이 주어질 때 길이가 n인 수열에서 짝수번째 원소들의 XOR값과 홀수번째 원소들의 XOR값이 같게 하는 수열을 찾으면 된다. 수열의 원소는 모두 다르고 231−1보다 작은 음이 아닌 정수이다.
