wifilion

FFT를 이용하는 대표적 문제이다.각각의 수를 차수가 십의 자리 수가 커질수록 더 커지는 어떠한 다항식의 계수집합으로 보고, 이들의 컨벌루션을 구한다.여기서 많이 헷갈리는 부분이, 분명히 단순한 다항식 곱셈이기 때문에, 10보다 큰 수가 각각의 차수에 대한 계수로써 나타날 수 있다. 그래서 올림처리를 해 주어야 한다. 이게 사실 FFT 외에 이 문제의 핵심이다 ㅇㅇ둘 중 하나가 0일 때를 예외 처리한 코드이다.#include#define endl '\n'using namespace std;typedef long long int ll;typedef complex cpx;typedef vector vec;double pi=acos(-1);int N, M;void FFT(vec &f, cpx w){ int n..

쓰레기 슈트는 convex hull 알고리즘을 활용하는 문제이다. 이 글에서는 convex hull 알고리즘을 다루지 않으니, 이에 대해서는 다른 글을 읽고 오길 추천한다. 쓰레기 슈트 문제는, 주어진 점들로 이루어진 다각형이 있을 때, 이를 회전시켜 들어갈 수 있도록 하는 구멍의 최소 너비를찾는 문제이다(문제 설명에 쓰여 있다). 그리고, 이 문제의 AC 여부를 결정하는 가장 큰 요소는... 부동소수점.항상 부동소수점 오차를 주의하고, 반올림 함수나 올림 함수 등을 컴퓨터에 미리 구현해 놓고 필요시마다 가져다 쓰는 것도 나쁘지 않은 방법이다(실제로 본인은 그렇게 했다). 쓰레기 슈트 문제는 얼핏 보기에는 컨벡스 헐을 사용하는 문제가 아닌 듯 보일 때도 있다. 그러나, 풀이에 사용할 가정이 성립하려면 c..

하루걸림ㅇㅇ역시 실버를 풀면서 인간이 힐링을 해야지 살 맛이 나는구나...내일은 클래스 3 도장깨기 ㄱㄱ해야지클래스3는 dfs/bfs라서 그래프를 좋아하는 본인으로썬 썩 괜찮은 경험이 될 듯.이전에 못 풀었던 문제들을 지금 들여다보니까참 뭐랄까 왜 생각 못했는지...

lazy propagation을 쉽게 말하자면, 구간 업데이트 쿼리를 빠른 시간 내에 처리하기 위해 lazy한 업데이트를 사용하는 것이다. 이게 뭔 소린가 하면, 업데이트를 안하고 존버까고 있다가, lazy배열의 값을 해당 노드를 필요로 하는 시점에서 update처리해주는 기법이다. 이러면 구간쿼리를 NlogN이 아닌, 다른 쿼리에 낑겨서 들어가기 때문에 logN으로 처리할 수 있다(물론 빅 오)스위치 문제는 이러한 lazy propagation의 대표적인 예시 중 하나이다. 본인은 쿼리 문제 중 세그트리 관련 문제를 풀 때, 이 문제가 세그트리를 어떻게 써야 하는지부터 생각하는 법이다.https://www.acmicpc.net/problem/1395  아래는 이 문제를 풀 때 생각한 순서이다.1.세그트..

2-SAT문제는, 두 개씩 묶인 boolian 변수들의 AND 연산을 true로 만들 수 있는 변수들의 boolian 설정이가능한지 묻는 문제이다. 역시 글로 쓰니 어렵다. 식으로 알아보자.f: (x1∨x2) ∧(~x3∨x4)∧.... 일 때, xn을 true/false(boolian 변수이므로)로 설정해서 이 전체 식이 true가 될 수 있는지여부를 판단하는 것이다. 당신은 명제의 화살표를 그래프의 간선에 대응시킬 수 있다는 생각을 해 본적 있는가?본인도 물론 없다. 어떤 훌륭한 친구가 그런걸 생각하겠는가. 근데 누가 했대...각 절(저 괄호로 묶인 단위를 절이라 한다)이 true가 되기 위한 조건을 생각해 보자. 첫 번째 절에서, x1이 true이면? x2는 true이던지 false이던지 그게 먼 좃..

자, 오늘은 무엇을 공부했는가, 사실 오늘 한건 아니고, SCC라는 테크?닉에 대해 공부를 했다SCC는 Tarjan's algorithm으로 구현하는 방법을 학습하였다.대충 말하자면, 트리를 만들고(그래프로? 이건 좀 귀한데) 자기 자신에서 최대로 향할 수 있는 부모 정점이자신이면 SCC로 스택에서 꺼내는, 뭐 그런 식이다.SCC의 성질로부터 사이클들을 SCC로 만들고, SCC로 만든 그래프는 사이클이 없는 방향그래프가 된다.즉, DAG이다.DAG에 먼짓을 할 수 있냐?그건 위상정렬이죠. 위상정렬에 뇌가 절여지는 중이다.과고에 있을 적 cactus를 매우 좋아하는 친구가 있었다.단절점 / 단절선을 배운 다음 그 유명한 cactus를 보고 싶은 느낌이다.

dp문제다. 그것도 3차원 어떻게 어찌어찌 하다 보니까 맞았던 문제다. #include #include using namespace std; long long int a, dp[100000][5][5], minn=5; int min1, min2; vector v; int dis(int a, int b){ if(a==0 or b==0) return 2; if(a==b) return 1; if(abs(a-b)==2) return 4; else return 3; } int main(){ while(cin >> a){ if(a==0) break; v.push_back(a); } if(v.size()==0){ cout

이번 문제는 정말 오랜만에 1트 AC받은 문제이다 이 문제를 풀 때의 주의점은, 1=>2 , 2=>1로 가는 가중치 경로가 있다 해도, 갱신하면 안 된다는 것 정도이려나 아래는 코드이다. 벡터 container를 이용한 merge연산을 통해 두 벡터를 합치는 방식을 썼다. 이는 집합을 합칠 때에서 착안했다. #include #include #define INF 1e9 using namespace std; long long int n, m, map[101][101]; vector path[101][101]; vector merge(vector v1, vector v2){ vector v3; for(int i=0;i n >> m; for(int i=1;i> c >> d; if(map[b][c]

이거 한참 해메고, 또 의미를 해석하는 데에도 시간을 많이 썼다. 이는 벨만 포드 알고리즘의 "거리 계산"에 집중했기 때문으로, 이 문제에서는 그것을 요구하는 것이 아니었다.... 이 문제에서는 결국 "갱신 여부"에 집중하므로, d[i]=INF?라는 조건문을 빼버려야 하며(그러면 애초에 갱신이 안되므로) 더 나아가 애초에 d[i]를 INF로 갱신 안 해도 갱신 여부만을 판단하는 데에는 아무 문제가 없다. 그렇게 질문 계시판을 참조하여 얻은 코드는 다음과 같다: #include #define INF 1e9 using namespace std; vector a; long long int TC, N, M, W, d[501]; bool bellman_ford(void){ for(int i=1;i> TC; for..

이 카테고리는 블로그 작성자 본인이 코린이이기 때문에 설명을 써 놓은 것이 아니라 그냥 말 그대로 "일기"형식, 기록 형식입니다. 참고 바랍니다.