티스토리 뷰
우선 몇 달 동안 글을 안 써서 죄송합니다.
대회 결과: 총 7솔 3틀이였고, D번 문제를 퍼솔했다. 꽤 잘 본 편이라고 생각한다.
0:00~0:03
퍼솔을 하고 싶어서 D번 문제를 먼저 봤다. 문제를 보자마자 떠오른 관찰은 정점 번호가 1018 이상이면 연산이 L이냐 R이냐는 필요가 없고, 개수만 필요하다는 것이였다.
이를 이용해서 정점 번호가 260이 넘으면 정점 번호를 260 이하로 만들기 위한 최소 U 연산 수를 저장했고, 최소 U 연산 수가 0인=정점 번호가 260 이하인 경우는 정점 번호를 그냥 저장했다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
int N, M;
cin >> N >> M;
string s;
cin >> s;
int c = 0;
int i;
for (i = 0; i < s.size(); i++)
{
if (s[i] == 'U')
{
if (c)
{
c--;
}
else
{
M /= 2;
}
}
else if (s[i] == 'L')
{
if (M * 2 > (1LL << 60))
{
c++;
}
else
M *= 2;
}
else
{
if (M * 2+1 > (1LL << 60))
{
c++;
}
else
{
M *= 2;
M++;
}
}
}
cout << M;
}0:03~0:04
A번을 봤다. 반복문과 조건문 3개를 써야 해서 평소 A보다 살짝 오래 걸리는 느낌이 들었다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
int V, A, B, C;
cin >> V >> A >> B >> C;
while (1)
{
V -= A;
if (V < 0)
{
cout << 'F';
break;
}
V -= B;
if (V < 0)
{
cout << 'M';
break;
}
V -= C;
if (V < 0)
{
cout << 'T';
break;
}
}
}0:05~0:06
B번을 보자마자 워들 생각이 났다. 워들을 풀려 가려는 욕구를 참고 셋에다가 A 에 있는 원소를 넣어서 2번을 체크하는 식으로 구현했다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
int arr[1001];
set<int>t;
signed main()
{
int N;
cin >> N;
int i;
for (i = 0; i < N; i++)
{
cin >> arr[i];
t.insert(arr[i]);
}
int x = 0,y=0;
for (i = 0; i < N; i++)
{
int a;
cin >> a;
x += arr[i] == a;
y += (t.count(a)) - (arr[i] == a);
}
cout << x << '\n' << y;
}0:06~0:10
C번을 봤다. 2차원 좌표가 나온 시점에서 살짝 귀찮아 보인다고 생각이 들었다. 워들이 더 풀고 싶어졌지만, 우선 모든 좌표들을 map<int,vector<pair<int(위치),int(번호)>>>에 넣었다.
맵의 원소 중 하나인 벡터에서 RL 부분문자열이 나오면 이 두 개가 충돌하게 된다.
실수로 fastio도 안 쓰고 unordered_map도 안 썼는데 통과한 게 신기하다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
map<int, vector<pair<int,int>>>x;
signed main()
{
int N;
cin >> N;
int i;
for (i = 0; i < N; i++)
{
int a, b;
cin >> a >> b;
x[b].push_back({ a,i });
}
string s;
cin >> s;
int ans = 0;
for (auto j : x)
{
sort(j.second.begin(), j.second.end());
int k;
for (k = 1; k < j.second.size(); k++)
{
if (s[j.second[k].second] == 'L' && s[j.second[k - 1].second] == 'R')
ans = 1;
}
}
if (ans)
cout << "Yes";
else
cout << "No";
}0:10~0:23
E번 문제를 봤다. N이 10만에 한 정점에서 시작하는 문제를 본 적이 있어서 처음 떠오른 풀이는 BCC 뇌절풀이였다. 구현하기 너무 싫어서 다른 풀이를 생각해봤다. 그러면서 두 가지 관찰을 했다.
1. a와 b를 잇는 간선의 길이보다 더 짧거나 길이가 같은 경로가 있으면 a와 b를 잇는 간선은 쓸모가 없다.
2. 그런 경로가 없으면 a와 b를 있는 최단경로는 a와 b를 있는 간선이고, 이는 대체할 수 없다.
따라서 답은 dist[i][j]>dist[i][k]+dist[j][k]를 만족하면서 i-j 사이 간선이 없는 (i,j) 쌍 개수였다.
간선이 없는 경우 처리를 안해서 1틀 후 ac
#include <bits/stdc++.h>
using namespace std;
#define int long long
int dist[301][301];
int fw[301][301];
signed main()
{
memset(dist, 1, sizeof(dist));
memset(fw, 1, sizeof(fw));
int N, M;
cin >> N >> M;
int i,j,k;
for (i = 0; i < M; i++)
{
int a, b, c;
cin >> a >> b >> c;
dist[a][b] = c;
dist[b][a] = c;
fw[a][b] = c;
fw[b][a] = c;
}
for (k = 1; k <= N; k++)
{
for (i = 1; i <= N; i++)
{
for (j = 1; j <= N; j++)
{
fw[i][j] = min(fw[i][j], fw[i][k] + fw[k][j]);
}
}
}
int ans = 0;
for (i = 1; i <= N; i++)
{
int j;
for (j = 1; j < i; j++)
{
if (dist[i][j] > (1LL << 30))
continue;
int c = 0;
int k;
for (k = 1; k <= N; k++)
{
if (k == i || k == j)
continue;
if (fw[i][k] + fw[k][j] <= dist[i][j])
c = 1;
}
if (c)
ans++;
}
}
cout << ans;
}0:23~0:46
F번은 DP인 것이 바로 생각났다. dp 점화식 구하기도 어렵지 않았다.
dp[i][j][k]는 i번째 옵션까지 보며 서로 다른 j개의 선물을 받았고 k개를 뽑았다는 것이다.
dp[0][0][0]=1이고, dp[i]를 보면서 dp[i+1][j][k]에 dp[i][j][k]를, dp[i+1][j+1][k+l]에 dp[i][j][k]*이 선택지를 뽑을 확률*(K-k)에서 (K-k-l)까지의 곱/(l!)을 더해주면 된다.
배열 크기를 잘못 잡아서 1틀 후 AC
#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[52][52][52];
#define MOD 998244353
int arr[50];
int pw(int n, int m = MOD - 2)
{
if (m == 0)
return 1;
if (m % 2)
return pw(n, m - 1) * n % MOD;
int v = pw(n, m / 2);
return v * v % MOD;
}
int pp[70];
signed main()
{
int N, M, K;
cin >> N >> M >> K;
int i;
int s = 0;
for(i=0;i<N;i++)
{
int a;
cin >> a;
s += a;
arr[i] = a;
}
for (i = 1; i <= 50; i++)
pp[i] = pw(i);
s = pw(s);
dp[0][0][0] = 1;
for (i = 0; i < N; i++)
{
int j;
for (j = 0; j <= M; j++)
{
int k;
for (k = 0; k <= K; k++)
{
dp[i + 1][j][k] += dp[i][j][k];
dp[i + 1][j][k] %= MOD;
int rmd = K - k;
int l;
int p = 1;
for (l = 1;; l++)
{
p *= arr[i];
p %= MOD;
p *= s;
p %= MOD;
if (j+1 > M || k+l > K)
break;
dp[i + 1][j+1][k+l] += dp[i][j][k] * p%MOD* rmd % MOD;
rmd *= K - k - l;
rmd %= MOD;
rmd *= pp[l+1];
rmd %= MOD;
dp[i + 1][j + 1][k + l] %= MOD;
}
}
}
}
cout << dp[N][M][K];
}0:46~0:54
G번을 봤다. 가장 먼저 한 관찰은 제3항은 sqrt(sqrt(9*1018))이하라는 것이다. 이는 10만 이하고, 다 체크할 수 있을 만큼 작다. 제2항은 제3항의 제곱~제1항의 루트 범위에 있어서, 간단한 식으로 구할 수 있다.
여기서 주의해야 할 점은 sqrt 함수가 정확도가 떨어져서, 이분 탐색 등으로 직접 구현해야 한다는 것이다. 이 때문에 1틀을 했다.
sqrt 오차만 아니였으면 최고의 문제라는 생각이 든다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[100100];
int cssq(int n)
{
int s = 1;
int e = 3000000001;
while (s != e)
{
int m = (s + e+1) / 2;
if (m * m <= n)
s = m;
else
e = m - 1;
}
return s;
}
signed main()
{
int T;
cin >> T;
int i;
dp[1] = 1;
for (i = 2; i <= 100000; i++)
{
int j;
for (j = 1; j * j <= i; j++)
{
dp[i] += dp[j];
}
}
while (T--)
{
int a;
cin >> a;
int l = cssq(a);
int ans = 0;
for (i = 1; i <= 100000; i++)
{
int v = i * i;
if (v <= l)
{
ans += (l - v + 1) * dp[i];
}
}
cout << ans << '\n';
}
}