블로그 옮겼습니다

문제 링크 $0\lt{N}\le{10^3}$$0\lt{K}\le{10^6}$문제는 간단하다. N개의 사람이 있고 K개의 경기가 있다.모든 경기는 적어도 한명은 참가되어야하지만 딱 한사람만 참가할 수 있다.각 사람은 적어도 한 경기는 해야하고 한 사람은 여러개의 경기를 할 수가 있다.이 때 경기가 배정되는 경우의 수를 구하는 문제이다. 우선 K가 10^6인건 훼이크라는 것을 알 수가 있다. 왜냐하면 K가 N보다 크면 모든 사람에게 적어도한경기씩 배정할 수가 없기 때문이다. 그렇기 때문에 K > N 이면 바로 0 을 출력하고 넘어간다면K > T; while(T--){ memset(dp,0,sizeof(dp)); dp[0][0] = 1; cin >> N >> K; if(K > N){ cout

문제 링크 n, m, d (1 ≤ n ≤ 150000; 1 ≤ m ≤ 300; 1 ≤ d ≤ n).수직선에 1, 2, ..., n 의 장소가 있다. m 개의 폭죽이 임의의 시간과 장소에서 발사된다.주인공은 1초에 d만큼 이동할 수 있다. 시작 위치는 아무데서나 시작해도 된다.i번 폭죽이 발사될 때 주인공이 x 지점에 있을 때 얻게되는 행복은 $b_i - |a_i - x|$ 이다.이 때 모든 폭죽이 발사되고 난 후에 주인공이 얻은 행복의 양이 최대가 되도록 하고싶다.그 아랫줄부터는 m개의 폭죽의 대한 정보 ai, bi, ti 가 주어진다.ai, bi, ti (1 ≤ ai ≤ n; 1 ≤ bi ≤ 109; 1 ≤ ti ≤ 109) dp[i][j] : t_i 시간에 j 위치에 있을 때 최대 행복도\(dp[..

문제 링크 N

문제 링크 \(1 L; pos.resize(N); for(int i = 0 ; i > pos[i]; auto s = upper_bound(all(pos), 0); auto m = upper_bound(all(pos), L / 2); vector ss = vector(s, m); vector ee = vector(m, pos.end()); reverse(all(ee)); for(int i = 0 ; i

https://community.topcoder.com/stat?c=problem_statement&pm=11817 A, B, X

https://community.topcoder.com/stat?c=problem_statement&pm=11781 n

https://community.topcoder.com/stat?c=problem_statement&pm=11308 풀이를 떠올린 속도는 나쁘지는 않았는데 cache 의 초기값을 -inf 로 안주고 0으로 줬다가 디버깅하느라 시간이 좀 걸렸다. 트리의 간선의 수 N이 정해지면 모든 노드들의 degree 의 합도 2N 으로정해지기 때문에 노드 수와 degree의 합이 N+1과 2N이 되게 하는 모든 degree의 조합의 최대 점수를 dp로 계산하면 된다. 트리의 노드 수와 트리 노드들의 degree 의 합만 기준에 일치한다면 각 노드의 degree 에 대한 조합이어떻게 되던 그에 해당하는 트리를 만들 수가 있다는 사실을 캐치하는 것이 중요한 것같다.이 것만 캐치하면 dp로는 바로 연결되기때문에. 12345..

https://www.acmicpc.net/problem/1804 2*B 격자에 음식이 N개 놓여져 있다. K개의 랩을 사용하여 음식을 덮을 때 덮이는 칸의 최소 개수를 구하는 문제이다. 랩은 어느 크기로든 늘리거나 줄일 수 있다. N > K >> B; for(int i = 0 ; i > r >> c; mp[c] = mp[c] | (1

https://www.acmicpc.net/problem/11570 N N; for(int i = 0 ; i > A[i]; cout

https://www.acmicpc.net/problem/14437 정수 S 와 문자열 str 가 입력으로 주어진다. S