2024년 9월 셋째 주 PS 일지

9/16 월요일

17398 통신망 분할

 

9/17 화요일

17709 Toilets: jaewoo2009가 추천해 줘서 시도했다가 일주일 넘게 잡고 있었던 문제입니다. 오랫동안 고민해서 해결한 문제인 만큼 어려웠고 풀이를 정리해 보고자 합니다.

 

서브테스크 1, 2

남자를 -1, 여자를 1로 정하고 뒤에서부터 누적 합을 구해줍니다. 그리고 2개씩 묶어서 살펴보는데 만약 그 2개의 사람이 누적 합에 추가돼서 만약 0보다 작아진다면 (2개의 사람이 모두 남자인 경우만 해당) 가장 가까운 여자와 자리를 바꿔주면 됩니다. 이런 식으로 해주면 $O(N)$ 안에 해결해 줄 수 있습니다.

 

서브테스크 3

조금만 생각해 보면 2개씩 묶어서 볼 필요는 없고 그냥 누적 합이 -1 미만인지만 확인해 주면 된다는 것을 알 수 있습니다.

누적 합이 가장 작은 지점에서 이보다 뒤에서 아무리 남자나 여자를 이동시켜봤자 누적 합이 바뀌지는 않습니다. 따라서 이를 양수로 만들어주기 위해서는 앞에 있는 여자를 뒤로 이동시켜 주거나 뒤에 있는 남자들을 앞으로 이동시켜 줄 수 있습니다. 근데 인덱스를 기준으로 봤을 때 두 경우는 동일하다는 것을 알 수 있고 불만도의 최댓값은 동일하다는 것을 알 수 있습니다. 그래서 결국 답은 여기서 나온 최대 불만도보다 작을 수 없습니다.

그러므로 남자들을 맨 앞으로 이동시켜 줄 것입니다. 그러면 이 지점보다 앞에 있는 지점들은 누적 합이 -1보다 작을 경우가 없습니다. (누적 합이 최소인 지점을 골랐으므로). 또한 뒤의 남자들을 이동시켜 줄 때 뒤에서부터 나오는 남자들을 차례대로 다 보내준다면 뒤에서도 누적 합이 -1보다 작을 경우가 없습니다. 결국 답은 이 지점에서 앞으로 보낼 남자의 수가 되고 이것은 $-prefix\_sum-1$입니다. 

결국 전체 배열에서 누적 합이 최소가 되는 지점을 잘 찾아주시기만 하면 되는 문제입니다.

 

#include <bits/stdc++.h>
#define int long long

using namespace std;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int N, M, K, sm = 0, cur = 0, mn = 0, smn;
    vector<pair<string, int>> inp;
    string S;

    cin >> N >> M;
    while (M--) {
        cin >> S >> K;
        inp.push_back({S, K});
    }

    reverse(inp.begin(), inp.end());
    for (pair<string, int> i : inp) {
        S = i.first, K = i.second, cur = 0, smn = 0;

        for (int i = S.size() - 1; i >= 0; i--) {
            cur += (S[i] == 'F' ? 1 : -1);
            smn = min(smn, cur);
        }

        mn = min({mn, sm + smn, sm + cur * (K - 1) + smn});
        sm += cur * K;
    }

    if (sm < 0) cout << -1;
    else cout << max(0ll, -mn - 1);
}

 

EPIC Institute of Technology Round Summer 2024 (Div. 1 + Div. 2)

KUHYAKU와 버추얼을 돌았습니다.

A, B, C는 쉬웠고 D는 DP 문제라는 것만 알면 풀리는 문제였습니다. 

나름 만족스러운 블루 상위 퍼포가 나왔습니다.

 

9/18 수요일

9248 Suffix Array: 접미사 배열과 LCP 배열에 대해 배웠습니다. (클래스 7 밀기)

11479 서로 다른 부분 문자열의 개수 2

9249 최장 공통 부분 문자열

10254 고속도로: 회전하는 캘리퍼스 알고리즘에 대해 배웠습니다. (클래스 7 밀기)

1017 소수 쌍 (클래스 7 밀기)

1671 상어의 저녁식사 (클래스 7 밀기)

16903 수열과 쿼리 20 (클래스 7 밀기)

2912 백설공주와 난쟁이 (클래스 7 밀기)

8462 배열의 힘 (클래스 7 밀기)

3878 점 분리 (클래스 7 밀기)

11868 님 게임 2: 스프라그 그런디 정리에 대해 배웠습니다.

16895 님 게임 3

13034 다각형 게임 (클래스 7 밀기)

16877 핌버 (클래스 7 밀기)

 

9/19 목요일

14959 Slot Machines (클래스 7 밀기)

16367 TV Show Game (클래스 7 밀기)

 

클래스 6, 7을 밀면서 느낀 소감

 

실력을 늘리고자 클래스 6과 7을 밀기로 다짐했었습니다. 아무래도 솔브닥에서 정해준 좋은 문제들이니깐 적어도 이 문제들은 모두 풀어봐야 하지 않을까? 라는 생각으로요.

여러 문자열과 기하 알고리즘들을 새롭게 배웠습니다. 사실 이 알고리즘들은 KOI 등에 잘 출제되지도 않아서 고등학생인 저에게 그다지 중요하지는 않으나 금장을 따기 위해선 필수적이라 배웠습니다. 그래도 나중에 기하나 문자열 문제들을 더 풀지는 않을 것입니다.

다른 클래스 문제들은 이전에 이미 풀어봤고 새롭게 푼 문제들은 쉽게 풀려서 막 스트레스받고 그러진 않았는데 그래서인가 실력 상승은 별로 안 된 것 같습니다.

그래서 FFT 같은 더 새로운 알고리즘이 나오는 클래스 8과 그 이상은 일부러 금장을 따려고 문제를 풀지는 않고 앞으로는 USACO 문제나 알고리즘 분류 들어가서 1페이지 문제 밀기 등으로 여러 문제를 풀어볼 예정입니다.

 

9/20 금요일

USACO January 2005 Contest Gold 

2414 게시판 구하기: 이분 매칭인 것을 눈치채지 못했고 태그를 깐 후에도 쉽게 풀이를 찾지 못했습니다. 콰니그의 정리에 대해 알게 된 문제입니다.

2276 물 채우기: 쉬운 줄 알았는데 생각하기 꽤 어려웠던 그래프 탐색 문제였습니다.

1988 낮잠 시간

 

9/21 토요일

ABC 372

ABC를 쳤습니다. F를 보는데 행렬 거듭제곱을 이용한 풀이밖에 떠오르지 않아 결국 5솔로 마무리했습니다.

 

USACO December 2004 Contest Gold

1667 지민이의 테러 Season Ⅵ: 이전에 풀었던 문제의 하위 호환 버전이였습니다.

7041 Cow Ski Area: 분명 SCC 기본 + 1은 아닌데...

7042 Dividing the Path: KUHYAKU의 풀이를 듣고 풀었습니다.

 

9/22 일요일

USACO March 2005 Contest Gold

1745 숨기: 플로우 + 파라메트릭 서치를 이용해서 푸는 문제라는 것은 빨리 알고 구현했는데 자꾸 반례가 생겨서 결국 大 KUHYAKU의 도움을 받아서 풀었습니다.

27006 Space Elevator

27007 Yogurt Factory

 

USACO October 2005 Contest Gold

2198 버스와 손님: 젠장 또 KUHYAKU

27000 Skiing