알고리즘/atcoder
AtCoder Beginner Contest 226 A부터 E까지 업솔빙
AtCoder Beginner Contest 226 A부터 E까지 업솔빙 D번까지 다 푼셋이다. 엣코더에서는 한 70%확률로 800까지 난이도 문제를 풀 수 있고, 그 위에 있는 난이도 문제는 50%확률로 풀 수 있는 것 같다. 티어가 오를 수 있다는 가능성이기 때문에 엣코더를 꾸준히 도전하고 싶다. 이번 대회에서 배운 내용은 무방향 그래프의 사이클 판독 특수한 경우? 라서 한번 경험해보면 좋을 것 같은 문제였다. 문제 옆에 붙어있는 난이도는 Atcoder Problems 에서 추정한 것으로 작성했다는 것을 미리 알린다. A - Round decimals (*14) 접기/펼치기 문제 설명 최대 소숫점 이하 3자리까지 표현할 수 있는 실수 $X$가 주어진다. 해당 $X$와 가장 가까운 정수를 출력하라. 문..
알고리즘/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번보다 더 많이 등장하지 않는다. 너의 목표는 같은 문자사이의 거리를 모두 같게 문자열에 있는 문자를 재배열 하는 것이다. 이때 문자를 새로 추가하거나 제거할 수 없다. 문제 해설 같은 문자사이의 거리를 모두 같게 만드는데 여기서 같은 문자는 최대 ..
알고리즘/atcoder
AtCoder Beginner Contest 225 A부터 D까지 업솔빙
AtCoder Beginner Contest 225 A부터 D까지 업솔빙 D번을 내가 왜 못풀었을까? 계속 강조하지만 문제를 너무 어렵게 생각하지 않는게 좋을 것 같다. 때로는 문제에서 하라는 대로 그대로 구현하는 능력도 중요하다는 것을 잊지말길. 하라는대로만 하고 그 다음 시간초과가 나면 새로운 알고리즘을 생각해보자. 문제 옆에 붙어있는 난이도는 Atcoder Problems 에서 추정한 것으로 작성했다는 것을 미리 알린다. A - Distinct Strings (*12) 접기/펼치기 문제 설명 알파벳 소문자 3글자로만 이루어진 문자열 $S$가 주어진다. $S$를 나열할 때 얻을 수 있는 서로다른 문자열의 개수는 몇개일까? 문제 해설 모든 문자가 같으면 1, 모든 문자가 다르면 6, 그렇지 않으면 3을..
알고리즘/codeforces
Codeforces Round #766 A부터 C까지 업솔빙
Codeforces Round #766 A부터 C까지 업솔빙 B번 문제가 게임이론? 이걸 어떻게 알아 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ 근데 막상 풀이 보면 납득이 가는 이유라서 정말 어이없는 문제. 이해가 정말 잘되서 놀랐다. C번 문제는 정수론 관련된 문제인데 알고리즘을 위한 정수론이 참 애매한것 같다. 정수론이 흔들리면 알고리즘에서 약점이 되는데, 그렇다고 막상 정수론을 공부하자고 하니 투머치인것 같고... 그냥 계속 문제 풀자. A. Not Shading (*800) 접기/펼치기 문제 설명 $n \times m$ 크기의 격자판이 있다. 몇개 격자에는 검은색으로 칠해져있고, 나머지는 흰색으로 칠해져 있다. 한번의 연산으로 검은 격자중 하나를 선택해서 다음 연산을 한번 실행한다. 해당 격자를 포함한 모든 행을 검은색..
알고리즘/atcoder
AtCoder Beginner Contest 224 A부터 D까지 업솔빙
AtCoder Beginner Contest 224 A부터 D까지 업솔빙 이번 대회에서 D번 문제가 내 잊어버린 BFS감을 다시 찾는데 도움이 된 것 같다. 이전에는 BFS문제가 나왔을 때, 이해하는데만 오랜 시간이 걸렸는데, 이제는 이해할 때 생각보다 적은 시간이 걸려서 좋았다. 그리고 D번 문제가 생각보다 잘 만든 문제라서 공부하면서 기분이 좋았다. C번 문제같은 경우는 일단 완전탐색을 항상 생각하는 것이 중요할 것 같다. 심지어 정렬까지도. 문제 옆에 붙어있는 난이도는 Atcoder Problems 에서 추정한 것으로 작성했다는 것을 미리 알린다. A - Tires (*6) 접기/펼치기 문제 설명 문자열 "er"과 "ist"로 끝나는 문자열 $S$가 주어진다. 만약 $S$가 "er"로 끝나면 "er..
알고리즘/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의 개수를 세고..
