구사과

A. Strange DeviceSubtask 1 (10점)문제에 적힌 대로 모든 순서쌍을 나열한 후, 정렬하여 서로 다른 순서쌍의 개수를 세자.Subtask 4/5 (20점)고정된 $0 \le y 각각의 구간 $[L_i, R_i]$ 에 대해서, 가능한 $q$ 의 구간을 계산할 수 있다. 가능한 $q$ 의 구간을 계산했다면, 가능한 $q \mod T$ 의 구간 역시 알 수 있다. (원형으로 넘어가는 것을 주의하도록 하자.) 결국 각 $y$ 에 대해서 가능한 $x$ 의 개수는 가능한 $q \mod T$ 의 개수랑 동일하니, 이러한 구간을 전부 추린 후, 구간 합집합을 $O(N \log N)$ 시간에 계산하면 $O(BN \log N)$ 에 문제를 해결할 수 있다.$N$ 개의 구간의 합집합을 구하는 것은, $[..

Berlekamp-Massey 알고리즘은 특정한 DP의 점화식을 찾아주는 알고리즘이다. $10^{18}$ 번째 피보나치 수를 찾기 위해서 행렬 곱셈을 짜고, 타일 채우기 문제를 풀기 위해서 수많은 점화식과 씨름하던 옛 시간은 이젠 안녕. 이제는 백트래킹 짜고 하드 코딩해서 넣으면 끝난다. 이 글은 알고리즘의 구현법, 동작 원리나 증명에 대해서 거의 설명하지 않는다. 그 이유는 내가 구현법과 동작 원리, 증명을 모르기 때문이다. 알고리즘 구현은 여기에서 복붙해서 사용하면 된다. 이론적 배경지식이 상당히 깊지만, 그 활용도가 매우 높기 때문에, 일단 이해하지 말고 작동법부터 제대로 깨우친 후, 나중에 다시 돌아와서 방법을 이해하는 것을 추천한다. 1967년 이 알고리즘을 개발한 수학자 Elwyn Berlek..

(So, 1986)가사

뭐 했는지만 대충 알 수 있는 수준의 짧은 요약글로 정리하려고 한다. 다 쓰면 너무 길다.Day1 A: NEERC 2018 B랑 매우 비슷한 General Matching. D: 특수한 그래프에서 weighted bipartite matching을 빠르게 계산하는 문제. weighted bipartite matching은 가중치가 큰 순서대로 에지를 추가하면서, 최대 매칭을 증가시키는 것만 넣어주는 식으로 계산할 수 있다. 이렇게 가중치를 없에고 최대 매칭 문제로 환원하면, ARC076F / POI Ice Skates 에 나온 유형처럼, 홀의 결혼 정리 + Segment Tree 로 해결 가능. 사실 생략한 아이디어들이 이것저것 있는데 다 적으면 너무 길어지니 생략. E: planar graph에서 ra..

블로그에 글을 쓰다 보면 캡처를 할 일이 정말 많다. 옛날에는 캡쳐를 하면 바로 파일이 생겨서 올릴 수 있었지만, 언젠가부터 캡쳐 후 저런 식으로 우하단에 썸네일을 띄워주기 시작했다. 썸네일 물론 좋으나, 썸네일이 10초동안 계속 화면에 남아 있고, 썸네일이 사라지기 전에는 파일 생성이 안된다. 저거 때문에 짜증난게 한 두번이 아닌데, 마침 얼마전에 이를 없애는 방법을 찾아서 공유하고자 한다.Cmd + Shift + 5를 누르면 캡쳐 툴이 뜬다. Shift + 3/4에 익숙한 사람들은 처음 보는 화면이 뜬다. 모하비 업데이트로 생긴 듯 하다. 옵션 -> 미리보기 썸네일 표시 를 해제한다.답답한 사람들이 많았을 것 같다. 이 팁으로 그동안 쌓인 스트레스가 다 해소되었으면 좋겠다.

practice_ptzbf 1월 22일 연습 오후: ARC 064 CDEF ainta (guest)36:3549:3343:4434:33tncks01212:4823:389:2359:19koosaga3:3097:5631:58- 실제 연습 환경에서 한 게 아니라 변동 사항이 있을 수 있다. (아인타는 약간 늦게 합류했고, 집중할 수 있는 상황이 아니었고, 등등..)하지만 내가 문제를 못 푼 건 그래서가 아니었다. 일단 D의 풀이를 보는데 한 30분 정도를 사용했고, F를 보고 풀 수 있다고 생각하고 너무 과도하게 달려들었던 것도 참패 요인이다. F는 내가 보통 거르고 보는 약수 포배 유형이다. 풀이를 들었는데 웬만큼 잘 생각하지 않았으면 못 풀었을 문제인 것 같다. 그런데 그런 유형인지를 모르고 E를 푼 이후..

관련 내용이 이 블로그에도 매우 잘 나와 있으니 같이 보면 좋을듯. 이 글에서는 LP에 대한 정의를 안다는 것을 가정하기 때문에, 정의를 모른다면 링크한 블로그를 참고해야 한다. 직관 다음과 같은 LP 문제를 생각해 보자. $\text{Maximize: } 4x + 4y$ $\text{Subject to: } x + y \leq 3,x, y \geq 0 $ 이 문제의 답은 굉장히 자명하다. $(x+y) \leq 3$ 이라는 조건이 있으니, $4(x+y) \leq 12$ 를 만족한다. 그 외에 다른 제약 조건은 $x, y \ge 0$ 뿐이니 답은 간단히 12로 결정된다. 이를 조금 더 어려운 예시로 바꿔보자. $\text{Maximize: } 4x + y $ $\text{Subject to: } x+y \..

1월 1일 심야: Petrozavodsk Winter 2018. ITMO Contest 좋은 셋이냐 하면 그건 잘 모르겠는데... 확실히 배울 건 많은 셋이었다. 그래도 이번 신년 연습 중에서는 이게 그나마 제일 정상이었던 거 같다 (...) A는 적분 식을 찾았으나 너무 복잡해서 포기했다. 하지만 그 복잡한 적분을 노가다하는게 정해였다고 한다(...) 우웩 F는 connection 정보를 관리하는 DP를 짜면, 가능한 연결 상태가 약 3000개 ~ 4000개 정도이다. 이걸 directed graph로 모델링하면, 결국 여기서 거리가 $K$ 인 walk를 찾는 문제가 된다. 이는 Berlekamp-Massey를 사용해서 해결할 수 있다. 곧 블로그에 글을 쓸 지도 모름. H는 directed mst라고..

Topcoder SRM 744 Easy는 그대로는 매우 귀찮으나, 2차원 부분합을 구할 때 쓰는 포함 배제 테크닉을 활용하면 조금 덜 귀찮아진다. 물론 그래도 귀찮다. 난 문제를 잘못 읽어서 망했다. Medium은 행과 열에 대해서 해당 행 / 열을 뒤집었는가? 를 나타내는 $n+m$ 개의 boolean 변수를 잡으면, 주어진 조건은 $X_i + X_j$ 의 홀짝성에 대한 제약조건으로 바뀐다. 이를 일종의 이분 그래프라고 생각하고 풀어주면 된다... 라는 류의 문제를 한 두 번 본게 아니어서 그냥 아무 생각 없이 코드를 짰으나 문제에 함정이 있다는 것을 늦게 깨달았다. 고치니까 150점. Hard는 큰 트리에서 특정한 형태의 선형 계획법 (LP) 를 돌리는 문제이다. small-to-large 트릭을 활..

방학동안 삼성전자 소프트웨어 멤버쉽에서 팀연습을 계속 진행하고 있다. 아래는 그 기록이다.12월 23일아침: Atcoder Regular Contest 077 C D E F koosaga 3:04 17:04 26:24 - tncks0121 4:51 21:30 45:37 - alex9801 24:20 34:13 47:11 - 점심: GP of Xian매우 말려서 루즈한 분위기로 계속 진행했는데 끝나고 나니까 등수가 기대 이상으로 높았다. 대체 왜 높을까.. * A는 풀이가 궁금한데 아무도 안 적어 준다.* B는 NEERC 2018 I와 비슷한 유형의 카운팅 문제이다. 수학 못하는 팀이라 대회 때는 아무도 안 잡았다 (그건 잘 한거 같다.) 나중에 NEERC 업솔브 할 일 있으면 비슷한 유형으로 풀어보면 좋..