A - Equal Hamming Distances 뜬금없이 어렵다. 초반 문제를 빠르게 못 푸는 내 성향상 더 말렸다. 그래도 WA는 안 쌓은게 어디... 최상위 코더들 코드를 확인해봤는데, 구현에 문제가 있는 것은 아니다. 그냥 속도가 느린 것. 그냥... 할 말이 없네. 쉬운 문제들 빨리 푸는 연습?을 더 해라? B - A < AP 반성해야 할 문제이다. 이번 ARC는 어려워서 빠른 2솔이 중요한데, 시간을 너무 잡아먹은 바람에 퍼포먼스가 잘 안 나왔다. (민트 중상위 퍼포) 시작할 때부터 등호 조건은 구하기 쉽네~ 이랬는데, 삽질하다가 못 알아차림... 꾸준히 스스로 지적하고, 또 조금씩 고쳐지는 것 같기도 한 습관 중에 하나인데, 풀이 방향을 섣불리 정하는 것이다. 풀이 초반에는 다양한 접근을 하..

정시 파이터는 내신 전날 [코포]를 한다~~ 잘 봤다! 4솔 직후 오렌지 퍼포가 떴는데, 대회 종로 40분 전쯤까지 오렌지 퍼포가 유지됐다. E를 보다가 케이스 분류가 상당히 많을 것 같다는 직감이 들어서 F로 넘어갈까 생각을 했다. 그래서 푼 사람 수를 확인했더니 30:40 정도 됐나 그래서 확실하게 접고 넘어갔다. F는 대충 풀이가 나오긴 했는데 자꾸 에러 뜨고 컴파일이 매우 느려져서 뭔가 vsc도 안 돌고 막 그러다가 끝났다. A. 살짝 오래 걸리긴 했는데, WA는 안 받아서 모난 데 없이 잘 푼 것 같다. B. 2분만에 풀었으니 적당한 속도로 잘 풀었다. 이 또한 모난 데 없다. C. 얘는 꽤 오래 걸렸다. 처음에 그리디 풀이가 예제에서 반례가 나와서 지우고 다시 짜느라 그런 것 같다. 이는 충분..

카카오 데이터 센터 이슈로 티스토리 사용이 안 되기 때문에 네이버 블로그에 올려본다. 오랜만에 코드포스에 들어갔다가 글로벌 라운드가 있길래 레지를 걸었다. 여태까지 두 번의 글로벌 라운드를 쳤는데, 그 두 번이 모두 핸들의 색깔을 한 단계 높이는 결과를 갖고 와서 글로벌 라운드를 좋아한다. 결과적으로 오늘도 많이 올랐다! D까지 풀었는데, ainta님이 D를 푼 뒤 40분만에 E1을 푼 걸로 봐서 대회가 40분 남은 상황에 내가 E1을 풀 가망은 없고, 인터렉티브 문제를 보면 어질어질하기도 하며, 지금 두통이 좀 있는 관계로 멈추고 대회 복기를 해보려고 한다. 참고로 평을 해보자면… 요즘 앳코더를 많이 돌렸더니 문제 퀄리티 차이가 확실히 느껴진다. 코포 D까지는 오락성이 짙은 느낌이었다. 그닥 교육적이지..

강릉에 왔다! 그냥 그렇다.. Baseball Watching 어려웠다 ㅠㅠ 회차가 $9$회 이내로 제한되고, 선택의 경우가 $3$가지라는 작은 제한을 잘 이용해야 될 것 같았다. 회차마다 $3$가지 선택을 하는걸 다르게 생각하면 $N$명을 $3$개의 집합으로 분할한 거고, 결국 $9$회 걸친 합집합의 최대 크기 및 최소 크기를 구하는 문제로 바뀐다고 생각했다. 그렇게 생각해보니 $3^9\times N$에 어느 정도의 상수가 붙은 풀이가 바로 나올 수 있었는데, 간소한 차이로 못 풀 것처럼 보였다. 다른 관찰이 그다지 보이지 않아서 이걸 조금만 최적화시켜도 풀리지 않을까 생각했다. 근데 집합을 bitset으로 관리하면 or 연산이 $N/32$~$N/64$에 된다는 얘기를 들어서 내 경우에 적용해보니 함수..

