checklist_idea

General

  1. 연산의 가능한 최종적인 결과물이 어떠한 형태인가?(https://codeforces.com/contest/1553/problem/D) 가능한 값이 연속하는가?(KOI검은돌, 코포801C) 임의로 순서를 강제(~가 최소가 되는것 선택 등)해도 되는가?(BOJ12894)

  2. 불변량, 단조성, 볼록성, 주기성을 찾을 수 있는가?

  3. 거꾸로 생각하기

  4. 비용이 작거나 특이한 형태로 주어진다면 그 의도를 파악하자. https://codeforces.com/contest/1842/problem/E 는 특이한 비용함수때문에 DAG->트리가 되서 풀수 있음. 단, red herring은 조심.

  5. 연산들이 점점 뭉쳐서 amortized하게 복잡도가 빨라지는가? seg beats, 2023모비스예선4번

  6. 충분조건부터 해결하고 남은부분 해결 boj.kr/21045

Specific

  1. 순열에 대한 문제는 순열사이클그래프를 한번 그려보자

  2. 버블정렬에 대한 문제는 큰거를 올려보내는게 아니라 작은거가 몇번 내려가는지를 보는게 유용할 수 있다.(or vice versa) BOJ11920

  3. 사전순최소 = 앞에서부터 그리디하게 매 순간 최적인걸 골라가면 전역최적

  4. N개 수의 합이 N인 경우, classify하면 갯수가 O(sqrt(N))이다. classify할때 숫자가 크려면 숫자가 전부 다 달라야 하므로 1+2+...+K = N 일때 최대인데, 이건 K가 최대 O(sqrt(N))임.

  5. 중간만남(MITM), 3개변수일때 가운데 잡고 나머지 결정

  6. 원형문제는 대부분 [-N,N)구간을 처리하는 방식으로 구현해야됨. 2023SCPC1차3번

조합 및 확률

  1. 더블카운팅 해보기

  2. 포함배제, 어떤 and조건으로 연결된 해집합을 구할때, 어떤 set에서 위반한 조건의 개수를 -1의 지수로 해서 포함배제를 할 수 있는듯? https://atcoder.jp/contests/abc297/editorial/6183

  3. `f(x)=k개수`보다 `f(x)=k이상개수`로 정의하고 f(x)-f(x-1)구하는게 종종 더 쉽다. https://codeforces.com/contest/1527/problem/D https://codeforces.com/contest/1876/problem/B

  4. 생성함수 표현이 도움이 될수도?

  5. 회전해서 같아지면 하나의 경우: 번사이드 보조정리

  6. Linearity of Expectation = E(X+Y)=E(X)+E(Y), 확률변수들의 독립여부 상관없음

게임이론

  1. impartial게임이면 grundy를 구하자. dp가 되면 좋고, 안되면 나이브짜고 규칙찾기.

  2. partial이면 minimax dp가 되는지 보고, 안되면 전략을 찾아야함.

  3. 전략찾기팁: 선택강제, 대칭성, 불변량(General.3)

  4. partial일때 종종 선공이 뭘 고른거에 후공이 매칭해서 점수가 변화하는 세팅이 있는데, 이러면 선공의 선택순서는 의미가 없다. 선공이 어떤순서로 뭘 가져오든, 후공은 최적전략에서 가져온것에 대응되는 행동쌍을 선택하기 때문. 정말 말그대로 최소가중치매칭으로 모델링된다.

  5. 여러개에 영향있을때는 작은범위(두 개만 있을때)에서 전략을 찾고 큰 범위로 확장하기. boj.kr/25736, atcoder.jp/contests/arc163/tasks/arc163_e

기하

  1. 임의polygon triangulation은 ear decomposition으로 nlogn에 할 수 있고, triangulation의 dual은 트리이다.

  2. 맨해튼 거리 -> 45도 회전변환 -> 변환하면 거리가 |x0-x1|+|y0-y1| 에서 max(|x0-x1|,|y0-y1|)

  3. 분리축 이론: 교차하지 않는 두 다각형은 어떤 변에대한 사영에서 겹치지 않는 경우가 존재한다.

작성중