티스토리 뷰
총 6문제를 풀면서 5번 틀렸다 ㅠㅠ
A번에서도 틀리는 걸 보면 정확성이 너무 떨어진 것 같다.
A번: 수에 0.5를 더한 뒤 내림하면 반올림이 되는데, 실수 오차를 막기 위해 0.5001을 더했다.
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
double N;
cin >> N;
cout << (int)(N+0.5001);
}B번:해싱을 이용해서 배열을 비교한 뒤 풀었는데, 그냥 배열을 set에 넣어도 된다 한다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#define int long long
using namespace std;
set<int>x;
signed main()
{
int N;
cin >> N;
int i;
for (i = 0; i < N; i++)
{
int K;
cin >> K;
int t = 0;
while (K--)
{
int a;
cin >> a;
t *= 79;
t += a+1;
t %= 7979797979797979LL;
}
x.insert(t);
}
cout << x.size();
}C번: 기본적인 dp 문제이다. i번을 배우는 시간은 max(전 기술들을 배우는 시간)+i를 배우는 시간으로 계산할 수 있다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#define int long long
using namespace std;
int dp[200100];
int r[200100];
int arr[200100][2];
vector<int>l[200100];
signed main()
{
int N;
cin >> N;
int i;
for (i = 0; i < N; i++)
{
int a,b;
cin >> a>>b;
arr[i][0] = a;
arr[i][1] = b;
while (b--)
{
int x;
cin >> x;
l[i].push_back(x);
}
}
r[N-1] = 1;
int ans = 0;
for (i = N - 1; i >= 0; i--)
{
if(r[i])
ans += arr[i][0];
int a = arr[i][1];
while (a--)
{
int x = l[i].back();
l[i].pop_back();
if (r[i])
r[x - 1] = 1;
}
}
cout << ans;
}D번: x,y의 절댓값이 서로소이면 한 번에 움직여야 하고, 아니면 x,y가 서로소가 되도록 최대공약수로 나눠줄 수 있다. 거기에다가 움직이는 방향의 부호까지 넣어 준 뒤, set을 이용해 서로 다른 움직임의 개수를 관리하면 된다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdlib.h>
#include <set>
#define int long long
using namespace std;
set<pair<int, int>>xy;
int arr[501][2];
int gcd(int x, int y)
{
return y ? gcd(y, x % y) : x;
}
signed main()
{
int N;
cin >> N;
int i;
for (i = 0; i < N; i++)
{
cin >> arr[i][0] >> arr[i][1];
int j;
for (j = 0; j < i; j++)
{
int x = arr[i][0] - arr[j][0];
int y = arr[i][1] - arr[j][1];
int xs = x < 0;
int ys = y < 0;
x = abs(x);
y = abs(y);
int g = gcd(x, y);
x /= g;
y /= g;
xy.insert({ x * (xs ? -1 : 1),y * (ys ? -1 : 1) });
xy.insert({ x * (xs ? 1 : -1),y * (ys ? 1 : -1) });
}
}
cout << xy.size();
}E번: 각 연결된 component에서 간선 개수와 정점 개수가 다르면 정답은 자명히 0이다. 아니라면 component는 사이클에 트리가 붙어있는 형태일 것이고, 사이클을 시계 방향으로 도는 것과 시계 반대 방향으로 도는 것 2가지 경우가 있을 것이다. 따라서 정답은 2^component 개수가 된다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdlib.h>
#include <set>
#define int long long
using namespace std;
int uf[200100];
int succ[200100];
int f(int n)
{
return uf[n] == n ? n : uf[n] = f(uf[n]);
}
int u(int n, int m)
{
n = f(n);
m = f(m);
if (n == m)
{
succ[n] = 1;
return 0;
}
succ[m] |= succ[n];
uf[n] = uf[m];
return 1;
}
signed main()
{
int N, M;
cin >> N >> M;
if (N != M)
{
cout << 0;
return 0;
}
int i;
for (i = 0; i < N; i++)
{
uf[i+1] = i+1;
}
int ans = N;
for (i = 0; i < M; i++)
{
int a, b;
cin >> a >> b;
ans -= u(a, b);
}
for (i = 0; i < N; i++)
{
if (!succ[f(i + 1)])
{
cout << 0;
return 0;
}
}
int rans = 1;
for (i = 0; i < ans; i++)
{
rans *= 2;
rans %= 998244353;
}
cout << rans;
}F번: dp[N][M]을 N명을 사용해서 S(P)가 M이 되도록 하는 경우의 수라고 하자. 여기서 가능한 M은 1000개 정도이고, 전이는 dp[N][M]에서 가능한 모든 크기를 해보면서 그룹을 뽑는 경우*순서를 정하는 경우를 계산한 뒤에 하면 된다. 중복 카운팅을 방지하는 방법은 그룹을 뽑을 때 무조건 가장 왼쪽 원소가 들어가게 뽑는 것이다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdlib.h>
#include <set>
#define int long long
using namespace std;
int dp[51][100000];
#define MOD 998244353
int mul(int n, int k)
{
if (k == 0)
return 1;
else if (k % 2)
{
return n * mul(n, k - 1) % MOD;
}
int a = mul(n, k / 2);
return a * a % MOD;
}
int gcd(int x, int y)
{
return y ? gcd(y, x % y) : x;
}
int check[1000010];
int revcheck[100100];
int perm[60][60];
signed main()
{
int N, K;
cin >> N >> K;
int i;
int M=0;
for (i = 1; i <=180180; i++)
{
int su = 0;
int j;
int cu = i;
for (j = 2; j * j <= i; j++)
{
int t = 1;
while (cu % j == 0)
{
t *= j;
cu /= j;
}
if (t > 1)
su += t;
if (su > N)
break;
}
if (cu>1)
su += cu;
if (su <= N)
{
M++;
revcheck[M] = i;
check[i] = M;
}
}
for (i = 0; i <= N; i++)
{
perm[i][0] = 1;
int j;
for (j = 1; j <= i; j++)
{
perm[i][j] = perm[i][j - 1] * (i - j + 1) % MOD;
}
}
dp[0][1] = 1;
for (i = 0; i < N; i++)
{
int j;
for (j = 1; j + i <= N; j++)
{
int mu = perm[N - i - 1][j - 1];
int k;
for (k = 1; k <= M; k++)
{
int cu = revcheck[k];
cu = cu * j / gcd(cu, j);
if (cu <= 1000000 && check[cu])
{
dp[i + j][check[cu]] += dp[i][k]*mu;
dp[i + j][check[cu]] %= MOD;
}
}
}
}
int ans = 0;
for (i = 1; i <= M; i++)
{
int r = mul(revcheck[i], K);
ans += r * dp[N][i];
ans %= MOD;
}
cout << ans;
}
댓글