취미로PS하는사람

https://www.acmicpc.net/problem/19274 앳코더를 사랑하는 나에게는 정말 익숙한 이름인 Snuke좌가 나오는 문제다. 대학생을 대상으로 하는 러시아 캠프(페트로 뭐시기)에서 앳코더쪽 사람들이 낸 문제인 것 같았다. 그래서 그런지 문제 스타일도 앳코더 스타일 느낌이 강하다. 코딩 간단, 디스크립션 간단, 아이디어성. 문제 정점이 $N$개인 트리가 주어진다. 우리는 적당히 $K$개의 정점 $x_1, x_2, \cdots, x_K$를 선택하여 임의의 정점 $i$에 대해 $(d(x_1, i), d(x_2, i), \cdots, d(x_K, i))$가 모두 다르도록 할 것이다. 다시 말해, $K$개의 정점을 골라 각 정점들로부터의 거리 정보 벡터로부터 어떤 점인지 알아낼 수 있도록 $K..

KMP.. 아픈 기억이 있는 알고리즘. 아무튼 그동안 이러저러한 이유로 KMP 공부를 미루고 있다가 최근에야 다시 제대로 배웠다. 아이디어 자체는 간단하다. 문자열 $S$에 패턴 $P$를 매칭할 때, $P$의 $i$번째까지의 문자열에 대해 접두사이면서 접미사인 문자열의 최대 길이(여기서 접두사와 접미사는 원래 문자열을 제외하고 말한다.)를 실패 함수라고 정의한 후 이를 잘 이용하면 $O(|S|+|P|)$에 패턴이 존재하는지 찾을 수 있다. $S$의 중간 부분부터 $i-1$번째까지 문자열과 $P$의 $p$번째까지 문자열이 일치한다고 하자. $S$의 $i$번째 문자를 새로 매칭시키려고 할 때, 만약 성공한다면 $p$를 1 증가시키면 그만이지만 실패할 경우, Naive하게 할 때는 매칭을 시작한 곳 다음 부분..

https://www.acmicpc.net/problem/19833 간단한 수열에서의 문제. 앳코더 스타일 같아서 마음에 들었고 충분히 대회에도 나올만 한 문제라고 느꼈다. 다만 코딩미스라던지 생각을 깔끔히 정리하지 못해 시간이 꽤나 걸렸다.. 다른 사람들의 답안을 훑어보니, 나와 비슷하게 푼 사람도 있었고 스택(?)을 이용하여 푸는 방법도 있는 것 같았다. 성실한 사람이라면 둘 모두 알아보면 좋을 것 같다. 문제 수열$\{a_i\}$가 주어진다. 서로 겹치는 원소가 없는 두 구간의 최댓값이 같은 경우의 수(즉, 구간쌍의 개수)를 구하시오. 풀이 더보기 수열의 수들을 좌표압축하면 $[1, n]$의 숫자로만 이루어져있다고 봐도 무방하다. 이제 $a_k=x$인 $k$들을 순서대로 $v_{x,1}, v_{x,..

요즘 특징이, 풀 문제는 다 푸는데 앞에서 이상한 문제에서 시간 끌리거나 몇 번 틀려서 동 솔브자 대비 순위가 낮다는 것이다. 앳코더는 그래도 푼 시간의 max라 그 영향이 적은 반면 코포는 누적이라 그 영향이 크다. 이번 대회로 2231점이 되었고, IM이 눈앞이다. 2400을 향해... https://codeforces.com/contest/1621 A $(1, 1), (3, 3), \cdots $ 순서대로 배치하면 된다. $k>\frac{n+1}{2}$면 불가능 B 결국 양 끝점만 중요하다. 하나의 구간에 대한 최대구간과 그 최소비용, 가장 왼쪽 점이 포함된 구간과 최소비용, 가장 오른쪽 점이 포함왼 구간과 최소비용을 적당히 관리하며 답을 출력하면 된다. C 결국 어떤 자리에 대해 숫자들은 어떤 사..

퍼플따리라서 에듀가 rated contest이다. 후... C에서 좀 말려서 E를 그렇게 늦게 풀지 않았음에도 랭킹이 상당히 낮았다. 앳코더를 열심히 해서 그런지 코너 케이스나 기타처리가 좀 미숙해졌다는 걸 느꼈다. 구현실력도 줄어들고. 코포도 레드 찍기로 마음 먹었으니 힘을 더 내야겠다. 오늘 풀지 못한 F는 정수론 문제로 보였는데, 내가 정수론을 잘 몰라 정수론 문제가 나올 때마다 숨이 턱턱 막힌다. 날잡고 정수론 웰노운이나 유용한 알고리즘들을 배워야겠다. 특히 디리클레 합성곱인가 그거.. 그거 꼭 배워야지 https://codeforces.com/contest/1622 A 막대 3개가 있는데 하나를 부러뜨려서 직사각형을 만들 수 있는지 판별하는 문제다. 일반성을 잃지 않고 $a \leq b \leq..