hckim

풀이

• 배열 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';
}

풀이

• 멀티셋에 가진 누들 길이 다 넣고 플랜 진행하면서 없으면 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";
 
}

풀이

• 한 칸에 대해서, 그 칸을 시작으로 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";
}

풀이

• 멀티셋으로 관리
• 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;
            }
        }
    }
}

풀이

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

풀이

• $y = 0$ 에 도달할 수 없는 점이 존재 하려면 세 점중 y 값이 최소가 아닌 두 점이 이루는 변이 x 축과 평행해야 하고 그 변의 길이가 답이 된다

코드

#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 TC; cin >> TC;
    while (TC--) {
 
        vector<pair<long long, long long> > p(3);
        for (int i = 0; i < 3; ++i) {
            cin >> p[i].first >> p[i].second;
        }
 
        if (p[0].second > p[1].second) swap(p[0], p[1]);
        if (p[0].second > p[2].second) swap(p[0], p[2]);
 
        long double answer = 0.0;
 
        if (p[1].second == p[2].second) {
            answer = abs(p[1].first - p[2].first);
        }
 
        cout.precision(9);
        cout << fixed << answer << '\n';
    }
}

풀이

• $k = n$ 일 때 힘의 합은 $k$
• $k = n - 1$ 일 때 서로 다른 두개를 합치면 합은 이전 합과 같고, 같은 두개 합치면 이전합 + 1 
• 같은 게 있으면 같은 것들 부터 합치자

코드

#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 TC; cin >> TC;
    while (TC--) {
        int N;
        cin >> N;
        map<int, int> a;
        for (int i = 0; i < N; ++i) {
            int num;
            cin >> num;
            ++a[num];
        }
 
        int d = 0;
        for (auto [num, cnt]: a) {
            if (cnt >= 2) d += cnt - 1;
        }
 
        vector<int> answer;
        int k = N;
        for (int i = 0; i < N; ++i) {
            if (d) {
                answer.push_back(k);
                --k;
                d--;
            } else {
                answer.push_back(k);
            }
        }
 
        reverse(all(answer));
 
        for (auto e:answer) {
            cout << e << ' ';
        }
        cout << '\n';
        
    }
}

풀이

• 제일 큰 distinct 원소부터 매칭이 되면 넘어가고 수를 추가해야되면 그 수만큼 추가해준다

코드

• 시간복잡도: $O(NlogN)$

#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 TC; cin >> TC;
    while (TC--) {
        long long N, X;
        cin >> N >> X;
        map<long long, long long> m;
        for (int i = 0; i < N; ++i) {
            int num;
            cin >> num;
            ++m[num];
        }
 
        int answer = 0;
        for (auto rit = m.rbegin(); rit != m.rend(); ++rit) {
            if (rit -> second == 0) continue;
            if (rit -> first % X == 0) {
                auto it = m.lower_bound(rit -> first / X);
                if (it != m.end() && it -> first == rit -> first / X && it -> second > 0) {
                    int tmp = min(rit -> second, it -> second);
                    it -> second -= tmp;
                    rit -> second -= tmp;
                }
 
                if (rit -> second > 0) {
                  answer += rit -> second;
                  rit -> second = 0;
                } 
            } else {
                answer += rit -> second;
            }
        }
        cout << answer << '\n';
    }
}

풀이

• operation 해도 각 문자들의 parity 가 유지되므로 홀수 개수인 문자가 존재하면 불가능하다
• 문자열 $c_1c_2c_3...$ 에 $c_3, c_2, c_1$ 을 뒤에 넣으면 $c_1c_2c_3c_3c_2c_1c_3c_2c_1...$ 로 만들 수 있다
• 앞에 부분은 tandem repeat 으로 빼놓고 뒷부분은 원래 문자열의 앞부분을 reverse 한것과 같다.
• 이 작업으로 문자열 뒷부분이 원래 문자열을 정렬한 상태로 두면 그 문자열은 순서대로 각 문자의 개수만큼 tandem repeat 을 이룬다
  • $c_1c_1c_2c_2c_2c_2c_3c_3...$

