Codeforces Round 918 Upsolving

대회 참가 유무: Y
최종 Performance: 1756 (Rank: 229 / 27413)
Round 링크: Top / 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틀 한것은 안 비밀이다.

풀이·코드 펼치기

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");
}