어떤 고수 분의 정올 필기 점수가 꽤 낮다는 정보를 보았다. 기존의 KOI 1차 풀이를 적는 블로거들이나 한컴 설명회에서 공통적으로 얘기하던 것은, 실기 문제를 돌리는 것이 곧 필기 대비이고 필기 점수는 상의 색깔 정도를 좌우할 뿐이라는 것이였다. 그런데 이번 필기를 보고 생각이 바뀌었다. 정올러들은 기본적으로 틀리면 다시 제출하고, 여러 테스트를 거칠 기회를 가진 채로 연습한다. 그래서 실수 한 번에 나락을 가는 수학 문제들에 취약할 것이라고 생각한다. 결론적으로, 필기에도 시간 투자를 꾸준히 해야 한다는 것이 내 생각이다. 조합, 대수 파트 공부를 다시 해야겠다.

글을 쓰는 시점은 6월 5일 오전 1시이다. solved.ac 시즌 2가 곧 오전 6시에 시작한다. 첫 시즌 공지 때에는 목표를 2주 정도 동안 Diamond 3로 잡았다. 그런데, 정올을 망친 뒤 슬럼프를 잠깐 가지고 해서 좀 더뎌졌다. 그래서 Diamond 4로 목표를 낮췄는데, 더 우선순위인 일이 생겨 티어를 높이는 것을 중단하였다. 그래서 아쉽게 5시간 남긴 상황에서 D4 - 32로, D4 달성은 무리라 판단하고 이만 자려고 한다. 한 2주 정도 더 레이팅 올리기에 여념을 쏟지 못할 것 같다. 아무튼 시즌 2 기대된다. +) PS 일지도 한동안 OI 문제 풀이에 쏟느라 안 하고 있었는데, 이제는 좀 적을지도? +) 저번에 Bitaro's Party에 알 수 없는 이유로 cin/cout을 억까 당한..

냐 공통 부분 수열 확장 문제 링크 서브태스크 구성도 좋고, 재미있게 풀었다. 풀이 및 코드 Subtask #1: $|W|=1$(14점) 더보기 자명하다. 왼쪽 확장 경우, 오른쪽 확장 경우로 나눠서 각각 쌍이 존재하는지 확인하면 된다. 하지만 Subtask #2도 충분히 쉬우므로 한번에 긁었다. Subtask #2: $\sum |X|, \sum |Y| \le 300$(17점) 더보기 $W$의 모든 위치에 대해서 문자 $c$를 끼워 넣은 경우에도 여전히 $|X|$와 $|Y|$의 부분 수열이 되는가를 판단하면 된다. 그러면 $\mathcal O(|W|\times |C|\times (|X|+|Y|+|W|))$의 시간이 걸린다. 따라서 대충 $26\times 300^2\approx 2\cdot 10^6$번의 ..

냐 K번째 수 문제 링크 냐 풀이 더보기 사실 루트질 연습하려고 담아둔 문제인데, 그냥 세그트리로 풀었다. 이게 머지 소트 트리 맞나? 아무튼 각 노드가 구간을 커버하는 배열의 정렬된 상태를 담는데... 이렇게 하면 쿼리를 $\mathcal O(\log n)$개의 구간에 대해 각각 $\mathcal O(\log n)$의 이진 탐색을 진행하여서 총 $\mathcal O(\log^2 n)$에 응답할 수 있게 된다. ヘビの JOI 君 문제 링크 풀이 쓰기 좀 귀찮네... 생각을 풀어서 쓰려니 귀찮다. 참고로 이 문제 기여에 나는 #Case_work를 넣었다. 깔끔하게 분류 안 하면 자꾸 꼬이는 듯. 풀이 더보기 물론 다익스트라다. 뭐 다른게 나올 일도 없지 않은가... 그 상태에서 뭘 어떻게 해야되냐가 문제인..

오늘 티어 많이 올린듯 후후 JOI 국가의 행사 문제 링크 3가지 풀이가 존재한다고 한다. 참고 풀이 더보기 멀티소스 다익스트라로 전처리를 해준다. 각 노드 $v$에 대해 구한 최단거리를 $\text{value}[v]$라고 하자. 문제가 $\displaystyle \min _{\text{v}\in \text{경로}} \text{value}[v]$ 쿼리를 푸는 문제로 단순화된다. $\text{value}[v]$의 크기에 따른 크루스칼 변형을 떠올릴 수 있다. 그렇게 구성되는 스패닝 트리 위의 간선을 타는 경로가 최적이다. 따라서 구성된 스패닝 트리로 sparse table을 구성한다. 쿼리를 sparse table로 처리한다. 코드 더보기 구현이 워낙 길어져서, 모듈화시켜서 풀었다. 덕분에 디버깅 없이 1..

냠 굉장한 학생 문제 링크 풀이 더보기 각 학생은 $(a,b,c)$값을 지닌다. 만약 모든 다른 $(a',b',c')$에 대해 $a'>a,\ b'>b,\ c'>c$가 만족한다면 굉장하다. 따라서 $(a,b,c)$를 $a$에 대한 오름차순으로 정렬한 뒤, $\text{RMQ}$ 세그트리에서 $b$번 인덱스에 $c$를 넣는 식으로 관리하면 문제를 풀 수 있다. List of Unique Numbers 문제 링크 $\text{last_pos}[x]$를 관리하면서 풀면 된다. 정사각형 만들기 문제 링크 정확한 내용을 모르겠어서 디코에 질문 올렸다. 풀이 더보기 코드 더보기 #include using namespace std; #define rep(i,a,b) for (auto i=(a); i> n >> m; i..

냠 수열과 쿼리 1 문제 링크 풀이 더보기 펜윅트리에서 각각이 구간을 정렬한 상태로 갖게 하면 된다. 거기에 이진탐색. 플3 날먹..!! AtCoder Beginner Contest 250 대회 링크 거의 한 5개월 만의 앳코더다. 그동안 코포 연습한게 있어서 민트 퍼포는 나오더라. Adjacent Squares 걍 Enlarged Checker Board 걍 Adjacent Swaps 걍 250-like Number $p\times q^3\le 10^{18}$ $p^4

오늘 기분이 좀 안 좋았었는데 문제가 잘 풀려서 싹 나았다. +) 32일 스트릭 뱃지 달성 +) 세그트리 태그 티어 플래5 달성 냅색문제 문제 링크 기억에, 옛날에 못 풀고 끙끙댔던 것 같은데 오늘 풀어보니까 풀이가 바로 떠올랐고, 구현도 쉬웠다. 풀이 더보기 $N\le 30$이니까 meet in the middle을 써야 한다는 것이 보일 수 밖에 없다. $\lfloor N/2\rfloor$랑 $N-\lfloor N/2\rfloor$개로 각각 나눠서 모든 경우를 나열한 뒤에 이진 탐색으로 하나씩 확인해주면 된다. 구현도 간단해서 코드는 생략한다. 데이터 만들기 1 문제 링크 APIO 2013 기출이다. 최단경로를 입문하는 사람한테 반례에 대한 사고력을 높여줄 만한 문제들인 것 같다. 풀이. 더보기 간단..