준연구소

// ver.2 속도가 빠름(2중 for문)
#include <stdio.h>

int main()
{
    int n, m;
    int d1, d2, d3;

    scanf("%d %d", &n, &m);
    scanf("%d %d %d", &d1, &d2, &d3);
    int t = n - m; // n - m이 (독도새우 수) - (보호해야 하는 수)이므로 n - m을 해준다.
    int ans = -1;

    // i는 d1을 사용한 횟수다.
    for (int i = 0; i <= t; i++) 
    {
        // j는 d2를 사용한 횟수다.
        for (int j = 0; j <= t; j++) 
        {
            int a = i * d1 + j * d2;
            // 만약 a가 k보다 크다면 빠져나가기 
            if (a > t) break;
            // b에는 현재 d3를 이용해 잡아야 하는 물고기수 저장
            int b = t - a;
            // c에는 b에 d3를 나눈 나머지를 저장한다.
            int c = b % d3;
            // 만약 c가 0이라면 계산할 수 있으므로 계산을 한다.
            if (c == 0)
            {
                int k = b / d3; // k에 잡아야 하는 물고기를 d3를 이용해 잡은 횟수 저장
                // 만약 ans가 처음 그대로인 -1이면 잡을 수 없다는 것이고
                //  i + j + k보다 크다면 최솟값이 생겼다는것이므로 변경
                if (ans == -1 || (ans > i + j + k))
                    ans = i + j + k;
            }
        }
    }
    printf("%d", ans);
}

// ver. 1 속도가 느림(3중 for문)
#include <stdio.h>

int main()
{
    int n, m;
    int d1, d2, d3;

    scanf("%d %d", &n, &m);
    scanf("%d %d %d", &d1, &d2, &d3);
    int t = n - m; // n - m이 (독도새우 수) - (보호해야 하는 수)이므로 n - m을 해준다.
    int ans = 1e8; // 1e8 = 100000000

    // i는 d1을 사용한 횟수다.
    for (int i = 0; i <= t; i++) 
    {
        // j는 d2를 사용한 횟수다.
        for (int j = 0; j <= t; j++) 
        {
            // k는 d3를 사용한 횟수다.
            for (int k = 0; k <= t; k++) 
            {
                // x에 d1, d2, d3를 이용해 잡은 새우 수를 모두 더해준다.
                int x = i * d1 + j * d2 + k * d3;
                // x가 t와 같다는것은 잡아야 하는 새우 수를 충족했다는 뜻
                if (x == t) 
                    // 만약 d1,d2,d3를 사용한 횟수인 i,j,k가 ans보다 작다는것은 최솟값이 나왔다는 것이므로 바꿔준다.
                    if (i + j + k < ans) ans = i + j + k; 
            }
        }
    }
    // 만약 ans가 1e8라는건 모든 새우를 못잡는것이므로 -1을 출력한다.
    if (ans == 1e8) printf("-1"); 
    else printf("%d", ans);
}

#include <stdio.h>

int M[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 30, 31, 30, 31 };

