플레티넘 3문제 셋

플랫이랑 코포가 언레되는걸 보고 1시간 반짜리 플레 3문제를 돌기로 했다.

합산해서 2솔이다.

A - 티켓 (?, ?분)

 

너무 어려워서 못풀었다.

 

B - 천상용섬 (gunwookim, 17분)

 

dp점화식을 세웠다.

dp[i][j] : i번째 물체를 높이 j로 잘랐을때 나올 수 있는 경우의 수

이제 최적화(?)를 진행해보자

 

최적화1 - O(NH^2)

모든 방법을 하나하나 해본다.

 

최적화2 - O(280NH)

1부터 100만까지의 수중에 약수의 최대 갯수는 280개 이므로, O(NH)번 만큼 돌면서 그 전의 높이의 약수만 보면 된다.

약수를 빠르게 구하는 방법은 sqrt(N)방법으로, 미리 전처리를 해둔다.

 

최적화3 - O(280^2N)

이번엔 O(NH)번 만큼 도는게 아니라 i번째 물체의 높이도 약수만 보면 된다는 것을 알 수 있다.

이러면 O(280^2N) 풀이가 완성된다.

 

최적화4 - O(280N)

플랫이 투 포인터를 이용한 풀이를 사용했다.

정확한건 나도 모른다~

 

아래의 코드는 최적화3 코드다.

#include <bits/stdc++.h>
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pi;
int n,a[305],mod = 1e9+7;
int d[305][90005];
vector <int> p[305];
vector <int> re;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int T; cin >> T;
	while(T--) {
		cin >> n;
		re.clear();
		for(int i = 1;i <= n;i++) {
			cin >> a[i];
			p[i].clear();
			for(int j = 1;j*j <= a[i];j++) {
				if(a[i] % j == 0) {
					re.push_back(j);
					p[i].push_back(j);
					if(j*j != a[i]) re.push_back(a[i]/j), p[i].push_back(a[i]/j);
				}
			}
			sort(p[i].begin(),p[i].end());
		}
		sort(re.begin(),re.end());
		for(int i = 1;i <= n;i++) {
			for(int &j : p[i]) {
				j = lower_bound(re.begin(),re.end(),j)-re.begin()+1;
			}
		}
		d[0][0] = 1;
		for(int i = 1;i <= n;i++) {
			for(int j : p[i]) {
				d[i][j] = d[i-1][0];
				for(int k : p[i-1]) {
					if(k > j) break;
					d[i][j] = (d[i][j]+d[i-1][k]) % mod;
				}
			}
		}
		int ans = 0;
		for(int i : p[n]) ans = (ans+d[n][i])%mod;
		cout << ans << '\n';
	}
}

 

C - 욱제어 (gunwookim, 47분)

 

x를 입력받으면 cnt[x]++ 해주고,

1부터 n까지 돌면서 지금까지 남아있는 이진수를 뒤에 '0', '1'을 추가해서 2배로 불려준다.

이때 조심해야 할점은, 1000번 반복하면 2^1000개가 되기 때문에 n개이하를 유지해야 한다.

자세한건 코드를 첨부한다.

 

#include <bits/stdc++.h>
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pi;
int n;
int cnt[1005];
int p[1005];
vector <int> v[1005];
vector <string> s,t;
string ans[1005];

void dfs(int x) {
	if(x == 1001) return;
	t.clear();
	for(string i : s) {
		t.push_back(i+"0");
		t.push_back(i+"1");
		if(t.size() >= n) break;
	}
	s = t;
	for(int i = 1;i <= cnt[x];i++) {
		ans[v[x].back()] = s.back();
		v[x].pop_back(); s.pop_back();
	}
	dfs(x+1);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	for(int i = 1;i <= n;i++) {
		int x; cin >> x;
		cnt[x]++;
		v[x].push_back(i);
	}
	int tn = 2;
	for(int i = 1;i <= 20;i++) {
		if(cnt[i] > tn) {
			cout << -1;
			return 0;
		}
		tn -= cnt[i];
		tn *= 2;
	}
	cout << "1\n";
	s.push_back("0");
	s.push_back("1");
	for(int i = 1;i <= cnt[1];i++) {
		ans[v[1].back()] = s.back();
		v[1].pop_back(); s.pop_back();
	}
	dfs(2);
	for(int i = 1;i <= n;i++) {
		cout << ans[i] << '\n';
	}
}