20/04/15 USACO 2019 December Contest Silver 유사코 실버

https://www.acmicpc.net/category/detail/2145

USACO 2019 December Contest Bronze

브론즈 문제는 N이 적어 완탐문제가 많았다.

 

MooBuzz 18265

https://www.acmicpc.net/problem/18265

18265번: MooBuzz

$1$부터 숫자를 말할껀데 $3, 5$의 배수는 숫자대신 Moo를 말한다. 이렇게 말할때 $N(1\le N \le 10^9)$번째 불리는 숫자가 무엇인지 출력하면 된다. 

두가지 풀이가 있다. 첫번 째로 (1 , 2, M, 4, M, M, 7, 8, M, M, 11, M, 13, 14, M)이렇게가 계속 반복이되는 것을 이용해 

ll arr[] = { 1,2, 4, 7,8,11,13,14 };//8개 반복
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    ll n;
    cin >> n;
    cout << (n - 1) / 8 * 15 + arr[(n - 1) % 8];
}

수학적으로 풀어도 된다. 

혹은 이분탐색을 이용해 풀어도 된다. 

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    ll l = 1;
    ll r = LNF/2;
    while (l <= r) {//숫자의 갯수
        ll mid = (l + r) / 2;
        if (mid - (mid / 5 + mid / 3 - mid / 15) >= n)//전체 갯수중  Moo가 되는 애들 수를 빼줌 
            r = mid - 1;
        else
            l = mid + 1;
    }
    //r 에 n번쨰 숫자 의 값 왼쪽게 들어가게 됨
    cout << r + 1;
}

 

Meetings 18266

https://www.acmicpc.net/problem/18266

18266번: Meetings

오우... 내 풀이가 잘못된거인지 모르겠지만 뭔가 복잡한? 번거로운 문제였다. 정렬 디따 해야됨

1차원 선 위 $0$과 $L ( 1\le L \le 10^9)$에 목적지가 있다.

$N (1\le N \le 5 * 10^4)$개의 소가 $w_i (1\le w_i \le 10^3)$의 몸무게와  $x_i (1\lt x_i \lt L)$ 의 좌표 그리고 $d_i$(1: 오른쪽 , -1 : 왼쪽)방향을 가지고 있다.

소들은 이동하다가 만나면 서로의 방향을 바꾼다 즉 -> <- 이렇게 오다가 만나면 <- -> 방향으로 돌아서서 이동 한다는 것이다. 이건 서로 가던방향으로 가고 무게만 바꾼다고 이해해도 된다.  이런 만남은 0.5 같은 정수가아닌 좌표에서 발생 할 수도 있다. 

목적지인 $0, L$에 들어간 소들의 몸무게가 전체 소 몸무게 절반 이상이 될 때 이때 까지 소들간에 접촉이 몇번 있었는지 출력하는 문제이다. 요즘같은 시국에 사회적 거리두기를 안하다니 큰일날 소들이다. 

코드로 보면 다음과 같다.

