---
id: "imported/blog/history/cf/cf-918"
title: "Codeforces Round 918"
description: "Div 4긴 하지만, 처음 해보는 All Solve! 한 해의 마지막 코포로 재밌게 참가했고, 뿌듯했다."
kind: "record"
published: "2023-12-29T00:00:00.000Z"
tags: ["PS","codeforces"]
url: "https://www.readiz.com/blog/history/cf/cf-918/"
markdownUrl: "https://www.readiz.com/blog/history/cf/cf-918/index.md"
---

# Codeforces Round 918

# Codeforces Round 918 Upsolving

- 대회 참가 유무: Y
- 최종 Performance: **1756** (Rank: 229 / 27413)
- Round 링크: [Top](https://codeforces.com/contest/1915) / [Problems](https://codeforces.com/contest/1915/problems)
- 문제별 결과

|  A  |  B  |  C  |  D  |  E  |  F  |  G  |
| :-: | :-: | :-: | :-: | :-: | :-: | :-: |
|  AC |  AC |  AC |  AC |  AC |  AC |  AC |

Div 4긴 하지만, 처음 해보는 All Solve! 한 해의 마지막 코포로 재밌게 참가했고, 뿌듯했다.

## A - Odd One Out

- 문제 링크: <https://codeforces.com/contest/1915/problem/A>
- Score: N/A
- 문제 예상 티어: Bronze IV

몇번 나왔던 `A ^ B ^ C` 구하기 문제. 같은 수는 두번 `XOR`하면 사라진다!

## B - Not Quite Latin Square

- 문제 링크: <https://codeforces.com/contest/1915/problem/B>
- Score: N/A
- 문제 예상 티어: Bronze III

단순 구현 문제. 없는 문자를 찾으면 된다.

## C - Can I Square?

- 문제 링크: <https://codeforces.com/contest/1915/problem/C>
- Score: N/A
- 문제 예상 티어: Silver V

나는 그냥 숫자 다 더한 다음에 `sqrt` 때린 후 제곱해서 원래 숫자가 나오는지로 봤다. 정수의 `sqrt`는 정확하게 계산된다. (제곱수가 맞을 경우)

## D - Unnatural Language Processing

- 문제 링크: <https://codeforces.com/contest/1915/problem/D>
- Score: N/A
- 문제 예상 티어: Silver I

`C`, `V`가 정의되고, `greedy` 하게 단어를 끊어주면 되는 문제. 예외처리 할게 별로 없었다.

## E - Romantic Glasses

- 문제 링크 (E1: Easy): <https://codeforces.com/contest/1915/problem/E>
- Score: N/A
- 문제 예상 티어: Gold I

나는 이게 F보다 쉬웠다. F 풀고 E를 풀었다. 그냥 수식을 보고 있자면 범위 수의 합을 어떻게 빨리 구하지? 할 수 있지만, 코포 문제가 늘 그렇듯 짝수 & 홀수를 나눠 생각해보면 답이 금방 나온다. 차이를 상쇄할 수 있느냐가 포인트.

## F - Greetings

- 문제 링크: <https://codeforces.com/contest/1915/problem/F>
- Score: N/A
- 문제 예상 티어: Platinum V

웰논인 것과는 별개로, solved tier 기준 이런 세그먼트 트리 기초 활용 유형은 `P5` 티어를 받는다. 입력을 선분으로 생각하고, 시작점 기준으로 정렬해서 루프를 시작한다. 그리고 루프는 끝점 기준으로 집어넣으면서(그리디 문제 대표 유형인 Job Scheduling 문제에서 쓰던 방식이다.), 기존의 선분을 몇개 교차하는지 세면 된다. 이 과정에서 `Segment Tree`나 `PBDS`가 필요한데, 나는 `PBDS`로 풀었다. `PBDS`의 `order_of_key` 메서드를 사용하면 쉽게 쿼리당 $O(\log N)$으로 처리가 가능해서 편하다.

## G - Bicycles

- 문제 링크: <https://codeforces.com/contest/1915/problem/G>
- Score: N/A
- 문제 예상 티어: Platinum V

백준에 정확하게 같은 문제가 있고, `P5`를 받았다.

- 주유소 문제: <https://www.acmicpc.net/problem/13308>

정해는 자전거 최소 가격 기준으로 다익스트라에 쓰이는 배열을 확장해서, `dp[1001]` 배열을 만들어서 다익스트라를 사용하는 것이다. 그래서 비용이 1000까지로 제한되어 있고, 이것이 출제 의도로 보인다.

다만, 자전거 가격이 적어도 1이라는 점을 이용해서, 백트래킹을 빡세게 적용하면 이 역시도 `AC`를 받는다. 아래는 이 점을 활용한 풀이이다. 주유소 문제도 동일한 방식으로 풀린다. 정해를 몰랐어서 12틀 한것은 안 비밀이다.

```cpp
struct Edge {
    int v;
    ll w;
    short min;
 
    bool operator<(const struct Edge& t) const {
        if (w != t.w) return w > t.w;
        return v < t.v;
    }
};

int mdist[1001][1001];
 
vector<Edge> e[1001];
 
short s[1001];
int N, M;
void solve() {
    scanf("%d %d", &N, &M);
    for(int i = 1; i <= N; ++i) e[i].clear();
 
    memset(mdist, 0x3F, sizeof(int) * 1001 * 1001);
    FOR(i,0,M) {
        int u, v, w; scanf("%d %d %d", &u, &v, &w);
        if (mdist[u][v] > w) mdist[u][v] = w;
        if (mdist[v][u] > w) mdist[v][u] = w;
    }
 
    FOR(i,1,N+1) {
        FOR(j,1,N+1) {
            if (i == j) continue;
            if (mdist[i][j] >= 0x3F3F3F3F) continue;
            e[i].push_back({j, mdist[i][j], -1});
        }
    }
    FOR(i,1,N+1) {
        ll tmp; scanf("%lld", &tmp);
        s[i] = tmp;
    }
 
    ll minw[1001];
    ll mins[1001];
    memset(minw, 0x3F, sizeof(ll) * 1001);    
    memset(mins, 0x3F, sizeof(ll) * 1001);    
 
    priority_queue<Edge> pq;
    pq.push({1, 0, 2000});
    while(pq.size()) {
        auto cur = pq.top(); pq.pop();
        // _D("checking %d: %lld\n", cur.v, cur.w);
        if (cur.v == N) {
            printf("%lld\n", cur.w);
            return;
        }
 
        short cmin = min(cur.min, s[cur.v]);
        for(auto& edge: e[cur.v]) {
            if (edge.min == cmin) continue;
            edge.min = cmin;
            ll tmp = (ll)cur.w + (ll)edge.w * cmin;
            if (minw[edge.v] > tmp || mins[edge.v] > cmin) {
                pq.push({edge.v, tmp, cmin});
                minw[edge.v] = tmp;
                mins[edge.v] = cmin;
            }
        }
    }
    assert(false);
    printf("ERR!\n");
}
```