2022 연세대학교 미래캠퍼스 슬기로운 코딩생활 Open Contest

https://www.acmicpc.net/contest/view/833

2022 연세대학교 미래캠퍼스 슬기로운 코딩생활 Open Contest

 

---

 

문제가 그리 어렵지 않아서 나도 다 풀 수 있었다.

 

풀이

A. 영수증

다 더한 값이 주어진 X랑 같은지 확인하면 된다.

 

B. 커트라인

정렬한 후 K번째로 큰 원소의 값을 출력하면 된다. 동점자 처리는 안 해줘도 되는 듯하다.

 

C. 연속 XOR

브루트포스로 하면 B <= 10^18이므로 당연히 시간초과가 날 것이다. 그러기에 A에서부터 B까지, 각 수를 2진수로 나타냈을 때 각 자리의 수가 홀수번 나타나면 해당 자리에 수가 있으며, 짝수버 나타나면 해당 자리에 수가 없다는 점을 이용한다. F(N, x)을 '0~N까지 이진수로 나타냈을 때 (1<<x)자리에 나타나는 1의 개수'라고 한다면,

F(N, x) = N / (1<<(x+1)) * x + max(0, N%(1<<(x+1)) - (1<<x) + 1)

이 된다. 식으로 보면 살짝 막막해 보이지만, 0부터 N까지

2의 자리의 패턴: 0 0 1 1 0 0 1 1 ...

4의 자리의 패턴: 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 ...

를 일반화한 것이다.

따라서, x=0부터, 1<<x 가 B 이하일 때까지 F(B, x) - F(A-1, x) 가 홀수이면 정답은 1<<x자리에 1이 있다.

P.S. 어제 술 먹고 와서 그런지 너무 일반화가 안 되더라. 그래서 우르스 잡고 오니 생각이 나서 풀었다.

 

D. 시루의 백화점 구경

백준 5427 불과 같은 multisource BFS 문제이다.

K값에 따라 '못 가는 마네킹 근처'를 BFS로 기록하고, 미루와 물을 동시에 BFS 진행한다.

마네킹 범위 기록을 '대충' 구현하면 시간초과가 뜰 지도..?

cf) 22.07.12 수정: 테스트케이스가 추가되면서 틀렸다. 기존 코드는 K 범위 안에 여러 개의 마네키이 있는 경우를 고려하지 않았다. 이를 개선하였다.

 

E. 방사형 그래프

각을 어떻게 계산할까 고민하다가, 기울기를 비교하여 풀었다. 찾아보니까 CCW로 더 편하게 할 수 있다고 한다.

 

코드

A

import java.io.*;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int X = Integer.parseInt(br.readLine());
        int N = Integer.parseInt(br.readLine());
        int sum = 0;
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            sum += Integer.parseInt(st.nextToken()) * Integer.parseInt(st.nextToken());
        }
        System.out.println((X == sum)? "Yes": "No");
    }
 
}
 

 

B

import java.io.*;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[] nums = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(nums);
        System.out.println(nums[N-K]);
    }
 
}
 

 

C

import java.io.*;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long A = Long.parseLong(st.nextToken());
        long B = Long.parseLong(st.nextToken());
        long ans = 0;
        int x = 0;
        while (((long)1<<x) <= B) {
            long digit = ((long)1<<x);
            long num = calc(B, digit) - calc(A-1, digit);
            if (num % 2 == 1) {
                ans += digit;
            }
            x++;
        }
        System.out.println(ans);
    }
 
 
    static long calc(long n, long digit) {
        long ret = 0;
        ret += n / (2*digit) * digit;
        n %= 2*digit;
        if (n >= digit) ret += (n-digit+1);
        return ret;
    }
}
 

 

D

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, -1, 1 };
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[][] map = new int[M][N];
        boolean[][] visited = new boolean[M][N];
        Queue<int[]> queue = new ArrayDeque<>();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 4) {
                    queue.offer(new int[] {i, j});
                }
            }
        }
        
        // 마네킹에 대해 bfs를 수행하기 위해 마네킹의 위치를 담아둔다.
        Queue<int[]> queue2 = new ArrayDeque<>();
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == 3) {
                    visited[i][j] = true;
                    queue2.offer(new int[] {i, j});
                }
            }
        }
        
        // 마네킹으로부터 거리가 K 이하인 구역은 지나가지 못함.
        int cnt = 0;
        while (cnt < K) {
            int size = queue2.size();
            while (size-- > 0) {
                int[] cur = queue2.poll();
                int r = cur[0], c = cur[1];
                for (int k = 0; k < 4; k++) {
                    int nr = r + dr[k], nc = c + dc[k];
                    if (nr < 0 || nr >= M || nc < 0 || nc >= N) continue;
                    if (visited[nr][nc]) continue;
                    visited[nr][nc] = true;
                    queue2.offer(new int[] {nr, nc});
                }
            }
            cnt++;
        }
        
        // 시루의 시작점
        visited[queue.peek()[0]][queue.peek()[1]] = true;
        int t = 0;
        
        // 시루의 이동을 bfs로 구현
        while (!queue.isEmpty()) {
            t++;
            int size = queue.size();
            while (size-- > 0) {
                int[] cur = queue.poll();
                int r = cur[0], c = cur[1];
                for (int k = 0; k < 4; k++) {
                    int nr = r + dr[k], nc = c + dc[k];
                    if (nr < 0 || nr >= M || nc < 0 || nc >= N) continue;
                    if (visited[nr][nc] || map[nr][nc] == 1) continue;
                    if (map[nr][nc] == 2) {
                        System.out.println(t);
                        return;
                    }
                    visited[nr][nc] = true;
                    queue.offer(new int[] {nr, nc});
                }
            }
        }
        System.out.println(-1);
    }
}
 

 

 

E

import java.io.*;
import java.util.*;
 
public class Main {
    
    static int[] ability = new int[8];
    static int[] choices = new int[10];
    static boolean[] visited = new boolean[8];
    static int ans = 0;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 8; i++) {
            ability[i] = Integer.parseInt(st.nextToken());
        }
        perm(0);
        System.out.println(ans);
    }
    
    static void perm(int cnt) {
        if (cnt == 8) {
            if (isConvex(choices)) ans++;
            return;
        }
        
        for (int i = 0; i < 8; i++) {
            if (visited[i]) continue;
            visited[i] = true;
            choices[cnt+1] = ability[i];
            perm(cnt+1);
            visited[i] = false;
        }
    }
    
    static boolean isConvex(int[] choices) {
        choices[0] = choices[8];
        choices[9] = choices[1];
        for (int i = 1; i <= 8; i++) {
            int x = choices[i-1], y = choices[i], z = choices[i+1];
            double s1 = (y-(x/Math.sqrt(2))) / (x/Math.sqrt(2));
            double s2 = ((z/Math.sqrt(2))-y) / (z/Math.sqrt(2));
            if (s2 >= s1) {
                return false;
            }
        }
        return true;
    }
}