ALOHA 여름방학 고급반 1주차

A. https://www.acmicpc.net/problem/27739

 

제곱이 도는 제한이니 길이 K인 구간을 고르는 경우 $O(N)$개를 각각 $O(N)$ 내지 $O(N\log N)$ 정도에 풀면 되고, 고른 구간을 정렬하고 좌표압축 비스무리하게 하면 풀 수 있다. 고려해야 하는 케이스는 왼쪽으로 쭉 늘리기 / 오른쪽으로 쭉 늘리기 / (가능하다면) 구간 전체 다 쓰기 세 가지인데, 처음에는 첫 두 가지 제대로 생각 못해서 좀 절었다. 구현이 좀 귀찮앗음..

 

#include <bits/stdc++.h>
using namespace std;
 
int N, K, A[2020];
int main() {
    cin.tie(nullptr)->sync_with_stdio(0);
 
    cin >> N >> K;
    for (int i = 1; i <= N; i++) cin >> A[i];
    int ans = 0;
    for (int l = 1, r = K; r <= N; l++, r++){
        vector<int> B;
        for (int i = l; i <= r; i++) B.push_back(A[i]);
        sort(B.begin(), B.end());
        B.erase(unique(B.begin(), B.end()), B.end());
        int nl = l-1, nr = r+1, bef = 1e9;
        for (; nl and A[nl] < bef; bef = A[nl--]);
        bef = 0;
        for (; nr <= N and A[nr] > bef; bef = A[nr++]);
        int now = B.size();
        if (l > 1) now = max<int>(now, B.end() - upper_bound(B.begin(), B.end(), A[l-1]) + l-nl-1);
        if (r < N) now = max<int>(now, lower_bound(B.begin(), B.end(), A[r+1]) - B.begin() + nr-r-1);
        if (1 < l and r < N and A[l-1] < B[0] and B.back() < A[r+1]) now = nr - nl - 1;
        ans = max(ans, now);
    }
    cout << ans;
}

 

B. https://www.acmicpc.net/problem/30484

 

문자열 자체의 inversion / 반복되어 생기는 inversion을 고려하면 식 정리가 깔끔하게 된다. 알파벳 문자열이라 inversion을 단순하게 구해도 된다. 오버플로 처리가 쪼금 귀찮아 보여서 파이썬 썼다.

 

s = input().strip()
N = int(input())
cnt = [0]*30
inv = aa = 0
for c in s:
    for i in range(ord(c)+1, ord('z')+1):
        inv += cnt[i-ord('a')]
    cnt[ord(c)-ord('a')] += 1
for c in s:
    for i in range(ord(c)+1, ord('z')+1):
        aa += cnt[i-ord('a')]
print((inv * N + N*(N-1)//2 * aa) % 1000000007)

 

C. https://www.acmicpc.net/problem/31572

 

풀기 싫게 생긴 데 비해 할 수 있는 일이 몇 가지 없어서 풀 만 했다.

 

count_pair를 $\lfloor \frac{N}{2} \rfloor +1$번, find_character는 1번만 쓸 수 있다. 팰린드롬인지 판별하려면 적어도 $\lfloor \frac{N}{2} \rfloor$개의 숫자 쌍을 비교해야 하니, 어떻게든 count_pair로 비교를 수행해야 한다고 유추할 수 있다. count_pair의 인자로 비교할 두 위치 $i$, $N-i-1$과 임의의 다른 위치 $x$를 넘겼다고 생각해 보자. $S_x$와 관계 없이 반환값이 $3$이라면 $S_i = S_{N-i-1}$이고, $0$이라면 $S_i \neq S_{N-i-1}$이니 반환값이 $1$일 때만 잘 처리하면 된다. 이를 위해 find_character를 잘 활용해야 할 것이다.

 

find_character는 수 하나와 다른 여러 수들을 비교하므로, count_pair에서 넘길 다른 위치 $x$를 모두 통일하자. 사고의 편의를 위해 수열의 길이가 홀수인 상황을 먼저 생각하면, 비교할 필요 없는 수열의 가운데 인덱스를 $x$로 쓸 수 있다. count_pair의 반환값이 $1$인 모든 $(i, N-i-1)$ 쌍에 대해 $S_i \neq S_x$이고 $S_{N-i-1} \neq S_x$라면 $S_i = S_{N-i-1}$이므로, find_character를 통해 반환값이 $1$인 쌍을 한꺼번에 조사하여 팰린드롬 여부를 판단할 수 있다.

 

수열의 길이가 짝수라면 $S_x = S_{N-x-1}$인지도 판단해야 한다. $(x, N-x-1)$ 쌍을 제외한 다른 쌍들은 같은 방법으로 조사할 수 있으며, count_pair를 2번 더 사용할 수 있다. 조사를 마친 상태에서 $x$과 $N-x-1$이 아닌 임의의 인덱스 $t$를 골랐을 때 $S_t = S_{N-t-1}$를 만족하며, $S_t$와 $S_x$가 같은지 여부도 count_pair의 반환값을 통해 알고 있다. 따라서 $S_t$와 $S_x$가 같을 때와 다를 때로 케이스를 나눠 count_pair를 적절히 쓰면 $S_x$와 $S_{N-x-1}$ 또한 비교할 수 있어 문제를 풀 수 있다. 

 

#include <vector>
 
extern int count_pair(int, int, int);
extern int find_character(int, std::vector<int>);
 
int guess_palindromicity(int N) {
    using namespace std;
    vector<int> v;
    for (int i = 1; i < N/2; i++){
        int r = count_pair(0, i, N-i-1);
        if (r == 0) return 0;
        else if (r == 1) v.push_back(i), v.push_back(N-i-1);
    }
    if (v.size()){
        if (find_character(0, v)) return 0;
        return count_pair(v[0], 0, N-1) == 1 and count_pair(v[0], N-v[0]-1, N-1) == 1;
    }
    else
        return count_pair(0, N-1, 1) == 3;
}

 

D. https://www.acmicpc.net/problem/12430

 

딱 봐도 그리디한 조건으로 정렬해서 냅색 돌리면 될 것처럼 생겼는데.. 조건 찾는 데 시간이 오래 걸렸다. P+S 오름차순으로 정렬하면 exchange argument 느낌으로 최적해가 될 것 같다는 믿음을 가지고 짰다. 

 

이 문제처럼 가능/불가능을 따지는 냅색은 뒤부터 업데이트하면 공간을 줄일 수 있고, 비트셋으로 최적화할 수 있다는 사실은 잘 알려져 있다. T <= 100인데 $\sum N$ 제한이 없어 비트셋 써야 하나 싶었는데 없어도 빨리 잘 돌아간다. 아마 최대 데이터가 안 들어있지 않을까?

 

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
 
int N, dp[101010];
void solve(){
    cin >> N;
    memset(dp, 0, sizeof dp);
    vector<pii> v(N);
    for (auto&[p,s] : v) cin >> p >> s;
    sort(v.begin(), v.end(), [](pii a, pii b){
        return a.first+a.second < b.first+b.second;
    });
    dp[0] = 1;
    for (auto[p,s] : v){
        for (int i = p+s; i >= s; i--)
            dp[i] |= dp[i-s];
    }
    for (int i = 101000;;i--){
        if (dp[i]){
            cout << i << '\n';
            return;
        }
    }
}
 
int main() {
    cin.tie(nullptr)->sync_with_stdio(0);
 
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++){
        cout << "Case #" << i << ": ";
        solve();
    }
}

 

E. https://www.acmicpc.net/problem/23096

 

아무생각안든다. 너무어려움