https://atcoder.jp/contests/abc241/tasks
Tasks - AtCoder Beginner Contest 241（Sponsored by Panasonic）
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
A - Digit Machine
더보기
풀이
- 배열 a 를 함수로 생각해서 세번 적용
코드
#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 N = 10;
vector<int> a(N);
for (auto& e: a) {
cin >> e;
}
cout << a[a[a[0]]] << '\n';
}
B - Pasta
더보기
풀이
- 멀티셋에 가진 누들 길이 다 넣고 플랜 진행하면서 없으면 No
코드
- 시간복잡도: $O(NlogN + MlogN)$
#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 N, M;
cin >> N >> M;
vector<int> a(N), b(M);
multiset<int> s;
for (auto& e: a) {
cin >> e;
s.insert(e);
}
for (auto& e: b) {
cin >> e;
auto it = s.find(e);
if (it == s.end()) {
cout << "No\n";
return 0;
}
s.erase(it);
}
cout << "Yes\n";
}
C - Connect 6
더보기
풀이
- 한 칸에 대해서, 그 칸을 시작으로 8방향에 대해서, 6칸 중 # 이 네칸이상이면 그 칸에서 그 방향으로 최대 2번 칠해서 6개 연속만들기 가능
코드
- 시간복잡도: $O(N^2*8*6)$
#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 N;
cin >> N;
vector<string> a(N);
for (auto& e: a) {
cin >> e;
}
int dr[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dc[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
auto check = [&](int r, int c) {
for (int dir = 0; dir < 8; dir++) {
int rr = r + dr[dir] * 5;
int cc = c + dc[dir] * 5;
if (rr < 0 || rr >= N || cc < 0 || cc >= N) continue;
int cnt = 0;
for (int k = 0; k < 6; ++k) {
int nr = r + dr[dir] * k;
int nc = c + dc[dir] * k;
cnt += a[nr][nc] == '.';
}
if (cnt <= 2) return true;
}
return false;
};
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (check(i, j)) {
cout << "Yes\n";
return 0;
}
}
}
cout << "No\n";
}
D - Sequence Query
더보기
풀이
- 멀티셋으로 관리
- 1 쿼리
- 멀티셋에 삽입
- 2 쿼리
- lower bound 부터 최대 k 번 뒤로 iterate
- 3 쿼리
- upper bound 의 prev 부터 최대 k 번 앞으로 iterate
코드
- 시간복잡도: $O(QlogQk)$
#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 Q;
cin >> Q;
multiset<long long> a;
while (Q--) {
long long q, x, k;
cin >> q >> x;
if (q == 1) {
a.insert(x);
} else if (q == 2) {
cin >> k;
auto it = a.upper_bound(x);
if (it == a.begin()) {
cout << "-1\n";
continue;
}
it = prev(it);
while (true) {
if (--k == 0) {
cout << *it << '\n';
break;
}
if (it == a.begin()) break;
it = prev(it);
}
if (k) {
cout << "-1\n";
continue;
}
} else {
cin >> k;
auto it = a.lower_bound(x);
if (it == a.end()) {
cout << "-1\n";
continue;
}
while (true) {
if (it == a.end()) break;
if (--k == 0) {
cout << *it << '\n';
break;
}
it = next(it);
}
if (k) {
cout << "-1\n";
continue;
}
}
}
}
E - Putting Candies
더보기
풀이
- ans[i]: i 번후 접시위 사탕 수라고 정의하면
- $ans[i] % N == ans[i + p] % N$ 인 $1 <= p <= N$ 이 존재
- $ans[i] % N$ 은 그 때 $p$ 주기를 갖는다, 즉 더해지는 수가 $p$ 주기를 가지고 반복된다
코드
- 시간복잡도: $O(N)$
#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);
long long N, K;
cin >> N >> K;
vector<long long> a(N);
for (auto& e: a) {
cin >> e;
}
vector<long long> v(N + 1, 0), v2(N + 1, 0), cnt(N, 0);
cnt[0] = 1;
long long idx = -1, p = -1;
for (int i = 1; i <= N; ++i) {
v[i] = v[i - 1] + a[v2[i - 1]];
v2[i] = v[i] % N;
if (++cnt[v2[i]] == 2) {
auto it = find(v2.begin(), v2.begin() + i, v2[i]);
idx = it - v2.begin();
p = i - idx;
break;
}
}
long long answer = 0;
if (K <= idx) {
answer = v[K];
} else {
K -= idx;
answer += v[idx] + (K / p) * (v[idx + p] - v[idx]);
K %= p;
for (int i = 0; i < K; ++i) {
answer += a[v2[idx + i]];
}
}
assert(p >= 1);
cout << answer << '\n';
}
728x90
'PS > Atcoder' 카테고리의 다른 글
| [앳코더] AtCoder Beginner Contest 240(비기너 240) 풀이 (0) | 2022.02.22 |
|---|