코드

• 시간복잡도: $O(N^2)$
  • 정렬하는데 각 원소마다 reverse 2번: $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);
 
    int TC; cin >> TC;
    while (TC--) {
        int N;
        cin >> N;
        vector<long long> a(N);
        map<int, int> cnt;
        for (auto& e: a) {
            cin >> e;
            ++cnt[e];
        }
        bool no = false;
        for (auto e: cnt) {
            if (e.second & 1) {
                no = true;
                break;
            }
        }
 
        if (no) {
            cout << "-1\n";
            continue;
        }
 
        vector<long long> sortedA(a);
        sort(all(sortedA));
 
        int start = 0;
        vector<pair<int, int> > operation;
        vector<int> t;
 
        auto swapWithFirst = [&](int i) {
            if (i == 0) return;
            for (int j = 0; j <= i; ++j) {
                operation.push_back({start + j + i + 1, a[j]});
            }
            reverse(a.begin(), a.begin() + i + 1);
            t.push_back(i + 1 << 1);
            start += i + 1 << 1;
        };
        for (int i = N - 1; i > 0; --i) {
            if (a[i] != sortedA[i]) {
                auto it = find(a.begin(), a.begin() + i, sortedA[i]);
                if (it != a.begin()) {
                    swapWithFirst(it - a.begin());
                }
                swapWithFirst(i);
            }
        }
 
        for (auto e: cnt) {
            t.push_back(e.second);
        }
 
        cout << operation.size() << '\n';
        for (auto [p, c]: operation) {
            cout << p << ' ' << c << '\n';
        }
        cout << t.size() << '\n';
        for (auto e: t) {
            cout << e << ' ';
        }
        cout << '\n';
 
    }
}

풀이

• 병자 후보를 set 으로, 0 l r 1 쿼리를 세그먼트 트리로 관리
• t = 0 
  • x = 0
    • set 에서 l 부터 r 까지 범위에 있는것들 다 지움 ($O(NlogN)$)
  • x = 1
    • l 노드 값 min(t[N + l], r) 로 업데이트
• t = 1
  • 병자 후보에 없으면 병 안걸림
  • 병자 후보 set 에서의 j 의 위치 앞, 뒤에 있는 후보를 l, r 이라고 하면
  • l + 1, j 구간의 오른쪽 구간 최소값이 뒤 후보값인 r 보다 작으면 그 구간에 j가 1을 결정하므로 병자임을 확정할 수 있다. 그 외 경우엔 여러 원소가 있으므로 결정할 수 없다.

코드

• 시간복잡도: $O(NlogN + QlogN)$

#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, Q;
    cin >> N >> Q;
    
    set<int> can;
    for (int i = 0; i < N; ++i) can.insert(i);
    vector<int> t(2 * N, 1e9);
    auto update = [&](int p, int val) {
        for (t[p += N] = val; p > 1; p >>= 1) t[p >> 1] = min(t[p], t[p ^ 1]);
    };
    auto query = [&](int l, int r) {
        int ret = 1e9;
        for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
            if (l & 1) ret = min(ret, t[l++]);
            if (r & 1) ret = min(ret, t[--r]);
        }
        return ret;
    };
 
    while (Q--) {
        int t2, l, r, x, j;
        cin >> t2;
        if (t2 == 0) {
            cin >> l >> r >> x; --l; --r;
            if (x == 0) {
                for (auto it = can.lower_bound(l); it != can.end() && r >= *it;) {
                    can.erase(it);
                    it = can.lower_bound(l);
                }
            } else {
                update(l, min(t[l + N], r));
            }
        } else {
            cin >> j; --j;
            if (!can.count(j) || !can.size()) {
                cout << "NO\n";
                continue;
            }
 
            int l = 0, r = N;
            auto it = can.lower_bound(j);
            if (it != can.begin()) l = *prev(it) + 1;
            if (next(it) != can.end()) r = *next(it);
 
            cout << (query(l, N) < r ? "YES\n" : "N/A\n");
        }
    }
}