To the Expert

Educational Codeforces Round 117 A부터 D까지 업솔빙 C번 문제하고 D번 문제가 개인적으로 정말 좋았다고 생각하는 대회이다. C번문제는 이분탐색밖에 모르던 내가 파라메트릭 서치를 알게해줬고, D번 문제는 알고리즘을 공부하려고 정수론을 공부하는 것은 정말 어리석은 짓이라는 것을 깨닫게 해줬다. 이번 대회는 상대적으로 수학이 많이 나왔는데, 수학 문제 특성상 그리디처럼 문제를 온몸 비틀어서 푸는게 아니라 규칙만 딱 찾으면 답이 나와서 기존 대회보다는 답을 구하는 과정만 이해하면 나머지 코딩은 쉬웠다. 이번 대회에서 배운 것은 이분탐색과 파라매트릭 서치 나머지 연산과 나눗셈 연산과 뺄셈 좌표평면이 나오면 꼭 그려서 해보기 A. Distance (*800) 접기/펼치기 문제 설명 두 ..

AtCoder Beginner Contest 234 A부터 E까지 업솔빙 시간이 맞아서 최초로 실제 대회에 참여한 문제셋이다. 그래서 그런지 더욱더 업솔빙에 최선을 다했고, 풀지 못했던 E와 기를 쓰고 겨우 풀었던 D번 문제가 생각보다 쉬운 문제였다는 난이도 선정에 아쉬워하기도 했다. 하지만 처음 Atcoder 대회에서 퍼포먼스가 *825정도 나왔다는 점에서 나는 매우 만족한다. 이제 atcoder를 계속 연습하면서 brown 등급의 문제는 거뜬하게, green등급은 기를 쓰고 풀어서 겨우 풀 수 있는 수준까지가 1차 목표이다. 이번 대회에서 배운 것은 재귀함수로 이진수 빠르게 구하기 다양한 자료구조 생각하기 때로는 모든 경우의 수를 다 구하는 것이 가장 좋은 해법이다. 문제 옆에 붙어있는 난이도는 At..

Codeforces Round #754 (Div. 2) A부터 C까지 업솔빙 A번문제만 푼 대회 B번 문제는 계속 봐도 해설이 안떠올라서 그나마 만만해 보이는 C번 문제로 넘어갔는데 경우의수 1가지를 못찾아서 못풀었다. *1400난이도 치고는 경우의수 7가지만 찾으면 되는 쉬운 문제 였는데, 못풀어서 아쉬웠다. B번 문제는 이전에 풀었던 C. Rings 랑 비슷한 문제라서 더더욱 폿풀어서 아쉬운 문제였다. 계속 훈련을 하면 언젠가는 단단해 지겠지.. 이번 대회에서 배운 것은 문제에서 제공하는 예제 풀이에 너무 몰입하여 생각하지 않기. A, B, C는 생각보다 쉬운 문제다! 끝까지 경우의수 생각하면서 풀기 A. A.M. Deviation (*800) 접기/펼치기 문제 설명 세 숫자 $a_1, a_2, a_..

AtCoder Beginner Contest 211 A부터 D까지 업솔빙 일본 친구들은 진짜 DP를 좋아하는 것 같다. C번 문제는 문자열 DP에, D번 문제는 BFS + 다익스트라 + DP문제를 내놓았다. 코드포스에서는 민트까지 DP가 거의 안나오는데, atcoder에서 높은 티어를 받으려면 dp를 무조건적으로 정복해야 할 것같다. 다행인거는 전형적인 dp가 맨날 나온다는 점? 문제 유형 다 외워버려야지.. 이번 대회에서 배운 점은 문자열 dp 다익스트라는 결국 BFS의 변형이다. 최단 경로 개수 찾기 문제 옆에 붙어있는 난이도는 Atcoder Problems 에서 추정한 것으로 작성했다는 것을 미리 알린다. A - Blood Pressure (*6) 접기/펼치기 문제 설명 사람의 수축기 혈압인 $A$..

Codeforces Round #753 (Div. 3) A부터 D까지 업솔빙 이번 대회에는 DIV. 3답게 C번까지 풀었지만 D번은 못풀었는데, 내가 마지막에 제출한 틀린 코드에서 pair에 정렬 순서만 바꾸면 풀리는 문제라서 이제는 D번을 풀 수 있는 단계까지 눈앞에 이르렀다. E번 문제는 빡 구현문제인데 원래라면 업솔빙 했어야 하지만 codefore와 atcoder에서 내가 당장 배워야 하는 것은 dp, greedy, constructive, math, implementation, number theory 이기 때문에 pass했다. 이번 대회에서 배운 것은 규칙을 찾는 문제에서는 문제가 하라는 대로 일단 처음 10개항은 써보기 잘 모르겠어도 끝까지 포기하지 말기 접근법이 잘못된 것 같으면 과감히 방향..

