Codeforces Round #688 (Div. 2) ABCD

import sys
input = sys.stdin.readline

for TEST in range(int(input())):
    n, m = map(int, input().split())
    r = [*map(int, input().split())]
    c = [*map(int, input().split())]
    s = set(x for x in r)
    res = 0
    for i in c:
        if i in s: res += 1
    print(res)

 

A - Cancel the Trains

 

인접한 지점끼리 거리가 모두 같으므로 중복되는 값의 수가 답이다.

 

 

import sys
input = sys.stdin.readline

for TEST in range(int(input())):
    n = int(input())
    s = [*map(int, input().split())]
    R = 0
    r = max(abs(s[1]-s[0]), abs(s[n-2]-s[n-1]))
    for i in range(n-1):
        R += abs(s[i]-s[i+1])
        if i<n-2:
            r = max(r, abs(s[i]-s[i+1])+abs(s[i+1]-s[i+2])-abs(s[i]-s[i+2]))
    print(R-r)

 

B - Suffix Operations

 

한 숫자를 원하는 수로 바꾼다 = 한 숫자를 제외한다

 

따라서 숫자 하나를 제외하여 얻을 수 있는 최대 이득을 구할 수 있다.

 

첫 수와 마지막 수에 대해 예외처리를 조금 하였다.

 

 

#include <bits/stdc++.h>
using namespace std;

int N;
int board[2002][2002];
int good[10], res[10];
int cMin[10], rMin[10], cMax[10], rMax[10];

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int TEST; cin >> TEST; while (TEST--) {

		for (int i = 0; i < 10; ++i) {
			cMin[i] = rMin[i] = 100000;
			cMax[i] = rMax[i] = -1;
			good[i] = res[i] = 0;
		}

		cin >> N;
		for (int r = 0; r < N; ++r) for (int c = 0; c < N; ++c) {
			char req; cin >> req; board[r][c] = req - '0';
		}

		for (int r = 0; r < N; ++r) for (int c = 0; c < N; ++c) {
			int cur = board[r][c]; good[cur]++;
			rMin[cur] = min(rMin[cur], r);
			rMax[cur] = max(rMax[cur], r);
			cMin[cur] = min(cMin[cur], c);
			cMax[cur] = max(cMax[cur], c);
		}

		for (int r = 0; r < N; ++r) for (int c = 0; c < N; ++c) {
			int cur = board[r][c], b, h;
			if (good[cur] < 2) continue;

			b = max(N - 1 - r, r), h = max(cMax[cur] - c, c - cMin[cur]);
			res[cur] = max(res[cur], b * h);
			b = max(N - 1 - c, c), h = max(rMax[cur] - r, r - rMin[cur]);
			res[cur] = max(res[cur], b * h);
		}

		for (int i = 0; i < 10; ++i) {
			cout << res[i] << " ";
		} cout << "\n";

	}
}

 

C - Triangles

 

어떤 수(digit) a의 위치 (r, c)의 최소와 최대를 구하면, 모든 a의 위치는 그 구간에 포함된다.

 

a를 한 꼭짓점으로 사용할 때, 임의로 사용할 위치는 보드의 테두리와 맞닿은 네 곳 중 하나로 정하는 것이 최선이다.

 

특히, 이렇게 만든 변은 보드의 변과 반드시 평행하다.

 

이제 나머지 꼭짓점을 원래 있던 a 중에서 골라야 하는데, 구간의 경계에 있는 아무 a를 고르면 현재 밑변으로 만들 수 있는 가장 큰 삼각형이 된다. (즉, 경곗값을 이미 구했으므로 실제로 탐색할 필요가 없다.)

 

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    ll n, streak = 0;
    int TEST; cin >> TEST; while (TEST--) {
        cin >> n;
        if (n & 1) { cout << "-1\n"; continue; }
        vector<int> res;

        while (n > 0) {
            res.push_back(1); n -= 2;
            streak = 4;
            while (n - streak >= 0) {
                n -= streak; streak *= 2;
                res.push_back(0);
            }
        }

        if (res.size() > 2000) { cout << "-1\n"; continue; }

        cout << res.size() << "\n";
        for (int i : res) cout << i << " "; cout << "\n";
    }

}

 

D - Checkpoints

 

예제를 관찰하여 길이 n의 수열 "1 0 0 ... 0" 은 2 + 4 + 8 + ... 2ⁿ 임을 알 수 있다. (실제론 역순이지만 중요하지 않다.)

 

그냥 naive하게 구해도 되는 것 같다.

 

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Tree {
    vector<int> dup;
    vector<vector<int> > adj;

    Tree(int sz0) {
        dup.resize(sz0 + 1);
        adj.resize(sz0 + 1);
        for (int i = 0; i < sz0 - 1; ++i) {
            int p, q; cin >> p >> q;
            adj[p].push_back(q); adj[q].push_back(p);
        }
        cout << solve(1) << "\n";
    }
    int solve(int id) {
        dup[id] = true;

        int go = 0;
        vector<int> ret;
        for (int i : adj[id]) if (!dup[i]) {
            go += 1;
            int req = solve(i);
            ret.push_back(req);
        }
        if (go == 0) return 1;
        sort(ret.begin(), ret.end());
        if (ret.size() == 1) {
            return ret[0] + (id != 1);
        }
        /*cout << id << " returns ";
        for (auto i : ret) cout << i << " "; cout << "\n";*/
        return ret[ret.size() - 2] + (go > 1);
    }

};

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int TEST; cin >> TEST; while (TEST--) {
        int n; cin >> n; Tree T(n);
    }

}

 

E - Dog Snacks

 

두 번째로 높은 서브트리로 뭔가 해 보려고 했는데 잘 안됐다.