sgc109’s gists

sgc109 / CF959B.cpp

Created April 7, 2018 15:52

	#include <bits/stdc++.h>
	#define pb push_back
	#define sz(v) (int)v.size()
	#define all(v) v.begin(),v.end()
	#define fastio() ios::sync_with_stdio(0),cin.tie(0)
	using namespace std;
	typedef long long ll;
	const int mod = 1e9 + 7;
	const int inf = 0x3c3c3c3c;
	const ll infl = 0x3c3c3c3c3c3c3c3c;

sgc109 / CF959A.cpp

Created April 7, 2018 15:52

	#include <bits/stdc++.h>
	#define pb push_back
	#define sz(v) (int)v.size()
	#define all(v) v.begin(),v.end()
	#define fastio() ios::sync_with_stdio(0),cin.tie(0)
	using namespace std;
	typedef long long ll;
	const int mod = 1e9 + 7;
	const int inf = 0x3c3c3c3c;
	const ll infl = 0x3c3c3c3c3c3c3c3c;

sgc109 / Zoo.cpp

Last active March 31, 2017 02:19

SRM 511 Level1 - Zoo

	#include <bits/stdc++.h>
	#define REP(i,a,b) for(int i=a;i<=b;++i)
	#define FOR(i,n) for(int i=0;i<n;++i)
	#define pb push_back
	#define all(v) (v).begin(),(v).end()
	#define sz(v) ((int)(v).size())
	#define inp1(a) scanf("%d",&a)
	#define inp2(a,b) scanf("%d%d",&a,&b)
	#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
	#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)

sgc109 / TheLuckyGameDivOne.cpp

Last active March 16, 2017 12:10

SRM 510 Level2 - TheLuckyGameDivOne

	#include <bits/stdc++.h>
	#define REP(i,a,b) for(int i=a;i<=b;++i)
	#define FOR(i,n) for(int i=0;i<n;++i)
	#define pb push_back
	#define all(v) (v).begin(),(v).end()
	#define sz(v) ((int)(v).size())
	#define inp1(a) scanf("%d",&a)
	#define inp2(a,b) scanf("%d%d",&a,&b)
	#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
	#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)

sgc109 / srm510easy.cpp

Created March 12, 2017 11:40

SRM 510 Level1 - TheAlmostLuckyNumbersDivOne

	/*
	https://community.topcoder.com/stat?c=problem_statement&pm=11461

	dp 문제이다. 꽤나 익숙한 유형중 하나이다. 어떠한 수가 있으면 맨윗자리부터 내려오면서 조건을 만족하는 가능한 숫자들의 경우의 수를 구하는문제로
	보통 문제에서 주어진 상한이나 하한을 보면서 특정 자리수가 상한보다 낮아지거나 하한보다 높아지는순간 그 뒷자리는 크기에대해 전혀 신경을 쓰지 않아도 되므로
	그에 대한 메모를 bool 형태로 memoization 해주면된다. 이 문제에서는 하한과 상한 두개 모두 있으므로 두개를 함께 따져주며 계산을 하면되고
	4나 7을 제외한 수가 최대 한번만 나올 수있다는 조건도 있으므로 지금까지 4나 7을 제외한 수가 나왔는지 안나왔는지도 함께 memoization 해주면된다
	단 아직 앞에 leading zero만 나왔을땐 4나7이 아닌수가 나왔다고 세면 안되기 때문에 이것도 memoization 해준다. 즉 bool형태의 memoization 을 4개해주고
	현재 몇자리까지 봐줬는지를 하나봐주면되는데 10^16까지니까 최대 17정도될것이다.
	그리고 지금까지는 이진수에 대해서 이렇게 윗자리부터 따져주며 세는것을 많이 봤었는데 십진수에 대해서는 처음본것같다.

sgc109 / srm509mid.cpp

Created March 12, 2017 06:29

SRM 509 Level2 - PalindromizationDiv1

	/*
	https://community.topcoder.com/stat?c=problem_statement&pm=11443

	주어진 문자열을 팰린드롬으로 만드는 dp 문제이다.
	부분문제를 정의하자면
	dp(i,j) : S[i:j] 를 팰린드롬으로 만들기위한 최소 비용

	점화식을 생각해보면 양 끝에서 부터 한글자 혹은 두글자씩 매치시키면서 양쪽 끝을 한칸 씩 좁혀나가는 식으로 구성할 수가 있다.
	어떻게 이게 가능하냐면 왼쪽끝 글자를 l, 오른쪽끝 글자를 r 이라고 했을때 l은 r과 매치시킬 수도있고 오른쪽에 새 글자를 만들어서 그것과
	매치시킬 수도있고 r을 삭제하고 r의 왼쪽 글자에대해 재귀적으로 선택할수가있다. 그렇기 때문에

sgc109 / srm508mid.cpp

Created March 11, 2017 09:25

SRM 508 Medium - YetAnotherORProblem

	/*
	https://community.topcoder.com/stat?c=problem_statement&pm=11379

	이 문제는 N개의 상한이 주어지고 그 상한보다 작거나 같은 수들을 N개 선택하여 그 N개의 합과 OR 이 같은 경우의 수를 구하는 문제이다.
	조금만 생각해보면 상한보다 작거나 같은 N개의 수를 2진수로 표현했을 때 각각의 비트가 겹치지 않는 수들의 조합을 구하라는 말과 동치임을 알 수 있다.
	그렇다면 우선 상한읜 최대 10^18 이니까 64개의 비트면 충분히 표현 가능할 것이다. 그렇다면 63번째 비트부터 차례로 내려가면서 각각의 상한을 넘지
	않도록 어떤 수에게 1을 줄 것인지를 결정하면 된다.(물론 아무 수에게도 1을 안줘도됨) 어떤 수에게 1을 줄 것인지 결정하는 부분은 그냥
	재귀 함수 내에서 반복문으로 구현하면 되는데 문제는 각각의 수마다 상한을 넘는지 넘지 않는지를 체크 해줘야 하는데 어떤 수에게 1을 주면 수가 변하기
	때문에 그에 대한 정보가 인자로 필요하다. 그런데 모든 수를 인자로 주기엔 O(64*10^19) 개의 공간이 필요하므로 힘들다.
	좀만 생각해보면 상한을 2진수로 표현했을 때 특정 자리가 1인데 그 자리에 이 수에게 1을 주지 않으면 그 아래 자리에 아무리 1을 줘도 절대 상한을

sgc109 / srm508easy(1).cpp

Created March 11, 2017 08:35

SRM 508 Level1 - DivideAndShift(1)

	/*
	https://community.topcoder.com/stat?c=problem_statement&pm=11434

	풀이1과 거의 동일한데 재귀함수의 구현 형태가 조금 다르다 풀이1 이 더 빠를것 같지만 이렇게도 생각해 볼 수 있을 것 같아서 써본다.
	처음에 길이 N인 덩어리가 있는데 이걸 길이가 1인 덩어리 까지 나누어 가는 과정을 생각해보자. 각각의 소인수들의 지수들을 모두 더한 값을 S라고해보자
	이 S가 최대한 나눌 수 있는 횟수일 것이고, 그렇다면 답은 아무리 커도 저 값보다 작거나 같을 것이다. 왜냐하면 길이가 1인 덩어리로 나눠 버리면
	우리가 가져가고자 하는 칸은 무조건 가져갈 수가 있기 때문이다. 그렇다면 나누는 순서에 대한 모든 경우의 수를 보면서 매 순간 순간 마다 중간에
	맨 왼쪽 칸과의 최소거리 + 지금까지 나눈 횟수의 최소값을 구하면 이게 답이될 것이다.

	*/