문제 링크 백설공주와 난쟁이와 비슷한 것도 같다. 물론 안 풀어봤다. 아무튼 이 문제는 랜덤 알고리즘으로 푸는 문제이다. 처음 접하는 컨셉이라 신선하고 좋다. 문제 요약 길이 $N$의 정수 sequence $A$가 주어진다. 이 때 $A$의 각 원소는 distinct하다. 자연수 $M\in [3,10^9]$을 골라 모든 $A_i$에 대해 $\mathrm{mod\ } M$을 취해줬을 때, $A$의 majority가 존재하게 하는 $M$을 찾아라. 제한 $1\le N\le 5\ 000$ $1\le A_i\le 10^9$ 문제 풀이 Monte Carlo algorithm은 적당한 시간 내에 동작하지만, 확률적으로 정답을 구하지 못할 수 있는 알고리즘을 말한다. 시간이 충분히 빠르다면 여러 번 수행함으로서 정답..

문제 링크 으... 어려워... 여태 풀었던 앳코더 문제들 중에 레이팅이 kenkooo 기준으로 제일 높다. (거의 꽉 찬 옐로우) 내가 보기에는 다이아도 줄 만한 것 같다. 발상이 너무 어렵다... 짜증나는 점이 하나 있는데, ABC 공식 풀이가 뭐가 많이 부족하다는 것이다. 잘못된 점도 많고 설명도 친절하지 않다. 문제 요약 웹 페이지에 웹 카운터는 접속 횟수를 측정한다. $i=0,1,2,\ldots,23$에 대해서, 매일 $i$시마다 다음의 접속 가능성이 존재한다. 만약 $c_i=$'T'라면 철수는 $X$%의 확률로 웹 페이지에 접속한다. 만약 $c_i=$'A'라면 영희는 $Y$%의 확률로 웹 페이지에 접속한다. $N$번째 접속이 영희에 의한 것일 확률을 $\mathrm{mod }\ 99824435..

문제 링크 Suffix array를 이용하여 "문자열 $S$의 회전 $\le$ 문자열 $T$의 회전"을 만족하는 쌍의 개수를 세는 문제이다. (단, $N=|S|=|T|$) 회전(rotate)을 관리할 때는 원래 문자열을 두 번 연속해서 붙여주는 것이 경험적으로 유용하다. 왜냐하면 붙여 만든 새 문자열의 길이가 $N$인 각 부분 문자열들이 원래 문자열의 회전이기 때문이다. 붙여서 관리하겠다는 것까지는 알겠다. 이제는 효율적으로 $S$의 회전들과 $T$의 회전들을 비교해야 한다. $S$의 회전마다 $T$의 SA에다가 이진 탐색으로 패턴 매칭을 시켜주는 것은 어떨까? 괜찮은 생각이지만 아직은 제한에 못 미친다. $S$와 $T$를 전부 때려넣고 SA를 돌릴 수는 없을까? 이게 핵심이다. $\color {red}..

좋다. 여우 신탁 오랫동안 고민한 뒤에야 맞췄다. 다양한 관찰과 접근을 시도했지만 전부 애매했다. sparse table을 이용하고 싶다는 생각도 했는데, 매번 함수가 다르기 때문에 무용지물이었다. 거꾸로 마지막 나머지들로부터 추적을 해볼까 하는 생각도 했는데, 크게 달라지는 점은 없었다. 기댓값의 선형성을 적극적으로 이용할 수 있는가도 고민해봤는데, 티어 상 그럴 것 같지도 않았고 써먹기 좋은 상황이 없었다. 사실 초반에 제수가 감소한다는 관찰을 했었는데, 이를 다시 생각해보니 쓸 만했다. 뭔가 로그 시간으로의 단축을 원했던지라 효과가 없다고 넘겼었는데, 분할 상환적으로 봤을 때 효과적이었다. 결국 풀이는 제수가 감소하는 만큼만 새 나머지로 이동시켜주면 되는 것이었다. 그러면 시간 복잡도가 분할 상환적..

교수님은 기다리지 않는다 문제 링크 쉽다. DSU를 잘 변형해서 풀면 된다. 'JOI 국가의 행사'를 풀어본게 도움이 된 것 같다. 더보기 #include using namespace std; using ii = pair; using ll = long long; #define rep(i,a,b) for (auto i = (a); i size(b)) swap(a,b), w = -w; // b에다가 a 붙여버리고 a의 값들 전부 apply for (int x : sub[a]) val[x] += w, sub[b].push_back(x); sub[a].clear(); par[a] = b; return true; } bool same(int a, int b) { return find(a) == find(b); }..