Kareus Devlog

오랜만의 포스팅입니다. 하던 일에 진전이 별로 없었기 때문에 포스팅할 것도 없네요. 이번엔 2021 shake의 나머지 문제를 모두 풀어봤습니다. 억까 때문에 스트레스가 쌓여서 PS는 이제 그만 건드릴까 생각 중입니다. 이전 문제들 (A ~ D번)은 여기에서 확인하실 수 있습니다. BOJ 24232. 망가진 나무 문제 링크 : https://www.acmicpc.net/problem/24232 24232번: 망가진 나무 첫째 줄에 뒤집어야하는 간선을 $N-1$자리 이진수로 출력한다. 왼쪽에서 $i$번째 비트는 $i$번째 간선을 뒤집어야 하면 1, 아니면 0이다. 이진수에 등장하는 1의 개수가 최소가 되도록 해야 한다. www.acmicpc.net 풀이 : 2021 shake의 E번, F번, G번, I번 ..

요즘 너무 바쁘다. 게임 엔진 건드릴 시간이 없다... 아무튼, shake 2021의 문제를 풀어봤습니다. Open Contest에서는 D번까지 풀었고, 그 뒤로는... 나중에 풀어봐야겠습니다. 시간이 부족행 BOJ 24228. 젓가락 문제 링크 : https://www.acmicpc.net/problem/24228 24228번: 젓가락 두 개의 정수 $N, R$이 주어진다. $(1 ≤ N,R ≤ 10^{18})$ www.acmicpc.net 풀이 : 젓가락이 한 쌍 완성되기 위한 최악의 경우는, 모든 젓가락을 하나씩 뽑은 뒤에 아무 젓가락이나 하나 뽑는 경우입니다. 이 때 뽑는 갯수는 $N + 1$개입니다. 그 이후엔 방금 완성한 한 쌍을 다시 뽑는 경우 (2개)와, 나머지 젓가락 중 한 쌍을 완성하는..

문제 링크 : https://www.acmicpc.net/problem/23744 23744번: 알고리즘 과외 지환이(롸롸롸롸)가 운영하는 알고리즘 학원에는 $N$명의 학생이 있고, 각 학생은 $1$부터 $N$까지의 번호를 가지고 있다, 알고리즘 학원에서는 학생의 수준을 나타내기 위해 레이팅 시스템을 www.acmicpc.net 1. 설명 N명의 학생이 있고, 각각 레이팅 값이 있습니다. 레이팅 차가 최대가 되도록 2명을 뽑아 그 차를 구해야 하는데, 학생마다 짝이 될 수 있는 학생 번호의 구간이 다릅니다. 2. 풀이 더보기 2021 서강대 프로그래밍 대회에서 출제된 문제입니다. 공식 홈페이지에 풀이가 있습니다. $i$번째 학생과 짝을 이룰 수 있는 학생 번호의 구간은 $[i - r_i, i - l_i]..

문제 : https://www.acmicpc.net/problem/17476 17476번: 수열과 쿼리 28 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 L R X: 모든 L ≤ i ≤ R에 대해서 Ai = Ai + X를 적용한다. 2 L R: 모든 L ≤ i ≤ R에 대해서 Ai = ⌊√A www.acmicpc.net 1. 설명 길이가 $N$인 수열 $A$에 대해 3개의 쿼리를 실행해야 합니다. 이때 $N \le 100000$이고, 총 쿼리 수 $Q \le 100000$입니다. 1 L R X : $L \le i \le R$인 모든 $A_i$에 대해 $A_i = A_i + X$를 실행한다. 2 L R : $L \le i \le R$인 ..

문제 : https://www.acmicpc.net/problem/13263 13263번: 나무 자르기 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄에는 a1, a2, ..., an이, 셋째 줄에는 b1, b2, ..., bn이 주어진다. (1 ≤ ai ≤ 109, 0 ≤ bi ≤ 109) a1 = 1이고, bn = 0이며, a1 b2 > ... > bn을 만족 www.acmicpc.net 1. 설명 나무를 자를 때마다 전기톱을 충전해야 합니다. $i$번째 나무의 높이는 $a_i$이고, 전기톱을 충전하는 비용은 완전히 자른 (높이가 0인) 나무 중 가장 높은 번호를 $j$라고 할 때 $b_j$입니다. 이 때 모든 나무를 자르기 위한 총 충전 비용..

문제 : https://www.acmicpc.net/problem/15896 15896번: &+ +& 길이 N의 자연수 수열 2개 A1, A2, ..., AN과 B1, B2, ..., BN이 주어진다. 다음 2가지 값을 구하여라. 모든 (Ai & Bj)의 합을 1999로 나눈 나머지 모든 (Ai + Bj)의 bitwise and 연산 값 여기서 &는 bitwise and 연산을 www.acmicpc.net 1. 설명 길이가 N인 수열 $A_1 , ... , A_N$ 과 $B_1 , ... , B_N$이 있습니다. $1 \le i,j \le N$인 모든 $i, j$에 대한 $A_i \cap B_j$ 의 합과 $A_i + B_j$의 & (bitwise AND) 연산 값을 구해야 합니다. 첫 번째 값의 경우 ..

문제 : https://www.acmicpc.net/problem/13705 13705번: Ax+Bsin(x)=C 첫째 줄에 정수 A, B, C가 주어진다. (0 < B ≤ A ≤ 100,000, 0 < C ≤ 100,000) www.acmicpc.net 1. 설명 정수 A, B, C가 주어집니다. 문제의 제목대로, Ax + Bsin(x) = C를 만족하는 x의 값을 구해야 됩니다. 거의 똑같은 문제로 14786번 문제가 있습니다. 둘 다 같은 식의 해 x를 구하는 것이지만, 13705번은 $10^{-7}$의 자리에서 반올림해야 하고, 14786번은 그냥 구하면 됩니다. 스페셜 저지냐 아니냐도 갈리는데, 이러한 차이만으로 난이도가 극단적으로 바뀌었습니다. 너무 헤매는 바람에 20트를 더 한 뒤에 Pyth..