Codeforces Round #752 (Div. 2) A부터 D까지 업솔빙 이번 대회에는 B번 1100 난이도까지 풀었지만 C번부터는 못풀었는데, 이 문제는 푸는 방법까지 알았는데 단 한가지 문장때문에 1시간을 뇌절하다가 못풀었다. 내가 푼 방식을 C번문제에서 설명할텐데, 내가 처음에 푼 코드와 정답 코드를 보면 이게 왜? 틀리지? 라는 생각을 이 글을 읽고 있는 사람 또한 알게 될 것이다. 마지막 D번 문제는 단순한 코드포스식 정수론이라서 업솔빙 할 것이다. 이번 대회에서 배운 것은 XOR연산과 홀수 짝수 반복 학습 최소공배수와 최대공약수, 그리고 배수 약수 찾기 알고리즘 break문의 위험성 수직선에서 나머지 연산의 기하학적 의미 A. Era (*800) 접기/펼치기 문제 설명 소호는 정수 $a_1..

Codeforces Round #737 (Div. 2) A부터 C까지 업솔빙 사실 코드포스에서 A번 문제가 5분 넘을때 까지 안풀리면 그 대회는 참가하지 않는 것이 RATING에 이로울 정도로 A번 문제를 쉽게 풀 수 있는지 없는지가 중요하다. 이번 대회는 A번 문제를 생각보다 빠르게 풀어서 기분이 좋았다. 하지만 바로 B번부터 막혀서 기분이 안좋았지만 나머지 B, C번 문제가 좋아서 업솔빙을 한다. 이번 대회에서 배운 것은 경로 압축 방법과 value-index pair 배열의 활용 이항계수의 성질 복습 및 dp 제발 정렬하는 것도 생각해보자. A. Ezzat and Two Subsequences (*800) 접기/펼치기 문제 설명 배열 1개가 주어지고 이 배열을 두 subsequences $a$, $..

AtCoder Beginner Contest 207 A부터 C까지 업솔빙 C번 문제 이거는 모르면 그냥 당하는 문제라고 생각했다. 문제 제목도 많은 조건 분기라서 이렇게 많은 조건을 분기해야 하나? 라는 생각을 하면서 문제를 풀었는데 결국은 못풀고 보니까 애초에 이런 문제를 푸는 방법이 있었다. 진짜 PS는 고인물 판인거 같다. 두 구간이 교차하는 조건 쉽게 구하기 닫힌구간과 열린구간에 대한 처리 방법 문제 옆에 붙어있는 난이도는 Atcoder Problems 에서 추정한 것으로 작성했다는 것을 미리 알린다. A - Repression (*6) 접기/펼치기 문제 설명 책상에 카드 3개가 있고 각 카드에는 양수가 적혀져 있다. 각 카드에 적혀있는 정수는 $A, B, C$이다. 두 카드를 선택하고 두 카드를..

AtCoder Beginner Contest 209 A부터 D까지 업솔빙 충격적이라고 느낀 문제 set, C번하고 D번을 모두 못풀어서 짜증이 났던 문제다 도대체 나는 천장을 얼마나 두들겨야 그 고지를 넘어갈 수 있을까? 심지어 C번문제는 거의 다 접근했는데 한가지 생각을 못해서 못풀었고, D번 문제는 접근방법 조차 생각을 못해서 배울 점이 개인적으로 많았다고 느끼는 문제다. bipartite graph(이분 그래프)의 정의 및 활용 문제 옆에 붙어있는 난이도는 Atcoder Problems 에서 추정한 것으로 작성했다는 것을 미리 알린다. A - Counting (*5) 접기/펼치기 문제 설명 $A$보다 작지않고 $B$보다 크지 않은 정수는 몇개일까? 문제 해설 일단 $A$부터 $B$까지 정수의 개수를..

문제 설명 앨리스와 밥은 $2 \times m$ 크기의 격자판에서 게임을 하고 있다. $i$번째 행과 $j$번째 열에 위치한 격자는 $a_{i, j}$개 코인이 위치해 있다. 처음에 앨리스와 밥은 격자 $(1, 1)$ 에 위치해 있다. 이들은 격자 $(2, m)$ 을 향해서 다음 동작을 수행한다. 가능한 움직임은 다음과 같다. 오른쪽으로 이동 $(x, y) -> (x, y + 1)$ 아래쪽으로 이동 $(x, y) -> (x + 1, y)$ 첫번째로 앨리스가 $(2, m)$ 을 향해서 움직인다. 앨리스는 방문한 모든 격자의 코인을 다 쓸어담는다. 단 처음과 끝도 포함. 두번째로 밥이 $(2, m)$ 을 향해서 움직인다. 이때 밥은 앨리스가 방문하지 않은 모든 격자의 코인을 다 쓸어 담는다. 즉 앨리스가 이..