[앳코더] AtCoder Beginner Contest 241(비기너 241) 풀이

https://atcoder.jp/contests/abc241/tasks

Tasks - AtCoder Beginner Contest 241（Sponsored by Panasonic）

 

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';
}