PS | 0731 ~ 0806 | 2022

8월 5일부터 일정이 있어서 PS를 당분간 못할 가능성이 높다.

1557 제곱 ㄴㄴ

기회가 되서 풀게 됐다.
옛날엔 감도 안잡힐 정도로 어려운 문제였는데 지금은 쉽게 풀이가 떠오르는게 기분이 매우 좋다.

내 풀이는 DB 풀이인데 Segmented Sieve를 사용한다.
https://www.acmicpc.net/problem/1016 를 풀고 나면 적당한 min, max만 찾으면 된다는 생각을 할 수 있다.
그 min,max를 구하기 위해 구간을 적당한 블록(2*10^6 정도)로 나눠주고 각 블록의 제곱 ㄴㄴ수의 개수를 구하는 것이다. 미리 전처리를 해놓고 (블록의 크기에 따라 다르겠지만 나의 경우 2000개의 수를 저장)  구간을 찾은 뒤 만들어놓은 체로 K번째 제곱ㄴㄴ수를 구해주면 된다.
내 풀이(DB 코드는 주석으로)

https://www.acmicpc.net/source/15060254과 https://www.acmicpc.net/source/33520604과 같은 풀이는 어떤 풀이를 쓴건지 잘 모르겠다.

뫼비우스 함수 쓴거 같은데 후에 정수론 팔 때 다시 풀어보려고한다.

 

16644 Easy Problem 

사실 제곱 ㄴㄴ 수라는 것이 정수론 쪽에서 꽤 유명한 문제다.

https://en.wikipedia.org/wiki/Square-free_integer#Table_of_Q(x),_6/%CF%802x,_and_R(x)

구간을 훨씬 쉽게 구할 수 있게 됐다. 적당한 R(x)를 예상해주면 된다.
라고 생각했으나
정확한 Q(x)를 구하는 것은 전혀 다른 문제이므로 더 고민이 필요하다.

 

밸런스 Scales ,

고등학교 1학년 고급알고리즘 방과후 시간에 경기과고 출신 선생님(외부강사)가 오셔서 자기가 가장 인상깊었던 문제(지금 생각해보면 그때 딱 우리 수준의 문제 중 가장 인상적인 것을 고르신 느낌)라고 OJ에 들고온 문제다.
정해가 커팅이라 하셨는데 지금 다시 보니 애초에 데이터가 약해서 (N이 1000까지라 되어 있는데 1000은 커녕 46보다도 작은 데이터 뿐이다) 기본적인 커팅( ans 갱신 dfs)만으로도 답이 나온다.
인줄 알았더니
a_i >= a_i-1 + a_i-2라는 조건이 있어서 n 최대가 46 언저리가 맞다.

#include<stdio.h>
int n,c,a[101];
int min(int a,int b){
    return a<b?a:b;
}
int f(int mi,int id){
    if(mi<0) return 1<<30;
    if(id==0){
        if(mi-a[id]>0) return mi-a[id];
        else return mi;
    }
    if(mi>a[id]*2.7)
        return f(mi-a[id],id-1);
    else
        return min(f(mi,id-1),f(mi-a[id],id-1));
}
int main(){
    scanf("%d%d",&n,&c);
    for(int i=0;i<n;i++)
        scanf("%d",a+i);
    printf("%d",c-f(c,n-1));
}

피보나치 수의 성질에 따라

Fi들의 누적합을 Si라 하면
Sn = F_n+2 - 1
이고 Fi+1/Fi는 황금비에 수렴하기 때문에 (1.618...)
Sn ~ Fn *  ϕ *  ϕ < Fn*2.7 인걸 확인했고
그래서 이제 대충 현재 누적합보다 크면 a[id]를 쓴다는 논리다.
그런데 막상 생각해보면 그냥 처음부터 누적합을 저장해두면 되기 때문에(...1)
알고리즘 상으로는 쓸모가 없고 증명할 때 도움이 되겠다.

