USACO 2022 US Open Silver Contest ★

1시간 차에 3번 풀고
2시간 차에 1번이랑 2번 섭태 풀었다.
3시간 반 차까지 2번 풀태를 고민했지만 별 진전이 없어서 승급 컷도 넘겼겠다, 버리고 튀었다.

2시간 만에 2.5문제 풀었다는 것만 봐도, 난이도가 근 3개 contest보다 쉬웠다.

Visits

$1\cdots N$로 이름 붙여진 Bessie의 친구들은 각자 자신의 농장을 소유하고 있다. 각 소 $i$는 소 $a_i(\neq i)$네 농장에 방문하고 싶다.
$1\cdots N$의 순열 $(p_1,p_2,\cdots,p_N)$에 대해 다음을 시행한다:

• $a_{p_i}$가 이미 농장을 떠났다면, $p_i$는 자신의 농장에 남는다.
• 그렇지 않으면, $p_i$는 자신의 농장을 떠나 $a_{p_i}$의 농장에 방문한다. 이러한 방문은 즐거워서 소가 $v_{p_i}(0\le v_{p_i}\le 10^9)$번의 "음메"를 외치게 만든다.

모든 가능한 수열 $p$에 대해 방문 후 "음메"의 최대 횟수를 계산하라.

풀이

함수형 그래프의 사이클 위 최솟값

코드

#include <bits/stdc++.h>
using namespace std; using ll = long long;
#define REP(i,a,b) for (auto i = (a); i <= (b); ++i)
#define mup(x,y) x = min(x,y)

const int N = 1e5+3;
int n, a[N], v[N];
vector<int> adj[N];
bool visited[N];

int calc(int x, int s[]) {
    int a, b, r = 1e9+3;
    for (b=s[a=s[x]]; a!=b; a=s[a], b=s[s[b]]);
    for (a=x; a!=b; a=s[a], b=s[b]);
    b=a;
    do mup(r,v[b]), b=s[b];
    while (a!=b);
    return r;
}

ll dfs(int s) {
    if (visited[s]) return 0;
    visited[s] = true;
    ll sum = v[s];
    for (auto u : adj[s])
        sum += dfs(u);
    return sum;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    ll answer = 0;
    REP(i,1,n) {
        cin >> a[i] >> v[i];
        adj[i].push_back(a[i]);
        adj[a[i]].push_back(i);
    }
    REP(i,1,n) {
        if (visited[i]) continue;
        answer += dfs(i)-calc(i,a);
    }
    cout << answer;
}

Subset Equality

소들은 암호를 연구하고 있다. 이번 연구에서는 원문에 관련없는 문자들을 넣어 해독하기 어렵게 만들었다.
소들은 소문자 'a'에서 'r'까지로 구성된 길이가 최대 $10^5$인 두 개의 문자열 $s$와 $t$를 전송한다. 이 메시지를 이해하기 위해 $Q(1\le Q\le 10^5)$개의 질의가 제공된다. 각 질의는 'a'에서 'r'까지의 소문자의 부분집합을 제공한다.
질의마다 제공된 부분집합의 문자들로만 제한되는 경우 $s$와 $t$가 동일한지 여부를 각 질의에 대해 결정하라.

풀이.

섭태, 나이브

코드.

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for (auto i = (a); i <= (b); ++i)
#define size(x) int((x).size())

const int L = 1e5+3, Q = 1003;
string s, t;
int q;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> s >> t >> q;
    REP(_,1,q) {
        string x; cin >> x;
        bool cs[18] = {0,};
        for (char c : x) cs[c-'a'] = true;
        bool possible = true;
        int i = 0, j = 0;
        while (i < size(s) and j < size(t)) {
            while (i < size(s) and !cs[s[i]-'a']) ++i;
            while (j < size(t) and !cs[t[j]-'a']) ++j;
            if ((i < size(s)) != (j < size(t)) or s[i] != t[j]) {possible = false; break;}
            else ++i, ++j;
        }
        cout << (possible ? "Y" : "N");
    }
}

COW Operations

Bessie는 'C', 'O', 'W' 세 문자만을 포함하는 길이가 최대 $2\cdot 10^5$인 문자열을 찾는다. 그녀는 다음 작업을 통해 문자열을 'C'로 바꾸는 것이 가능한지 궁금하다.

1. 인접한 두 개의 동일한 문자를 삭제한다.
2. 한 문자를 선택해 그 문자와 다른 두 문자로 치환한다. 두 문자의 순서는 아무래도 좋다.

$s$의 부분문자열 $Q(1\le Q\le 2\cdot 10^5)$개에 대해 'C'로 바꾸는 것이 가능한지 출력하라.

풀이..

불변량

코드..

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for (auto i = (a); i <= (b); ++i)

const int N = 2e5+3;
int n, q, cC[N], cO[N], cW[N], l, r;
char s[N];

int C() {return (cC[r]-cC[l-1])%2;}
int O() {return (cO[r]-cO[l-1])%2;}
int W() {return (cW[r]-cW[l-1])%2;}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> &s[1] >> q;
    n = strlen(&s[1]);
    REP(i,1,n) {
        cC[i] = cC[i-1]+(s[i] == 'C');
        cO[i] = cO[i-1]+(s[i] == 'O');
        cW[i] = cW[i-1]+(s[i] == 'W');
    }
    REP(i,1,q) {
        cin >> l >> r;
        if (C() != O() and C() != W()) cout << "Y";
        else cout << "N";
    }
}