준연구소

#include <stdio.h>

int main()
{
	printf("2\n");
    printf("00:04 11:56");
}

#include <iostream>

// 입력 : 시간 h, 분 m, 기준값 d
// 출력 : 현재 시간대의 각도가 주어진 사잇각(d)와 같다면 1, 아니면 0
int f (int h, int m, int d) // h = 3, m = 0
{
    // t = h시와 m분을 분으로 환산 // t = 180
    int t = h * 60 + m;

    // t가 홀수면 시침의 회전수에 소수점이 붙기 떄문에 오답이 나오게 된다.
    if (t % 2 == 1)
        return 0;

    // x = 시침이 몇도 도는지 저장(t / 2는 0.5를 분수로 바꾼 것)
    // y = 분침이 몇도 도는지 저장
    // z = x - y의 절댓값 저장
    int x = (t / 2) % 360;
    int y = (t * 6) % 360; 
    int z = abs(x - y);

    // z가 180보다 큰것은 주어진 사잇각의 크기를 초과하므로
    // 360에 z를 뺸 값을 z에 저장
    if (z > 180)
        z = 360 - z;

    if (z == d)
        // 현재 시간의 사잇각이 주어진 사잇각과 
        // 같은 것이므로 1 반환
        return 1;
    else
        // 현재 시간의 사잇각이 주어진 사잇각과 
        // 같지 않은것이므로 0 반환
        return 0;
}

int main()
{
    // d = 사잇각
    /// h, m = 시간과 분
    // cnt = 개수
    int d, h, m, cnt = 0;

    scanf("%d", &d);
    
    // 시간은 0시부터 11시까지 있으니
    // h를 0부터 11까지 돌린다.
    for (h = 0; h < 12; h++)
    {
        // 분은 0분부터 59분까지 있으니
        // m을 0부터 59까지 돌린다.
        for (m = 0; m < 60; m++)
        {
            // f함수에서 참이 나왔다는건 d와 같은 각이라는 뜻이므로
            // cnt를 1 올려준다.
            if (f(h, m, d) == 1) cnt++;
        }
    }
    
    // d와 사잇각이 같은 시각의 개수 출력
    printf("%d\n", cnt);
    
    // 시간은 0시부터 11시까지 있으니
    // h를 0부터 11까지 돌린다.
    for (h = 0; h < 12; h++)
    {
        // 분은 0분부터 59분까지 있으니
       // m을 0부터 59까지 돌린다.
        for (m = 0; m < 60; m++)
        {
            // f함수에서 참이 나왔다는건 d와 같은 각이라는 뜻이므로
            // 시각을 출력해준다.(%02d = 숫자 2개 고정적으로 출력, 한 자리 수는 앞에 0 추가 출력
            // 예:출력값이 8이면 08이 출력된다.)
            if (f(h, m, d) == 1) printf("%02d:%02d\n", h, m);
        }
    }
}

// ver.1 가장 비효율적 코드(for문)
#include <stdio.h>

int main()
{
	// n = 한라봉 무게, ans = 박스의 개수 저장
	int n, ans = -1; 

	scanf("%d", &n);

	// t = 한라봉의 무게를 저장시켜놓은 변수인데 이 변수를 기준으로 아래 for 문이 돌아간다.
	int t = n; 

	// i = 10kg짜리 박스를 사용하는 개수를 저장한다.
	for (int i = 0; i <= t; i++) 
	{
		// 만약 10kg 박스만으로 한라봉을 포장할 수 없다면 for문 나가기
		if (i * 10 > t) break;

		// j = 5kg짜리 박스를 사용하는 개수를 저장한다.
		for (int j = 0; j <= t; j++) 
		{
			// 만약 10kg 박스와 5kg 박스만으로 한라봉을 포장할 수 없다면 for문 나가기
			if (i * 10 + j * 5 > t) break;

			// k = 3kg짜리 박스를 사용하는 개수를 저장한다.
			for (int k = 0; k <= t; k++)
			{
				// 만약 10kg, 5kg, 3kg 박스만으로 한라봉을 포장할 수 없다면 for문 나가기.
				int a = i * 10 + j * 5 + k * 3;
				if (a > t) break;

				// b = 남은 한라봉 무게를 저장.
				int b = t - a;
				int l = b;

				// 만약 ans에 한 번도 값이 들어간 적이 없거나 ans이 모든 상자 사용값보다 크다면 ans 바꾸기
				if (ans == -1 || (ans > i + j + k + l))
					ans = i + j + k + l;
			}
		}
	}

	// 박스의 개수 출력
	printf("%d", ans);
}

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

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';
	}
}