sgc109 / srm508easy.cpp

Last active March 11, 2017 08:23

SRM 508 Level1 - DivideAndShift

	/*
	https://community.topcoder.com/stat?c=problem_statement&pm=11434

	이 문제는 수학적 지식이 필요하다. 우선 문제에서 칸들이 K개가 있을 때 K의 약수이면서 소수인 수로 나눌 수가 있다고 했는데
	이것은 바로 매 회에 소인수로 한번 나눌 수 있다는 것을 의미한다. 그렇기 때문에 소인수 분해를 했을 때 소인수들의 지수 들을 모두 더한 값이
	최대한으로 나눌 수 있는 횟수인 것 이다. 그렇다면 우리가 특정 칸을 가져가기 위한 최소 횟수가 있다고 치면 그 최적해는
	몇번은 나눌것이고 몇번은 옆으로 이동시킬 것이다. 우선 나누는 행위를 먼저 보면 각각의 소인수 마다 나누는 횟수가 있을 거고 그 횟수는 0일 수도 있을것이다.
	그렇다면 각각의 소인수에 대하여 나누는 횟수들의 모든 조합에 대한 경우들을 모두 보면서
	우리가 고르려고하는 놈이 맨 왼쪽 칸으로 부터 몇 만큼 떨어져 있는지 봐서 그중 최소 값이 답이 될것이다.
	물론 맨 왼쪽 칸으로 부터 떨어진 거리는 min(좌측으로 갔을때 거리, 우측으로 갔을대 거리) 일 것이다.

sgc109 / srm507mid.cpp

Created March 9, 2017 00:56

SRM 507 Level2 - Cube Packing

	/*
	우선 1x1x1 큐브들과 LxLxL 큐브들의 부피의 총합을 구해보면
	Ns+Nb*L^3 인데 이것을 T 라고 해보자. 그럼 적어도 우리가 이 큐브들을 포장하는 하나의 큐브의 부피 V는 T보다 크거나 같다.
	그렇다면 T보다 크거나 같은 모든 V에 대해 검사해보자. 그런데 여기서 따져줘야 할 것이 세가지가 있다.
	첫번째로 큐브의 모서리의 길이를 x,y,z 라고할때 x<=y<=z 관계를 유지해줘야 셌던것을 또 안센다. 회전하면 결국 같은게 나오기때문이다.
	(그렇기 때문에 x^3 <= 2e9 일 것이다)
	두번째로 지금 보는 V의 부피가 T보다 크다 할지라도 Nb개의 큐브가 모두 들어갈 수 없는 상황이 있다. 이것을 분리 해주기 위해서
	LxLxL 큐브가 들어갈 수 있는 개수를 세어 줘야하는데 이것은 (x/L)(y/L)(z/L) 이다. 이것이 Nb보다 크거나 같은지를 봐주면된다.
	세번째로 x와 y가 정해지면 xyz가 T보다 크거나 같아야하기때문에 최소 z가 정해질텐데
	이 최소z부터 모든 가능한 z값을 다 봐주지 않아도 된다는 것이다. 딱 이거 하나만 봐주면된다. 그렇기 때문에 시간복잡도는

Wood Hwang sgc109