int is_yun_year(int y)
{
	return (((y % 4) == 0) && ((y % 100 != 0)) || ((y % 400) == 0));
}
int main()
{
	// k = 황금 사과가 수확되기 시작하는 사과와 배의 개수
	// n = 2일마다 수확되는 사과의 개수
	// m = 3일마다 수확되는 배의 개수
	int k, n, m;

	scanf("%d %d %d", &k, &n, &m);

	// k가 수확된 사과와 배의 개수를 저장하는 변수인데
	// 첫날에 사과와 배를 수확했기 떄문에
	// 첫번째로 수확된 사과와 배 제거
	k -= n + m;

	//6일을 기준으로 한 사가와 배의 수확량
	int num6 = 3 * n + 2 * m;

	// days 날에 처음으로 황금사과를 수확
	int days = 0; // 첫번째 황금 사과 수확까지 걸리는 날
	if (k > 0) // 만약 수확해야 하는 사과와 배의 개수가 0보다 크다면
	{
		int x = k / num6; // num6를 반복해야 하는 횟수
		days += x * 6; // days에 x * 6일만큼 사과와 배를 수확

		// k는 총 수확해야하는 사과와 배의 개수이니 
		// k에 x * 6일만큼 수확한 사과와 배를 제거해준다.
		k -= x * num6;

		// 만약 수확해야 하는 사과와 배가 없으면
		// days에 2를 추가해 첫 황금 사과를 수확하는 날짜를 저장한다.
		if (k == 0) days += 2;

		// 만약 수확해야 하는 사과와 배가 2일마다 수확되는 사과의 양보다 작거나 같다면
		// 한번 더 사과를 수확한 후 다음 사과 수확일에 황금 사과를 수확하면 되므로
		// days에 4를 추가해 첫 황금 사과를 수확하는 날짜를 저장한다.
		else if (k <= n) days += 4;

		// 만약 수확해야 하는 사과와 배가 2일마다 수확되는 사과의 양과 3일마다 수확되는 배의 양을 합친 것보다 작거나 같다면
		// 한번 씩 사과와 배를 수확한 후 황금 사과를 수확하면 되므로
		// days에 4를 추가해 첫 황금 사과를 수확하는 날짜를 저장한다.
		else if (k <= n + m) days += 4;

		// 만약 수확해야 하는 사과와 배가 2일마다 수확해야 하는 사과를 2번 수확한 것과 3일마다 수확되는 배의 양을 합친 것보다 작거나 같다면
		// 사과를 두 번 수확하도 배를 한 번 수확하면 황금 사과를 수확하는 날짜가 나오므로
		// days에 6를 추가해 첫 황금 사과를 수확하는 날짜를 저장한다.
		else if (k <= 2 * n + m) days += 6;

		// 위에 작업을 다 거쳤는데도 끝나지 않았다면 num6 과정을 한번 더 하면 되므로
		// days에 8을 더한다.
		else days += 8;
	}
	else days = 2; // 만약 k가 0보다 작다면 다음 사과 수확날에 황금 사과를 수확할 것이므로 days를 2로 정한다.

	int year = 2023, month = 1, day = 1;

	while (1)
	{
		// 만약 is_yun_year 함수에서 결과가 1이 나오면 윤년이란 뜻인데
		// M[2]가 2월 달 끝부분이므로 29로 바꾼다.
		if (is_yun_year(year)) M[2] = 29; 
		else M[2] = 28; // 윤년이 아니면 28로 둔다.
		if (days >= M[month]) // 만약 첫번쨰 황금 사과 수확일이 달 수를 넘어버린다면
		{
			days -= M[month]; // days에 달 수를 빼고
			month++; // 달을 하나 올린다.
			if (month == 13) // 만약 month가 13이면 년도를 올려줘야 하므로
			{
				year++; // 년도를 올려주고
				month = 1; // 달을 1로 바꿔준다.ㄴ
			}
		}
		else break; //days가 M[month]를 넘지 않으면 이 반복문을 나간다.
	}
	// 년도는 4칸에 맞춰서 출력하고
	// 월과 일은 2칸에 맞춰 출력한다.
	printf("%04d/%02d/%02d", year, month, day + days);
}

ABC 190 간단 후기 올립니다~ (atcoder.jp/contests/abc190)

A - Very Very Primitive Game

간단한 구현 문제입니다. 먼저 시작하는 사람의 캔디가 더 많으면 먼저 시작하는 사람이 이기고, 그렇지 않으면 다른 사람이 이깁니다.

int main() {
	int a, b, c; cin >> a >> b >> c;
	if (c == 0) {
		if (a > b) cout << "Takahashi";
		else cout << "Aoki";
	}
	else {
		if (b > a) cout << "Aoki"; 
		else cout << "Takahashi";
	}
}

B - Magic 3

간단한 구현 문제입니다.  X < S and Y > D인 (X, Y)가 존재하면 Yes, 아니면 No를 출력하면 됩니다.

int main() {
	int n, s, d; cin >> n >> s >> d;
	int x, y;
	while (n--) {
		cin >> x >> y;
		if (x<s && y>d) {
			cout << "Yes"; return 0;
		}
	}
	cout << "No";
}

C - Bowls and Dishes

완전탐색 문제입니다. K명의 사람이 C or D를 선택하는 모든 경우(2^K)에 대하여 가장 많은 조건을 만족하는 경우를 출력하면 됩니다

typedef pair<int, int> p;
 
int N, M, K, ans, S[100];
p ab[100], cd[100];
 
void f(int idx) {
	if (idx == K) {
		int dish[104], i;
		for (i = 1; i <= N; i++) dish[i] = 0;
		for (i = 0; i < K; i++) {
			if (S[i] == 1) dish[cd[i].x] = 1;
			else dish[cd[i].y] = 1;
		}
		int sum = 0;
		for (i = 0; i < M; i++) {
			if (dish[ab[i].x] && dish[ab[i].y]) sum++;
		}
		ans = max(ans, sum);
		return;
	}
	S[idx] = 1; f(idx + 1);
	S[idx] = 2; f(idx + 1);
}
 
int main() {
	int i;
	cin >> N >> M;
	for (i = 0; i < M; i++) cin >> ab[i].x >> ab[i].y;
	cin >> K;
	for (i = 0; i < K; i++) cin >> cd[i].x >> cd[i].y;
	f(0);
	cout << ans;
}

D - Staircase Sequences

수학 문제입니다. 등차수열의 시작과 끝을 각각 a, b라고 할 경우 a + (a+1) + ... + b = N 인 (a, b) 쌍의 개수를 구하면 됩니다. 좌변은 (1+2+...+b) - (1+2+...+a-1) 이므로, b(b+1) - a(a-1)= 2N --> (b+a)(b-a+1)=2N이 됩니다.

2N을 xy꼴로 나타내서 x=b+a, y=b-a+1 or x=b-a+1, y=b+a가 성립하는지 확인하면 됩니다.