int N, M;
vector<pair<pii, int>> v;//좌표 순으로 정렬하기 위함
vector<int> l, r, l1;//l:  왼쪽에 도달할때 시간, r: 오른쪽에 도달할때 시간 , ll 왼쪽으로 가는 애들의 시작좌표
vector<pii> vc;//0과 L에 들어가는 시간과 무게 넣어서 정렬
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> N >> M;
    int ws = 0;//무게합
    int leftcou = 0, rightcou = 0;
    for (int i = 1; i <= N; i++) {
        int a, b, c;
        cin >> a >> b >> c;//무게, 좌표 , 속도
        ws += a;
        v.push_back({ {b,a},c });//아 속도는 1,-1만 주어짐 30분 고민하고 이제봤네 아!
    }
    sort(v.begin(), v.end());//좌표 순으로 정렬
    for (int i = 0; i < N; i++) {
        int a, b, c;
        a = v[i].first.second;
        b = v[i].first.first;
        c = v[i].second;
        if (c == 1) {
            r.push_back(M - b);//이 시간뒤에 오른쪽에 도착
        }
        else {
            l.push_back(b);//이 시간뒤에 왼쪽에 도착
            l1.push_back(b);//왼쪽으로 갈 애들이 어디있는지 넣기
        }
    }
    sort(l1.begin(), l1.end());
    sort(r.begin(), r.end());
    for (int i = 0; i < l.size(); i++) {
        vc.push_back({ l[i], v[i].first.second });//시간 , 무게 넣기
    }
    for (int i = 0; i < r.size(); i++) {
        vc.push_back({ r[i], v[N-1-i].first.second });
    }
    sort(vc.begin(), vc.end());
    int stem = 0;//임시 무게
    ll ans = 0;//정답
    int  ti = 0;//조건을 만족하기위해 걸리는 
    while (stem * 2 < ws) {
        stem += vc[ti].second;
        ti++;
    }
    ti = vc[ti - 1].first;// 다 넣는데 걸리는 시간
    for (int i = 0; i < N; i++) {
        int b = v[i].first.first;//위치
        int c = v[i].second;
        if (c == 1) {//오른쪽으로 갈테야
            ans += upper_bound(l1.begin(), l1.end(), b + 2 * ti) - lower_bound(l1.begin(), l1.end(), b);
        }
    }
    cout << ans;
}

엄청난 정렬을 한다. 정렬과 이분탐색 만으로 이런문제를 만들수 있다니 신기하고 놀랍다. 유사코 푼거중에 제일 어려웠음... 실버 실화냐

 

 

Milk Visits 18267

https://www.acmicpc.net/problem/18267

18267번: Milk Visits

LCA문제인줄 알고 달려 들었으나 틀리고 쉬운 풀이로 꺾음 물론 LCA로 해도 맞아야되는데 왜 틀린지 모르겠음;;

$N (1\le N \le 10^5)$개의 노드를 가진 트리를 주고 노드는 $H , G$중 하나의 성분을 갖는다.

그리고 $M (1\le M \le 10^5)$개의 쿼리를 주는데 $A, B, C$ 를 입력으로 준다. $A$ 노드에서 $B$노드로 갈때 $C(H, G)$ 를 방문할수 있는지를 출력 하면 된다. 

연결이 트리 형식이고 2개로만 나눠지니 위 그림과 같은 형식으로 나뉘게 될꺼다. 같은 종류 끼리 엮여 있으면 같은 컴포넌트로 묶어 준다. 그리고 $A$ 와 $B$가 다른 컴포넌트라면 무조건 $H, G$둘다 방문 할수 밖에 없음을 알 수 있다. 같은 컴포넌트라면 1가지 종류만 방문할텐데 그것이 $C$인지 확인 해주면 되는 아주 쉬운 문제이다 .

int N, M;
string s;
vector<int> adj[MAXN];
int arr[MAXN];
 
void dfs(int node, int par, int gi) {
    arr[node] = gi;
    for (int there : adj[node]) {
        if (there == par)continue;
        if (s[there] == s[gi])
            dfs(there, node,  gi);
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> N >> M;
    cin >> s;
    for (int i = 1; i < N; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for (int i = 0; i < N; i++) {
        arr[i] = -1;
    }
    for (int i = 0; i < N; i++) {//같은 컴포넌트로 엮기
        if (arr[i] != -1)continue;//이미 체크 된거면 패쓰
        dfs(i, i, i);
    }
    string ans;
    for (int i = 1; i <= M; i++) {//쿼리 해결
        int a, b;
        char c;
        cin >> a >> b >> c;
        a--, b--;
        if (arr[a] != arr[b]) {//다른 컴포넌트
            ans += "1";
        }
        else {//같은 
            if (s[arr[a]] == c)
                ans += "1";
            else
                ans += "0";
        }
    }
    cout << ans;
}

카트!