티스토리 뷰
A. Everyone Loves to Sleep
문제 :
<hide/>
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t;
for (cin >> t; t--;) {
int n, h, m, ans = 1e9;
cin >> n >> h >> m;
int t = h * 60 + m;
for (int i = 0; i < n; i++) {
cin >> h >> m;
int t1 = h * 60 + m;
if (t > t1) t1 += 1440;
if (t1 - t < ans) ans = t1 - t;
}
cout << ans / 60 << ' ' << ans % 60 << '\n';
}
return 0;
}
B. Remove Prefix
문제 :
길이가 $n$인 수열과 수열의 가장 첫 번째 원소를 지우는 연산이 있을 때 수열의 모든 원소가 최대 한 번씩만 등장하기 위해 사용해야 하는 연산의 최소 횟수를 구하면 된다.
풀이 :
$1\leq a_i\leq2\times10^5$이므로 원소가 중복되는지 검사하는 배열을 만든다. 배열은 값은 처음에 모두 0으로 하고 수열의 처음부터 끝까지 보며 각 원소의 위치를 저장한다. 이때 저장돼있던 배열의 값이 0이 아니면 원소가 중복된다는 뜻이므로 저장된 위치가 답이 될 수 있는지 확인한 후 현재의 위치 값으로 바꿔준다.
코드 :
<hide/>
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t;
for (cin >> t; t--;) {
int n, x, ans = 0;
cin >> n;
vector<int> inx(n + 1, 0);
for (int i = 1; i <= n; i++) {
cin >> x;
if (inx[x] != 0 && inx[x] > ans) ans = inx[x];
inx[x] = i;
}
cout << ans << '\n';
}
return 0;
}
C. Minimum Varied Number
문제 :
한자리 수들을 중복되지 않게 최소로 사용하여 합이 $s$가 되면 된다.
풀이 :
$9$부터 $1$까지 $1$씩 감소시키면서 $s$보다 작으면 $s$에서 빼준다. 빼준 숫자들을 오름차순으로 출력하면 된다.
코드 :
<hide/>
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t;
for (cin >> t; t--;) {
int x, i;
cin >> x;
for (i = 9;; i--) {
if (x - i <= 0) {
cout << x;
break;
}
x -= i;
}
for (i++; i <= 9; i++) cout << i;
cout << '\n';
}
return 0;
D. Color with Occurrences
문제 :
문자열 $t$와 $n$개의 문자열이 있을 때 $n$개의 문자열들을 최소로 사용하여 $t$를 만들 때 그 횟수를 구하면 된다.
문자열의 각 값들이 겹쳐도 된다. 예를 들어 $s_1 = ba, s_2=aba$라 했을 때 $s_1$과 $s_2$를 합쳐 $baaba$도 되지만 $baba$도 만들 수 있다.
풀이 :
$t$의 길이가 최대 $100$, $s_i$($n$개 문자열 중 $i$번째 문자열)의 길이가 최대 $10$이라 완전 탐색으로 해도 시간 안에 답이 구해진다. $t$에서 각 위치의 문자들이 한번 이상은 있어야 하기 때문에 앞에서부터 순서대로 문자를 채워간다. $t$에서 가장 마지막으로 완성된 문자의 위치를 $i-1$이라 하면 $i$번째 문자를 포함하면서 아직 포함되지 않은 문자를 가장 많이 채울 수 있는 $s_i$를 다음으로 사용하고 이를 $t$의 모든 문자가 채워질 때까지 반복하면 된다. 만약 어떤 $s_i$로도 채울 수 없다면 $-1$이 된다.
코드 :
<hide/>
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t;
for (cin >> t; t--;) {
string str;
cin >> str;
int n;
cin >> n;
vector<string> ar(n);
for (int i = 0; i < n; i++) cin >> ar[i];
vector<pair<int, int>> ans;
int inx = 0, i;
for (i = inx; inx < str.size();) {
int next = 0, pos1, pos2;
for (int j = 0; j < n; j++) {
for (int k = 0; k < ar[j].size(); k++) {
if (inx - k < 0) break;
if (inx - k + ar[j].size() > str.size()) continue;
if (str.substr(inx - k, ar[j].size()) == ar[j]) {
if (inx - k + ar[j].size() > next) {
next = inx - k + ar[j].size();
pos1 = j + 1;
pos2 = inx - k + 1;
}
break;
}
}
}
if (next == 0) break;
ans.push_back({ pos1,pos2 });
inx = next;
}
if (inx >= str.size()) {
cout << ans.size() << '\n';
for (auto it : ans) cout << it.first << ' ' << it.second << '\n';
ans.clear();
}
else cout << "-1\n";
}
return 0;
}
E. Add Modulo 10
문제 :
$n$개의 정수 수열 $a_1, a_2, ..., a_n$이 있고 어떤 원소의 $10$으로 나눈 나머지를 자신에게 더할 수 있는 연산이 있다. 예를 들어 $12$는 $2$를 더하여 $14$가 될 수 있고 또 $14$에서 $4$를 더하여 $18$이 될 수 있다. 이때 이런 수열과 연산을 통하여 모든 원소가 같은 값을 가지게 할 수 있는지 구하면 된다.
풀이 :
어떤 수가 홀수라면 짝수로 만들기 위해 $10$으로 나눈 나머지를 한번 더해준다.
(1) 어떤 수가 $5$로 나누어 떨어질 때 : $10n(0\leq n$인 정수$)$형태로 만들어 준 뒤 $10$으로 나눴을 때 나오는 몫의 종류가 $1$이하면 된다.
(2) 어떤 수가 $5$로 나누어 떨어지지 않을 때 : $2\rightarrow 4\rightarrow 8\rightarrow 6\rightarrow 2\rightarrow ...$로 반복되는데 반복될 때마다 $20$이 증가하므로 $20$으로 나눈 나머지가 같은지 보면 된다. 먼저 일의 자리를 $2$로 만들어준 뒤 $20$으로 나눈 값의 종류가 $1$이하면 된다.
코드 :
<hide/>
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t;
for (cin >> t; t--;) {
int n, x, cnt = 0;
int temp = 0, stat5[3] = {};//0,10,10u
int prev = 0, pcnt = 0;
bool stat[3] = {};//0,2,12
cin >> n;
while (n--) {
cin >> x;
if (x % 5 == 0) while (x % 10) x += x % 10;
while (x % 5 != 0 && x % 10 != 2) x += x % 10;
if (x % 5 == 0) {
stat[0] = true;
if (x == 0) stat5[0] = true;
else if (x == 10) stat5[1] = true;
else {
if (prev != x) pcnt++;
prev = x;
stat5[2] = true;
}
}
else if (x % 20 == 2) stat[1] = true;
else stat[2] = true;
}
if ((int)stat5[0] + stat5[1] + stat5[2] > 1 || pcnt > 1 || (int)stat[0] + stat[1] + stat[2] > 1) cout << "No\n";
else cout << "Yes\n";
}
return 0;
}
F. Build a Tree and That Is It
문제 :
풀이 :
G. Path Prefixes
문제 :
$1$을 루트로 하면서 $n$개의 정점으로 구성된 트리가 있고 각 간선에는 $a_i, b_i$의 양수 가중치가 있다.
$1$부터 임의의 $u (2\leq u\leq n)$까지 가는 경로의 $\sum a_i$를 $A$라 하고,
$1$부터 $v (1$부터 $u$까지 경로 중 임의의 원소$)$까지 가는 경로의 $\sum b_i$를 $B$라 할 때
$A\geq B$를 만족하게 하는 $v$가 $1$부터 몇 개의 간선을 거쳐오는지를 구하면 된다. ($1$을 제외한 모든 원소에 대하여)
풀이 :
$1$부터 $u$까지 가는 간선의 가중치가 모두 양수이므로 이동할수록 계속 누적되는 값은 계속 증가한다. 각 정점들에 대해 1부터 자신까지의 $A(=\sum a_i)$를 구해놓고 $1$부터 트리를 dfs로 탐색하는데 각 간선의 값이 누적될 때마다 그 값을 벡터에 저장해놓는다. 그러면 어떤 정점에서 $v$를 구할 때 저장된 벡터의 값들 중 자신의 $A$값보다 작은 값들 중 제일 큰 값의 위치가 답이 된다. 이를 이분 탐색으로 빠르게 구할 수 있다.
코드 :
<hide/>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct node {
int p, a, b;
};
const int N = 2e5 + 2;
vector<vector<node>> adj(N);
vector<ll> ans(N), A(N), st = { 0 };
void getA(int inx, ll sum) {
for (int i = 0; i < adj[inx].size(); i++) {
getA(adj[inx][i].p, sum + adj[inx][i].a);
}
A[inx] = sum;
return;
}
void getAns(int inx) {
int left = 0, right = st.size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (A[inx] < st[mid]) right = mid - 1;
else left = mid + 1;
}
ans[inx] = left - 1;
for (int i = 0; i < adj[inx].size(); i++) {
st.push_back(st.back() + adj[inx][i].b);
getAns(adj[inx][i].p);
st.pop_back();
}
return;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t;
for (cin >> t; t--;) {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
adj[i].clear();
ans[i] = 0;
}
int p, a, b;
for (int i = 2; i <= n; i++) {
cin >> p >> a >> b;
adj[p].push_back({ i,a,b });
}
getA(1, 0);
getAns(1);
for (int i = 2; i <= n; i++) cout << ans[i] << ' ';
cout << '\n';
}
return 0;
}'ps' 카테고리의 다른 글
| codeforces round 814 (div.2) (0) | 2022.08.25 |
|---|---|
| codeforces round 813 (div.2) (0) | 2022.08.20 |
| codeforces round 812 (div.2) (0) | 2022.08.17 |
| educational codeforces round 133 (0) | 2022.08.11 |
| codeforces round 810 (div.2) (0) | 2022.08.04 |