hckim

풀이

• 각 키와 그에 맞는 도어에 대해 키 -> 도어 순서로 되어있지 않으면 NO

코드

#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--) {
        string s;
        cin >> s;
        set<int> key;

        bool answer = true;
        for (auto e: s) {
            if ('a' <= e && e <= 'z') {
                key.insert(e);
            } else {
                if (!key.count(e - 'A' + 'a')) {
                    answer = false;
                    break;
                }
            }
        }

        if (answer) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
}

풀이

• 피보나치 수열이 증가수열이므로 내림차순으로 순열을 정렬하면 뭔가 되지 않을까부터 생각
• 맨 뒤의 1을 앞으로 하나씩 옮기면 된다.
• $[N, N - 1, ... 2, 1], [N, N - 1, ..., 1, 2], ..., [1, N, N - 1, ..., 2]$

코드

#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<int> a(N - 1);
        for (int i = 0; i < N - 1; ++i) {
            a[i] = i + 2;
        }

        sort(rall(a));
        for (int i = 0; i < N; ++i) {
            bool did = false;
            for (int j = 0; j < N; ++j) {
                if (!did && i == j) {
                    cout << "1 ";
                    did = true;
                } else {
                    cout << a[j - did] << ' ';
                }
            }
            cout << '\n';
        }

    }
}

풀이

• 길이 1, 2, ..., N 부분수열에 대해서 길이에 대한 maxSum 값을 구해둔다
• 그 maxSum 부분 수열의 원소들에 최대한 X 를 더하는게 이득
• 곱하는 위치수 k 에 대한 길이 d 부분수열의 합의 최댓값은 $maxSum[d] + min(d, k), * X$  

코드

• 시간복잡도: $O(N^2)$

#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, X;
        cin >> N >> X;
        vector<long long> a(N);
        vector<long long> pa(N, 0);
        for (int i = 0; i < N; ++i) {
            cin >> a[i];
            pa[i] = a[i];
            if (i) pa[i] += pa[i - 1];
        }

        vector<long long> maxSum(N + 1, -1e18);

        maxSum[0] = 0;
        for (int d = 1; d <= N; ++d) {
            long long maxSum_ = -1e18;
            for (int i = 0; i + d - 1 < N; ++i) {
                long long sum = pa[i + d - 1];
                if (i) sum -= pa[i - 1];
                maxSum_ = max(maxSum_, sum);
            }
            maxSum[d] = maxSum_;
        }

        for (int k = 0; k <= N; ++k) {
            long long answer = 0;
            for (int d = 0; d <= N; ++d) {
                answer = max(answer, maxSum[d] + 1LL * min(d, k) * X);
            }
            cout << answer << ' ';
        }
        cout << '\n';
    }
}

풀이

• 각 칸에 대해서 가장 마지막으로 행한 operation 의 번호를 매기고 모든 칸에서 distinct 한 operation 번호의 수를 p 라 하면 각 p 개의 그룹에 색의 개수 k 개씩 칠하는 경우가 있으므로 답은 $k^p$ 이다
• operation 의 역순으로 생각해보자
  • 이전에 칠해진거 밑에 칠해진다
  • 다 채워진 뒤에는 더 이상 칸들의 마지막 operation 번호에 변화가 있을 수 없다.
• $r[x], c[y]$ 각각 x행/y열 이 이미 다른 번호에의해 칠해졌는가 라고 정의하면
  • 지금 수행할 operation 의 x, y 에 대해
    • r[x] = true && c[y] = true 이면 변화가 없음
    • 하나라도 false 면 가능
    • 또한 전체행이나 전체열이 채워지면 더 해볼 필요가 없음

코드

• 시간복잡도: $O(Q)$
• 주의할점: testcase 에 대한 n, m 의 제한이 없어서 testcase 마다 vector r, c 를 잡으면 이거때문에 시간초과남

#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;

    vector<int> r(2e5 + 1, -1), c(2e5 + 1, -1);
    while (TC--) {
        int N, M, K, Q;
        cin >> N >> M >> K >> Q;

        vector<pair<int, int> > operation(Q);
        for (int i = 0; i < Q; ++i) {
            cin >> operation[Q - 1 - i].first >> operation[Q - 1 - i].second;
        }

        int rr, cc;
        rr = cc = 0;
        long long answer = 1;
        long long MOD = 998244353;
        for (auto [x, y]: operation) {
            if (rr == N || cc == M) break;
            if (r[x] == TC && c[y] == TC) continue;
            answer = answer * K % MOD;
            if (r[x] != TC) r[x] = TC, rr++;
            if (c[y] != TC) c[y] = TC, cc++;
        }

        cout << answer << '\n';
    }
}

풀이

• 움직이는 칸의 범위는 처음 R, 처음 D 를 duplicate 한 칸들로 둘러 싸여있는 형태
  • 한 종류만 있는 경우에는 그냥 N
• 칸 범위 구하기
  1. 초기 칸 수
  2. 아래로 한칸씩 내릴때(duplicate D) 추가되는 칸 수(정사영 내렸을때 칸 수) * (내릴 수 있는 칸 수)
     • 추가되는 칸 수 계산할 때 처음 R, D 에 유의
  3. 아래로 다 내린상태에서 옆으로 옮길때 추가되는 칸 수 * 옆으로 옮길수 있는 칸 수

코드

• 시간복잡도: $O(s.size())$

#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;
        cin >> N;
        string s;
        cin >> s;

        long long r, d, fr, fd;
        r = d = fr = fd = 0;

        for (int i = 0; i < s.size();) {
            if (s[i] == 'R') {
                int tmp = 0;
                while (i < s.size() && s[i] == 'R') ++tmp, ++i;
                r += tmp;
                if (fr == 0) fr += tmp;
            } else {
                int tmp = 0;
                while (i < s.size() && s[i] == 'D') ++tmp, ++i;
                d += tmp;
                if (fd == 0) fd += tmp;
            }
        }

        if (r == 0 || d == 0) {
            cout << N << '\n';
            continue;
        }
        
        long long answer = 0;
        if (s[0] == 'D') {
            answer = (r + d + 1);
            answer += (r + 1) * (N - d - 1);
            answer += (d - fd + 1 + N - d - 1) * (N - r - 1);
        } else {
            answer = (r + d + 1);
            answer += (r - fr + 1) * (N - d - 1);
            answer += (d + 1 + N - d - 1) * (N - r - 1);
        }
        cout << answer << '\n';
    }
}