ll N;

inline int f(ll x, ll y) {
	if ((x + y - 1) % 2 == 0) return 1;
	return 0;
}
 
int main() {
	cin >> N;
	N *= 2;
	ll ans = 0;
	for (ll i = 1; i*i <= N; i++) {
		if (N%i) continue;
		ll j = N / i;
		if (f(i, j)) ans++;
		if (f(-i, -j)) ans++;
	}
	cout << ans;
}

E - Magical Ornament

Graph + bit DP 문제입니다. M개의 이웃한 쌍 (A,B)를 edge, N개의 gem이 node인 graph를 생각하자. K개의 C에 대하여 Ci에서 Cj의 shortest path를 구하자.(BFS 이용) 모든 (Ci, Cj) 쌍의 shortest path를 D[K][K]라고 하자. K개의 C를 node, D를 edge로 갖는 Graph에서 임의의 정점에서 다른 모든 노드를 방문하는 최소 비용 (salesman problem)을 구하면 된다.

int N, M, K, C[20], CC[100004], CI[100004], S[20];
vector<int> adj[100004];
int adj2[20][20];
const int INF = (int)1e9;
int dp[1 << 17][17];
 
int dfs(int state, int u) {
	int &ret = dp[state][u]; if (ret != -1) return ret;
	if (state == ((1 << K) - 1)) return ret = 0;
 
	ret = INF;
	for (int v = 0; v < K; v++) {
		if (state&(1 << v)) continue;
		if (adj2[u][v] == -1) continue;
		int a = dfs(state | (1 << v), v) + adj2[u][v];
		if (a < INF) ret = min(ret, a);
	}
	return ret;
}
 
int main() {
	int i, j;
	cin >> N >> M;
	for (i = 0; i < M; i++) {
		int a, b; cin >> a >> b;
		adj[a].push_back(b); adj[b].push_back(a);
	}
	cin >> K;
	for (i = 0; i < K; i++) {
		cin >> C[i]; CC[C[i]] = 1; CI[C[i]] = i;
	}
 
	for (i = 1; i <= N; i++) {
		if (CC[i] == 0) continue;
		queue<int> q; q.push(i);
		vector<int> dist(N + 1, -1); dist[i] = 0;
		while (!q.empty()) {
			int u = q.front(); q.pop();
			for (auto v : adj[u]) {
				if (dist[v] != -1) continue;
				dist[v] = dist[u] + 1;
				q.push(v);
			}
		}
		for (j = 1; j <= N; j++) {
			if (CC[j] == 0 || i == j) continue;
			adj2[CI[i]][CI[j]] = adj2[CI[j]][CI[i]] = dist[j];
		}
	}
 
	int ans = INF;
	for (i = 0; i < (1 << K); i++) for (j = 0; j < K; j++) dp[i][j] = -1;
	for (i = 0; i < K; i++) {
		int ret = dfs(1 << i, i);
		if (ret < INF) ans = min(ans, ret + 1);
	}
	if (ans == INF) ans = -1;
	cout << ans;
}

F - Shift and Inversions

Segment Tree 문제입니다. i ~ i + N -1 구간의 inversion count를 구하면 됩니다. (0<= i <N) i=0일 경우는 segment tree를 이용하면 됩니다. (소스코드 rev_cnt) i=1 ~ N-1일 경우는 A[i]보다 작은 숫자와 큰 숫자는 O(1)에 찾을 수 있습니다. (소스크도 up, dn) 이유는 0 ~ N-1 숫자가 한 번씩 나오기 때문입니다.

struct sg {
	int st[1200004];
	void upd(int a, int b, int node, int node_st, int node_en) {
		if (a < node_st || node_en < a) return;
		if (node_st == node_en) {
			st[node] = b; return;
		}
		upd(a, b, node * 2, node_st, (node_st + node_en) / 2);
		upd(a, b, node * 2 + 1, (node_st + node_en) / 2 + 1, node_en);
		st[node] = st[node * 2] + st[node * 2 + 1];
	}
	int qry(int a, int b, int node, int node_st, int node_en) {
		if (a > node_en || node_st > b) return 0;
		if (a <= node_st && node_en <= b) return st[node];
		return qry(a, b, node * 2, node_st, (node_st + node_en) / 2) +
			qry(a, b, node * 2 + 1, (node_st + node_en) / 2 + 1, node_en);
	}
}S;
 
int main() {
	int i, n; cin >> n;
	vector<int> A(n + 1);
	ll rev_cnt = 0;
	for (i = 1; i <= n; i++) {
		cin >> A[i]; A[i]++;
		S.upd(A[i], 1, 1, 1, n);
		rev_cnt += (i - S.qry(1, A[i], 1, 1, n));
	}
	cout << rev_cnt << '\n';
	for (i = 1; i < n; i++) {
		int dn, up;
		dn = A[i] - 1; up = n - A[i];
		rev_cnt = rev_cnt - dn + up;
		cout << rev_cnt << '\n';
	}
}