알고리즘/codeforces
Educational Codeforces Round 121 A부터 C까지 업솔빙
Educational Codeforces Round 121 A부터 C까지 업솔빙 C번문제를 거의 다 풀었다고 생각했는데, 쉬울듯 말듯 계속 풀게만드는 문제라서 애먹었다. DIV 2 3솔의 벽은 높은것 같다. 그래도 *1100문제를 풀어서 다행이다. 이제 진짜 B번 문제는 좀 감이 잡히는 것 같아서 기분이 좋은 하루이다. A. Equidistant Letters (*800) 접기/펼치기 문제 설명 알파벳 소문자로 이루어진 문자열 $s$가 주어진다. 각 문자는 2번보다 더 많이 등장하지 않는다. 너의 목표는 같은 문자사이의 거리를 모두 같게 문자열에 있는 문자를 재배열 하는 것이다. 이때 문자를 새로 추가하거나 제거할 수 없다. 문제 해설 같은 문자사이의 거리를 모두 같게 만드는데 여기서 같은 문자는 최대 ..
알고리즘/codeforces
Codeforces Round #766 A부터 C까지 업솔빙
Codeforces Round #766 A부터 C까지 업솔빙 B번 문제가 게임이론? 이걸 어떻게 알아 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ 근데 막상 풀이 보면 납득이 가는 이유라서 정말 어이없는 문제. 이해가 정말 잘되서 놀랐다. C번 문제는 정수론 관련된 문제인데 알고리즘을 위한 정수론이 참 애매한것 같다. 정수론이 흔들리면 알고리즘에서 약점이 되는데, 그렇다고 막상 정수론을 공부하자고 하니 투머치인것 같고... 그냥 계속 문제 풀자. A. Not Shading (*800) 접기/펼치기 문제 설명 $n \times m$ 크기의 격자판이 있다. 몇개 격자에는 검은색으로 칠해져있고, 나머지는 흰색으로 칠해져 있다. 한번의 연산으로 검은 격자중 하나를 선택해서 다음 연산을 한번 실행한다. 해당 격자를 포함한 모든 행을 검은색..
알고리즘/codeforces
Codeforces Round #765 A부터 B까지 업솔빙
Codeforces Round #765 A부터 B까지 업솔빙 C번 문제가 *1700문제라서 심지어 dp라 깔끔하게 포기하고 오는 길이다. 나는 *1400까지 문제만 깔끔하게 푸는 실력이 되고 싶다. A. Ancient Civilization (*800) 접기/펼치기 문제 설명 이진수의 거리 는 다음과 같이 정의한다. 두 이진수끼리 같은 자리를 비교할 때, 서로 다른 숫자의 개수가 바로 그 거리이다. $n$개의 이진수가 주어졌을 때, 각 이진수와 y사이 거리 합을 최소화 하는 이진수 $y$를 찾아라. 문제 해설 문제를 보면서 처음에는 단순하게 or연산을 사용하면 되나 싶었는데, 자세히 보니까 아니였다. $n$개의 이진수에 대해서 맨 뒤자리 비트부터 보는데, 각 자리의 비트에서 1의 개수와 0의 개수를 세고..
알고리즘/codeforces
Codeforces Round #764 A부터 D까지 업솔빙
Codeforces Round #764 A부터 D까지 업솔빙 C번 문제까지는 어찌 문제를 풀었는데, 퍼포먼스는 1100정도 나온 것 같다. d번 문제는 이분탐색이라는 단서가 너무 많이 주어져 있었는데, 활용능력하고 결정함수를 만드는 능력이 떨어져서 못푼것 같다. A. Plus One on the Subset (*800) 접기/펼치기 문제 설명 배열 $a[1, ..., n]$이 주어진다. 그리고 다음 연산을 몇번이고 수행해서 배열의 모든 원소를 같게 만들고 싶다. 한 연산에서, 배열에 있는 index를 선택하고 해당 index에 속한 원소값을 1 올린다. 배열에 있는 모든 원소를 모두 같게 만들기 위해서 필요한 최소 연산횟수는 무엇인가? 문제 해설 index를 제한없이 선택할 수 있기 때문에 이 문제가 쉽..
알고리즘/codeforces
Hello 2022 A부터 B까지 업솔빙
Hello 2022 A부터 B까지 업솔빙 확률과 통계를 못하는 나는 경우의 수를 나누는 것을 정말 못한다. B번 문제가 그냥 경우의 수 나누는 문제 그자체라서 못풀겠다. 내가 하는 지금 문제풀이가 나중에 코딩테스트에 도움이 되길. A. Stable Arrangement of Rooks (*800) 접기/펼치기 문제 설명 $n \times n$ 크기 체스보드와 $k$개 룩이 있다. 칸 $(x, y)$ 는 행 $x$와 열 $y$의 교차점이다. 만약 한 룩이 다른 모든 룩에게 잡히지 않는다면 이 배치는 좋다 고 한다. 만약 한 룩을 다른 인접한 칸에 한칸 옮겨서 좋지 않은 배치가 된다면 이 좋은 배치는 안정적이지 않다고 한다. 그렇지 않으면 이 배치는 안정적인 배치라고 한다. $n \times n$ 크기의 판..
알고리즘/codeforces
Good Bye 2021: 2022 is NEAR A부터 C까지 업솔빙
Good Bye 2021: 2022 is NEAR A부터 C까지 업솔빙 B번까지 풀었는데, 퍼포먼스가 1300까지 나오는 기적? B번을 생각보다 빨리 풀어서 그런것 같다. 나는 쉬운 문제 셋보다 어려운 문제셋에 더 강점이 있는 것 같다는 생각을 요즘 계속 하는 중이다. 쉬운 문제셋은 생각보다 당황을 많이 하는데, 어려운 문제셋은 최선을 다해서 풀려고 해서 그런것 같다. 이번에는 C번까지 업솔빙을 해봤으니 공부가 더 많이 된것 같다. A. Integer Diversity (*800) 접기/펼치기 문제 설명 $n$개 정수 $a_1, a_2, ..., a_n$이 주어진다. 주어진 숫자의 아무 부분 집합을 선택해서 이 숫자들의 부호를 바꾼다. 이때 이 연산은 횟수 제한이 없다. 우리가 얻을 수 있는 배열 중에서..
