A - Shampoo
\(V\)를 \((a+b+c)\)의 합으로 나뉘어주고, 시뮬레이션을 해주면 풀 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#include <unordered_map>
#include <random>
using namespace std;
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define debug(x) cout << (#x) << " " << x << "\n";
#define compress(x) sort(all(x)); x.erase(unique(all(x)), x.end());
typedef long double ld;
typedef long long ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
#define fi first
#define se second
int dx4[4] = { 1, 0, -1, 0 };
int dy4[4] = { 0, 1, 0, -1 };
int dx8[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dy8[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
typedef complex<double> base;
const double PI = acos(-1);
template<typename T>
pair<T, T> operator+(const pair<T, T>& a, const pair<T, T>& b) { return pi(a.fi + b.fi, a.se + b.se); }
template<typename T>
pair<T, T> operator-(const pair<T, T>& a, const pair<T, T>& b) { return pi(a.fi - b.fi, a.se - b.se); }
template<typename T>
pair<T, T> operator*(const pair<T, T>& a, ll b) { return pi(a.fi * b, a.se * b); }
template<typename T>
ostream& operator<<(ostream& os, pair<T, T> p)
{
os << "(" << p.fi << ", " << p.second << ")";
return os;
}
template<typename T>
ostream& operator<<(ostream& os, vector<T>& vec)
{
for (T w : vec) os << w << " ";
return os;
}
ll ccw(pi a, pi b, pi c) { return (b.fi - a.fi) * (c.se - a.se) - (c.fi - a.fi) * (b.se - a.se); }
ll gcd(ll a, ll b) { return (!b ? a : gcd(b, a % b)); }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }
ll mypow(ll x, ll cnt)
{
if (!cnt) return 1;
ll mid = mypow(x, cnt / 2);
return mid * mid * (cnt % 2 ? x : 1);
}
void solve()
{
ll v, a, b, c; cin >> v>> a >> b >> c;
ll k = v / (a + b + c);
v -= k * (a + b + c);
if (v < a)
{
cout << "F\n";
return;
}
v -= a;
if (v < b)
{
cout << "M\n";
return;
}
v -= b;
if (v < c)
{
cout << "T\n";
return;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int tc = 1;
while (tc--) solve();
return 0;
}
|
cs |
B - Hit and Blow
문제 그대로 map을 활용해 구현해주면 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
|
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#include <unordered_map>
#include <random>
using namespace std;
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define debug(x) cout << (#x) << " " << x << "\n";
#define compress(x) sort(all(x)); x.erase(unique(all(x)), x.end());
typedef long double ld;
typedef long long ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
#define fi first
#define se second
int dx4[4] = { 1, 0, -1, 0 };
int dy4[4] = { 0, 1, 0, -1 };
int dx8[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dy8[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
typedef complex<double> base;
const double PI = acos(-1);
template<typename T>
pair<T, T> operator+(const pair<T, T>& a, const pair<T, T>& b) { return pi(a.fi + b.fi, a.se + b.se); }
template<typename T>
pair<T, T> operator-(const pair<T, T>& a, const pair<T, T>& b) { return pi(a.fi - b.fi, a.se - b.se); }
template<typename T>
pair<T, T> operator*(const pair<T, T>& a, ll b) { return pi(a.fi * b, a.se * b); }
template<typename T>
ostream& operator<<(ostream& os, pair<T, T> p)
{
os << "(" << p.fi << ", " << p.second << ")";
return os;
}
template<typename T>
ostream& operator<<(ostream& os, vector<T>& vec)
{
for (T w : vec) os << w << " ";
return os;
}
ll ccw(pi a, pi b, pi c) { return (b.fi - a.fi) * (c.se - a.se) - (c.fi - a.fi) * (b.se - a.se); }
ll gcd(ll a, ll b) { return (!b ? a : gcd(b, a % b)); }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }
ll mypow(ll x, ll cnt)
{
if (!cnt) return 1;
ll mid = mypow(x, cnt / 2);
return mid * mid * (cnt % 2 ? x : 1);
}
void solve()
{
int n; cin >> n;
map<int, int> A, B;
for (int i = 0; i < n; i++)
{
int x; cin >> x;
A[x] = i;
}
for (int i = 0; i < n; i++)
{
int x; cin >> x;
B[x] = i;
}
int one = 0, two = 0;
for (auto& p : A)
{
if (B.find(p.first) == B.end()) continue;
(B[p.first] == p.second ? one : two)++;
}
cout << one << "\n" << two;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int tc = 1;
while (tc--) solve();
return 0;
}
|
cs |
C - Collision 2
좌우로만 움직일 수 있기 때문에, \(y\)좌표가 같은 점끼리 보자. 같은 \(y\)좌표에 있는 점들 중 (왼쪽 방향, 오른쪽 방향) 인 쌍이 있다면 충돌한다. 스위핑을 이용해 적당히 구현해주자.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#include <unordered_map>
#include <random>
using namespace std;
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define debug(x) cout << (#x) << " " << x << "\n";
#define compress(x) sort(all(x)); x.erase(unique(all(x)), x.end());
typedef long double ld;
typedef long long ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
#define fi first
#define se second
int dx4[4] = { 1, 0, -1, 0 };
int dy4[4] = { 0, 1, 0, -1 };
int dx8[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dy8[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
typedef complex<double> base;
const double PI = acos(-1);
template<typename T>
pair<T, T> operator+(const pair<T, T>& a, const pair<T, T>& b) { return pi(a.fi + b.fi, a.se + b.se); }
template<typename T>
pair<T, T> operator-(const pair<T, T>& a, const pair<T, T>& b) { return pi(a.fi - b.fi, a.se - b.se); }
template<typename T>
pair<T, T> operator*(const pair<T, T>& a, ll b) { return pi(a.fi * b, a.se * b); }
template<typename T>
ostream& operator<<(ostream& os, pair<T, T> p)
{
os << "(" << p.fi << ", " << p.second << ")";
return os;
}
template<typename T>
ostream& operator<<(ostream& os, vector<T>& vec)
{
for (T w : vec) os << w << " ";
return os;
}
ll ccw(pi a, pi b, pi c) { return (b.fi - a.fi) * (c.se - a.se) - (c.fi - a.fi) * (b.se - a.se); }
ll gcd(ll a, ll b) { return (!b ? a : gcd(b, a % b)); }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }
ll mypow(ll x, ll cnt)
{
if (!cnt) return 1;
ll mid = mypow(x, cnt / 2);
return mid * mid * (cnt % 2 ? x : 1);
}
struct Q
{
int x, y, idx;
};
bool operator<(const Q& a, const Q& b)
{
if (a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
void solve()
{
int n; cin >> n;
vector<Q> arr(n);
for (int i = 0; i < n; i++)
{
cin >> arr[i].y >> arr[i].x;
arr[i].idx = i;
}
string S; cin >> S;
sort(arr.begin(), arr.end());
for (int i = 0; i < n; i++)
{
int k = i + 1;
while (k < n && arr[k].x == arr[i].x)k++;
bool right = false;
for (int j = i; j < k; j++)
{
if (S[arr[j].idx] == 'R') right = true;
else
{
if (right)
{
cout << "Yes\n";
return;
}
}
}
i = k - 1;
}
cout << "No\n";
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int tc = 1;
while (tc--) solve();
return 0;
}
|
cs |
D - Moves on Binary Tree
Up하는 연산은 \(\frac{x}{2},\) Left는 \(2*x,\) Right는 \(2*x+1\)이다. 하지만 수가 많이 커지기 때문에 무식하게 연산하지는 못한다. 그렇기 때문에 주어진 X를 LR의 경로로 나타낼 수 있고, Up하게 된다면 경로를 뒤에서 하나 빼주고, 나머지는 추가하는 식으로 관리해줄 수 있다.
결국 답은 long long 범위에 있기 때문에 쉽게 구현해줄 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#include <unordered_map>
#include <random>
using namespace std;
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define debug(x) cout << (#x) << " " << x << "\n";
#define compress(x) sort(all(x)); x.erase(unique(all(x)), x.end());
typedef long double ld;
typedef long long ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
#define fi first
#define se second
int dx4[4] = { 1, 0, -1, 0 };
int dy4[4] = { 0, 1, 0, -1 };
int dx8[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dy8[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
typedef complex<double> base;
const double PI = acos(-1);
template<typename T>
pair<T, T> operator+(const pair<T, T>& a, const pair<T, T>& b) { return pi(a.fi + b.fi, a.se + b.se); }
template<typename T>
pair<T, T> operator-(const pair<T, T>& a, const pair<T, T>& b) { return pi(a.fi - b.fi, a.se - b.se); }
template<typename T>
pair<T, T> operator*(const pair<T, T>& a, ll b) { return pi(a.fi * b, a.se * b); }
template<typename T>
ostream& operator<<(ostream& os, pair<T, T> p)
{
os << "(" << p.fi << ", " << p.second << ")";
return os;
}
template<typename T>
ostream& operator<<(ostream& os, vector<T>& vec)
{
for (T w : vec) os << w << " ";
return os;
}
ll ccw(pi a, pi b, pi c) { return (b.fi - a.fi) * (c.se - a.se) - (c.fi - a.fi) * (b.se - a.se); }
ll gcd(ll a, ll b) { return (!b ? a : gcd(b, a % b)); }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }
ll mypow(ll x, ll cnt)
{
if (!cnt) return 1;
ll mid = mypow(x, cnt / 2);
return mid * mid * (cnt % 2 ? x : 1);
}
void solve()
{
ll n, p; cin >> n >> p;
string now;
while (p != 1)
{
ll t = p / 2;
if (2 * t == p) now.push_back('L');
else now.push_back('R');
p /= 2;
}
reverse(now.begin(), now.end());
string str; cin >> str;
for (char c : str)
{
if (c == 'U') now.pop_back();
else now.push_back(c);
}
ll ans = 1;
for (char c : now)
{
if (c == 'L') ans *= 2;
else if (c == 'R') ans = 2 * ans + 1;
}
cout << ans;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int tc = 1;
while (tc--) solve();
return 0;
}
|
cs |
E - Edge Deletion (Upsolve)
플로이드 와샬로 각 쌍들의 최단 경로를 계산하자. 만약 간선 \(a b c\)가 있고, \(1 <= k <= N\)일 때, \(dst[a][k] + dst[k][b] <= c\)인 경우가 존재한다면 이 간선은 필요하지 않다.
왜냐하면 이 경우가 하나라도 존재한다면 이 간선을 사용하지 않고도, \(k\)로 우회하여 코스트 \(c\)보다 작게 움직일 수 있기 때문에 필요없다고 생각할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Line
{
int u, v;
ll c;
};
ll dst[301][301];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
for (int i = 0; i <= 300; i++)
fill(dst[i], dst[i]+301, 1e17);
int n, m; cin >> n >> m;
vector<Line> vec(m);
for (auto& p : vec)
{
cin >> p.u >> p.v >> p.c;
dst[p.u][p.v] = dst[p.v][p.u] = p.c;
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dst[i][j] = min(dst[i][j], dst[i][k]+dst[k][j]);
int ans = 0;
for (auto& p : vec)
{
bool flag = false;
for (int i = 1; i <= n; i++)
if (dst[p.u][i] + dst[i][p.v] <= p.c) flag = true;
ans += flag;
}
cout << ans;
return 0;
}
|
cs |
G - Sqrt (Upsolve)
문제를 잘 이해한다면 \(x_1, x_2, x_3\) 이런식으로 감소하게 나열하고, 자신의 다음 원소는 제곱근 이하 원소로 이루어진 수열의 경우의 수를 묻는 문제로 생각할 수 있다. 그렇다면 문제 그대로 아래 dp를 생각해볼 수 있다.
dp[i] = 현재 i일 때, 만들 수 있는 경우의 수
\(dp[1] =1\)
\(dp[i] = \sum_{j=1}^{\sqrt{i}} dp[j]\)
naive하게 구현할 경우 \(O(\sqrt{n} * \sqrt{n})\) 이 걸리지만, 바텀업으로 구간합을 만들어주면서 dp를 채운다면 \(O(\sqrt{n})\)으로 풀 수 있다.
하지만 \(\sqrt{n} = 10^9\) 이므로, 한번더 줄여야 되는데, 저 점화식에 그 다음 단계도 생각해보자는 아이디어다. \(1 <= i <= n^{\frac{1}{4}}\) 인 애들이 몇 번 나타나는 지 계산해보자. 그렇다면 아래의 점화식을 얻을 수 있다.
\(dp[i] = \sum_{j=1}^{i^{\frac{1}{4}}} (i-j*j+1)*dp[j]\)
위와 같이 구간합으로 관리한다면 \(O(n^{\frac{1}{4}})\)로 해결할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll sqf(ll x)
{
ll ans = sqrt(x) - 1;
while ((ans + 1) <= x/ (ans + 1)) ans++;
return ans;
}
ll dp[100001], psum[100001];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
dp[1] = psum[1] = 1;
for (int i = 2; i <= 100000; i++)
{
dp[i] = psum[sqf(i)];
psum[i] = psum[i - 1] + dp[i];
}
int tc; cin >> tc;
while (tc--)
{
ll x; cin >> x;
ll x2 = sqf(x), x4 = sqf(x2);
ll ans = 0;
for (ll i = 1; i <= x4; i++) ans += (x2 - i * i + 1) * dp[i];
cout << ans << "\n";
}
return 0;
}
|
cs |
'PS > Codeforces' 카테고리의 다른 글
AtCoder Beginner Contest 254 (0) | 2022.07.03 |
---|---|
Codeforces Round #777 (Div. 2) (0) | 2022.03.14 |
Codeforces Round #725 (Div. 3) (0) | 2021.12.01 |
Codeforces Round #702 (Div. 3) (0) | 2021.12.01 |
[Codeforce] Educational Codeforces Round 104 (Rated for Div. 2) (0) | 2021.12.01 |