현재 남은 값이 a[i] * 2.7보다 작을 때만 2개로 분기된다는 얘기
누적합 쓰는 풀이도 이와 비슷하므로 잘 하면 저격데이터 만들 수 있을거 같은데 귀찮다...

 

고등학교 OJ에 있는 이상한 문제

https://code.sasa.hs.kr/problem.php?id=1305 

내 분석 상 정해는 FFT.
FFT를 아는 분이 있었다는 것도 놀라운데, 데이터가 약해서 네이브 솔루션이 0ms가 나온다는 점이 황당하다 ㅋㅋ
오랜만에 code sasa 전체적으로 둘러봤는데 문제 상태를 보면 그 많은 문제를 푼 내게 존경심이 생겨난다. 

 

rkm 정수론 1강

https://www.acmicpc.net/problem/16532 

이 문제가 진짜 재밌다.

오프라인 쿼리 (세그/펜윅 이용 -> K에 대해 정렬하고 K보다 큰 소수들에 대해 체 칠하기. 이때 체를 세그로 만들어준다.)
온라인 쿼리 (머지소트 트리 이용)
나이브(+ 최적화)
모두 통과하는 신기한 문제

 

이건 내 풀인데 Q가 작은 점을 이용해 적당히 O( Q * (N까지 소수 개수) )로 문제를 해결한다.
K*K >= N일 때와 K*K<N일 때를 나누어 처리해준다.
K*K >= N 일 때는 K 초과의 소수에 대해 그 소수가 최대소인수인 수들의 개수는 floor(N/K)이므로 그냥 더해준다음 N-1에서 빼주면 되고, K*K<N일 때는 K 이하의 소수에 대해 그 소를 최대소인수로 가지는 수들 중 N 이하인 수의 개수를 더해주면 된다.
다시 생각해보면 괜히 K로 분할한다는 생각을 해서 세그도 못 쓰고, 머지소트 트리도 못 쓰고 괜히 스탠스가 애매해졌다 ㅋㅋㅋㅋㅋㅋ
첨에 약 600ms로 통과해서 데이터가 약해서 겨우 뚫었네 했는데, 다시 보니 K*K 조건 검사할 때 오버플로우가 났었다(...) 그래서 조건문을 바꾸고 다시 제출하니 292ms가 나왔고, 나름 안정적이다.

이제 애매한 내 풀이와 차원이 다른,

내 풀이의 극극극극극극 상위호환 풀이를 가져왔다.
K*K>=N일 때 조화수열 이용한 것도 레전드지만, K*K<N일 때 부분문제로 쪼갠게 정말 감동,,

#include<bits/stdc++.h>
using namespace std;
vector<int> primes;
bool comp[100005];
int pre[100005];
int f (int n, int k) {
	if (n <= 0) return 0;
	if (n == 1) return 1;
	if ((long long)k * k >= n) {
		int ret = n;
		for (int v = 1; v * v <= n; v++) {
			int L = n/(v+1), R = n/v;
			if (R <= k) break;
			ret -= v * (pre[R] - pre[max(L,k)]);
		}
		return ret;
	}
	int ret = 1;
	for (int p : primes) if (p <= k) ret += f(n/p,p); else break;
	return ret;		
}
int main () {
	for (int i = 2; i <= 100000; i++) {
		pre[i] = pre[i-1];
		if (!comp[i]) {
			if ((long long)i * i <= 100000)
				for (int j = i * i; j <= 100000; j += i)
					comp[j] = true;
			primes.push_back(i);
			++pre[i];
		}
	}
	int q; scanf ("%d",&q);
	while (q--) {
		int n,k; scanf ("%d %d",&n,&k);
		printf ("%d\n",f(n,k)-1);
	}
	return 0;
}

다른 사람들 다 오프라인 쿼리에 이상한 자료구조 쓰고 있을 때 혼자 압도적으로 적은 메모리로 압살한다.

for (int p : primes) if (p <= k) ret += f(n/p,p); 이 부분이 진짜 레전드