본문 바로가기

분류 전체보기

문제 풀이/Codeforces 2021. 4. 4. Codeforces Round #712 (Div1, Div. 2) A - Déjà Vu Problem - A - Codeforces codeforces.com 문자열 \(s\)가 주어진다. \(s\)의 임의의 위치에 문자 'a'를 추가하여, \(s\)가 팰린드롬이 아니도록 만들어야 한다. \(s\)가 'a'로만 이루어져 있다면 불가능하다. 그렇지 않다면, \(s\)의 맨 앞이나 맨 뒤에 'a'를 추가하면 둘 중 하나는 답이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include using namespace std; typedef long long ll; typedef pair pii; typedef pa..
작곡 2021. 4. 3. Rage of Necromancer 맨날 만들던 피아노/뉴에이지/클래식 곡이 아닌 첫 곡이다. 장르는 아마도 하드스타일이다. (그것치곤 빠른것 같긴하다) 평소에는 멜로디나 화성진행을 어떻게 해야될지 고민하는 것이 가장 힘든 점이었는데, 얘를 만들 때는 어떻게 원하는 음을 만들어야하는지 몰라서 시행착오를 많이 하느라 힘들었다. 일단 하드스타일 특유의 킥을 만들어야 했다. 일반적인 킥 몇개와 오실레이터 악기를 적당히 섞어서 잘 가공하니까 뭔가 그럴듯한게 나오긴했다.. 사실 조금 더 센 느낌을 원하긴했는데, 처음이니 일단 이 정도로 만족하기로 했다. 여기에 적당히 화성진행을 하나 깔고 무한 반복 시키니까 일단 틀이 완성되었다. 이제 여기에 적당히 멜로디를 얹으려고 했는데, 하던대로 멜로디를 쓰니까 장르와 너무 안 어울렸다! 그래서 그냥 화성에 ..
문제 풀이/Codeforces 2021. 3. 30. Codeforces Round #711 (Div. 2) A - GCD Sum Problem - A - Codeforces codeforces.com 어떤 수 \(x\)의 gcdSum을 \(x\)와, \(x\)의 모든 자릿수의 합의 최대공약수로 정의하자. \(n\)이 주어지면, \(n\)보다 크거나 같으면서 gcdSum이 1보다 큰 가장 작은 수를 구해야 한다. 어떤 수 \(x\)가 3으로 나눠 떨어진다면, gcdSum도 3의 배수이다. 따라서 \(n, n+1, n+2\)중 하나가 답이 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #include using namespace std; typedef long ..
문제 풀이/그외 2021. 3. 28. Code Jam - Qualification Round 2021 Reversort Code Jam - Google’s Coding Competitions Put your coding skills to the test as you work your way through multiple rounds of algorithmic coding puzzles for the title of Code Jam Champ and 15,000 USD. codingcompetitions.withgoogle.com 문제에 Reversort이라는 정렬방법이 주어진다. 배열이 주어지면, Reversort를 이용해 정렬하는데 필요한 비용을 구해야 한다. 하라는대로 구현하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25..
문제 풀이/그외 2021. 3. 21. Round A 2021 - Kick Start 2021 K-Goodness String Kick Start - Google’s Coding Competitions Hone your coding skills with algorithmic puzzles meant for students and those new to coding competitions. Participate in one round or join them all. codingcompetitions.withgoogle.com \(n\)길이의 문자열 \(s\)가 주어진다. 이 문자열의 점수를 \(s_i \ne s_{n-i+1}\)를 만족하는 \(i\)의 개수라고 하자. (\(1 \le i \le n/2\)) 문자열의 점수를 \(k\)로 만들기 위해, 바꿔야 하는 문자의 최소 개수를 구해야 한다. 주어..
문제 풀이/Codeforces 2021. 3. 20. Educational Codeforces Round 106 A - Domino on Windowsill Problem - A - Codeforces codeforces.com \(2 \times n\)크기의 격자가 있다. 첫번째 열의 첫 \(k_1\)개 칸과 두번째 열의 첫 \(k_2\)개 칸이 흰색으로 칠해져 있고, 그 외의 칸은 검은색으로 칠해져 있다. \(w\)개의 흰색 도미노와 \(b\)개의 검은색 도미노가 있다. 도미노의 크기는 모두 \(2 \times 1\)이고, 두 칸의 도미노의 색과 격자의 칸이 모두 같으면 그곳에 도미노를 놓을 수 있다. 도미노를 겹쳐서 놓을 수는 없을 때, 모든 도미노를 격자에 놓는 것이 가능한지 알아내야 한다. 관찰을 잘 하면, 각 색깔의 도미노의 면적보다 격자의 면적이 더 작지만 않으면 무조건 가능하다는 것을 알 수 있다. ..
문제 풀이/Codeforces 2021. 3. 18. Codeforces Round #708 (Div. 2) A - Meximization Problem - A - Codeforces codeforces.com \(n\)길이의 배열 \(a\)가 주어진다. 이 \(a\)의 원소들의 순서를 재배열해서, 모든 prefix의 MEX값의 합이 최대가 되도록 해야 한다. 큰 MEX값이 최대한 빨리 나와야 함을 알 수 있다. 앞에서부터 \(a_i = i\) (0-index)가 되도록 최대한 수를 채우면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #include using namespace std; typedef long lon..
알고리즘/수학 2021. 3. 14. FFT 최대 차수가 \(n\)인 두 다항식 \(A, B\)가 있습니다. 두 다항식의 곱 \(A \times B\)을 계산하는 작업은 일반적으로 \(O(n^2)\)의 시간복잡도를 가지게 됩니다. 이 작업을 무려 \(O(n\log n)\)에 할 수 있는 FFT 알고리즘에 대해 알아봅시다. 먼저, 다항식을 나타내는 2가지 방법에 대해 알아봅시다. \(n\)차 다항식을 나타낸다고 생각해 봅시다. 먼저, 일반적으로 \(n\)차 다항식의 \(n+1\)개의 계수를 차례대로 늘어놓는 방법이 있습니다. $$ax^2+bx+c \rightarrow \{c,b,a\}$$ \(i\)번째 원소는 \(i\)차 항을 나타내기 때문에 역순입니다. 이를 Coefficient Representation이라고 합니다. 두 번째로, 이 다항식에 \..

티스토리툴바