티스토리 뷰
ABC 209를 봤고, 5문제를 풀었다.
A번: 단순한 계산 문제이다. A>B인 경우를 생각 안 해서 한 번 틀렸다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
using namespace std;
vector<int>link[200100];
int arr[200100];
int d[200100];
int p[200100][20];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T,N, M, a, b, c;
cin >> N >> M;
vector<int>x;
int i;
cout << max(0,M - N + 1);
}B번: 전체 물건의 가격은 기본 가격의 합-N/2이다. X가 이보다 큰지 작은지 판별하면 된다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T,N, M, a, b, c;
cin >> N >> M;
vector<int>x;
int i;
for (i = 0; i < N; i++)
{
int a;
cin >> a;
M -= a - i % 2;
}
cout << (M < 0 ? "No" : "Yes");
}C번: 조합론 문제이다. 우선 C를 오름차순으로 정렬해준다. i번째가 가질 수 있는 경우의 수는 Ci-i+1개이다. 왜냐하면 1~Ci가 가능한데, 1번째에서 i-1번째까지는 쓸 수 없기 때문이다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#define int long long
using namespace std;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T, N, M, a, b, c;
cin >> N;
vector<int>x;
int i;
for (i = 0; i < N; i++)
{
int a;
cin >> a;
x.push_back(a);
}
sort(x.begin(), x.end());
int ans = 1;
for (i = 0; i < N; i++)
{
ans *= max(0LL, x[i] - i);
ans %= 1000000007;
}
cout << ans;
}D번: 퍼솔을 노리기 위해 가장 먼저 푼 문제이다. 두 사람이 움직이는 거리는 트리에서의 거리와 같고, 이 거리가 홀수면 중간에서 만나고, 짝수면 마을에서 만난다. 거리는 lca를 통해 구할 수 있다. 퍼솔은 실패하고 5번째로 풀었다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
using namespace std;
vector<int>link[200100];
int arr[200100];
int d[200100];
int p[200100][20];
void pp(int n, int de)
{
d[n] = de;
int i;
for (i = 1; i < 20; i++)
{
p[n][i] = p[p[n][i - 1]][i - 1];
}
for (i = 0; i < link[n].size(); i++)
{
if (!d[link[n][i]])
{
p[link[n][i]][0] = n;
pp(link[n][i], de + 1);
}
}
}
int lca(int a, int b)
{
if (d[a] < d[b])
swap(a, b);
int di = d[a] - d[b];
int i;
for (i = 19; i >= 0; i--)
{
if ((1 << i) & di)
a = p[a][i];
}
if (a == b)
return a;
for (i = 19; i >= 0; i--)
{
if (p[a][i] != p[b][i])
{
a = p[a][i];
b = p[b][i];
}
}
return p[a][0];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T,N, M, a, b, c, i;
cin >> N >> M;
for (i = 1; i < N; i++)
{
int a, b;
cin >> a >> b;
link[a].push_back(b);
link[b].push_back(a);
}
pp(1, 1);
while (M--)
{
int a, b;
cin >> a >> b;
int r = d[a] + d[b] - 2 * d[lca(a, b)];
cout << (r % 2 ? "Road":"Town")<<'\n';
}
}E번: 문자열을 그대로 다루기는 힘들어 보이니, 첫 3글자의 조합과 마지막 3글자의 조합을 수로 나타내자. 이러면 단어 하나는 3글자 조합에서 다른 3글자 조합으로 가는 간선이 되고, 게임은 이 그래프에서 이루어지게 된다. 결과를 예측하기 위해, 특정 단어로 이어나가야 할 때, 지는지 이기는지를 알아야 한다. 지는 경우는 이어나갈 수 없거나, 이어나가는 모든 경로가 이기는 경우로 이어지는 2가지다. 이기는 경우는 지는 경우로 이어나갈 수 있는 경우 1가지다. 나머지 경우는 모두 비기는 경로이다. 이를 구하기 위해 뒤집힌 간선들로 이루어진 그래프에서 변형된 위상 정렬을 사용한다. 처리될 조건은 지는 경우임이 확실하거나, 이기는 경우임이 확실한 경우 2가지로, 이 경우들이 나오면 상태를 저장하고 간선 뒤에 있는 노드들을 처리한다. case work 때문에 3틀 후 ac
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#define int long long
using namespace std;
vector<int>link[200000];
int lc(char x)
{
if (x <= 'Z')
return x - 'A'+26;
else
return x - 'a';
}
int stp[200100];
int enp[200100];
int pos[200100];
int cou[200100];
int vis[200100];
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T = 52 * 52 * 52;
int N;
cin >> N;
int i;
for (i = 0; i < N; i++)
{
string s;
cin >> s;
int j;
int r = 0;
int c = 1;
for (j = 0; j < 3; j++)
{
r += c * lc(s[j]);
c *= 52;
}
stp[i] = r;
r = 0;
c = 1;
for (j = 0; j < 3; j++)
{
r += c * lc(s[j+s.size()-3]);
c *= 52;
}
link[r].push_back(stp[i]);
cou[stp[i]]++;
enp[i] = r;
}
queue<int>tps;
for (i = 0; i < T; i++)
{
if (cou[i] == 0)
tps.push(i);
}
while (tps.size())
{
int a = tps.front();
tps.pop();
if (pos[a] == 0)
pos[a] = -1;
for (i = 0; i < link[a].size(); i++)
{
if (pos[a] == -1)
pos[link[a][i]] = 1;
cou[link[a][i]]--;
if ((cou[link[a][i]] == 0 || pos[link[a][i]] == 1) && !vis[link[a][i]])
{
vis[link[a][i]] = 1;
tps.push(link[a][i]);
}
}
}
for (i = 0; i < N; i++)
{
if (pos[enp[i]] == 1)
cout << "Aoki";
else if (pos[enp[i]] == -1)
cout << "Takahashi";
else
cout << "Draw";
cout << '\n';
}
}F번: 풀지는 못했지만, 이웃한 원소의 크기가 작을 경우 큰 원소부터 처리해야 한다는 관찰을 하였다.
총평: F번이 그리 어려워 보이지 않았는데 풀지 못해서 아쉽고, E번 같은 문제는 한 번에 풀 수 있도록 노력을 해야겠다는 생각이 들었다.