AtCoder Beginner Contest 136
알고리즘 문제풀이/AtCoder 2019. 8. 6. 02:32
Performance : 2079
Rating : 703 -> 1178 (앳코더 레이팅은 수렴하기 전까지는 빠르게 오른다. 대략 10~15번 정도 치러야 Provisional이 빠지고 대충 수렴했다고 보는듯하다)
진짜 오랫만에 해보는 ABC인데, 나름 재밌게 했다. ABC의 경우 문제간 난이도 편차가 워낙 커서 사실상 2문제 (D + E) 를 40분~1시간 정도에 풀고, 남은 시간동안 F를 생각해 본다 정도 느낌으로 라운드를 풀 생각이었는데 딱 그렇게 됐다.
A. Transfer
풀이 생략. 시키는 대로 구하면 된다.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a, b, c;
cin >> a >> b >> c;
cout << (c-min(a-b,c));
}
B. Uneven Numbers
풀이 생략. 시키는 대로 구하면 된다. 숫자가 별로 크지 않으니 그냥 전부 Manually 더하기로 했다.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
int ct = 0;
cin >> n;
for (int i = 1; i<=9; i++)
if (i<=n)
ct++;
for (int i = 100; i<=999; i++)
if (i<=n)
ct++;
for (int i = 10000; i<100000; i++)
if (i<=n)
ct++;
cout << ct;
}
C. Build Stairs
어디선가 본 문제랑 똑같은거 같은데, 대체 어딘지 잘 모르겠다. 아무튼 앞에서부터 그리디하게 내릴 수 있으면 최대한 내리는게 이득이라는걸 별로 어렵지 않게 파악할 수 있고, 이렇게 끝까지 다 내린 다음 처음부터 끝까지 돌면서 되는지 아닌지만 파악하면 OK.
#include <bits/stdc++.h>
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
int stair[101010];
int main()
{
usecppio
int n;
cin >> n;
for (int i = 1; i<=n; i++)
cin >> stair[i];
for (int i = 1; i<=n; i++)
if (stair[i] > stair[i-1])
stair[i]--;
bool ok = true;
for (int i = 1; i<=n; i++)
if (stair[i] < stair[i-1])
ok = false;
cout << (ok?"Yes":"No");
}
D. Gathering Children
길이가 최대 10만 정도인 컨베이어 벨트에 L 또는 R이 쓰여있다. L은 이 칸에 서 있는 사람이 1시간 후에 왼쪽으로 한칸 이동한다는 뜻이고, R은 오른쪽으로 1칸 이동한다는 뜻이다. 이때, 시작할 때 각 칸에 1명씩 사람이 서 있다면, $10^{100}$ 시간 후에 각 칸에는 사람이 몇 명이나 서 있을지를 구하는 문제이다.
정해와 약간 다르게 풀었다.
먼저 정해는 대략 이런 느낌인데...
- 만약에 RRR...RL..LLL 형태의 구간이 있다면, 어느정도 시간이 지나고 나면 모든 사람이 가운데 R와 L로만 모이게 된다.
- 어느정도 시간이 지나고 나면, 그다음부터는 시간의 홀짝에만 영향을 받는다.
- 투포인터 같은걸로 잘 구간을 쪼개서 관리하면서, 이 구간에 있는 사람이 충분히 큰 짝수 시간 후에 어떻게 모일지 찾으면 된다.
굉장히 자연스럽게 이런 생각들을 할 수 있지만, 사실 나는 이다음 투포인터를 어떻게 잘 써야 구현뇌절을 안 할지 고민하다가 다음과 같은 풀이를 얻었다.
$\texttt{dp[i][t]}$ 를, "처음에 $i$번째 칸에 서 있었던 사람이 $2^{t}$ 만큼의 시간이 지나면 어디에 가는가?" 라고 정의하자. 이제, 이 정보를 빨리 계산하기 위해서는, $i$ 번째 칸에 서 있었던 사람이 $2^{t-1}$ 시간 후에 어디로 가는지 먼저 파악한다. 이 칸을 $u$ 라고 하자. 이제, $u$번째 칸에 서 있었던 사람은 $2^{t-1}$ 시간 후에 어디로 가는지 알아내면 되는데, 코드로는 $\texttt{dp[i][t] = dp[dp[i][t-1]][t-1]}$ 로 간단히 쓸 수 있다. 짤때는 별 생각 없이 짰는데 결과적으로는 LCA Sparse Table이랑 비슷한 느낌?
컨베이어 벨트의 길이가 10만이므로, 10만 번 정도가 지나면 모든 사람의 위치가 둘 중 하나로 고정되게 된다. 그 후에는, 시간의 짝수 / 홀수에 따라서만 위치가 바뀌므로, 10만을 넘는 짝수 시간 후의 배치는 $10^{100}$ 시간 후의 배치와 정확히 같아진다.
나는 그냥 넉넉히 $2^{20} = 1,048,576$ 시간 후의 배치를 구했다.
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define ll long long
#define int ll
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef pair <int, int> pii;
int n;
int initposition[101010];
int position[101010][25];
int ct[101010];
string str;
int32_t main()
{
cin >> str;
n = str.length();
for (int i = 0; i<n; i++)
initposition[i] = i;
for (int i = 0; i<n; i++)
{
if (str[i] == 'L')
position[i][0] = initposition[i]-1;
if (str[i] == 'R')
position[i][0] = initposition[i]+1;
}
for (int t = 1; t<=20; t++)
for (int i = 0; i<n; i++)
position[i][t] = position[position[i][t-1]][t-1];
for (int i = 0; i<n; i++)
ct[position[i][20]]++;
for (int i = 0; i<n; i++)
printf("%lld ",ct[i]);
printf("\n");
}
E. Max GCD
나름 재밌었던 수학 문제.
$n$개의 수에 대해서, 최대 $k$번 다음과 같은 연산을 할 수 있다.
- 서로 다른 두 개의 수를 골라서, 하나는 1을 더하고, 하나는 1을 뺀다.
연산이 끝난 후, 배열 내의 모든 수의 GCD를 구한 값을 최대화해야 한다.
먼저, 모든 연산이 끝난 후 배열 내의 모든 수의 합은 절대 변하지 않음은 자명. 이 합을 $S$ 라고 하자.
배열 내의 모든 수가 어떤 정수 $g$의 배수라면, $S$도 $g$의 배수일 것이다. 따라서, 가능한 $g$의 후보는 $S$의 약수들로 압축된다. 최대 합은 5천만이고, 5천만 이하의 수의 약수의 개수는 많아야 $\log(5e7)$의 몇제곱 개 정도임이 알려져 있다. (다른 말로, 어떤 수 $x$ 이하의 수 중 가장 약수가 많은 수도 많아야 $\log^a x$ 정도의 약수를 갖는다.) 이 값이 많아야 수천개 안으로 들어올 것이다.
이제, 각 후보에 대해서 적당한 시간 ($n^2$ 이면 25만을 최대 몇천번 돌아야 하니까 약간 위험하고, 경험상 그렇게 타이트한 시간 복잡도를 주지는 않을 것이라고 믿고 아마 $n \log n$일 것이라고 추측했다.) 에 가능한지의 여부를 판정하면 된다. 당연하게도, 각 수 자체는 어차피 의미가 없고 후보 $g$로 나눈 나머지만 의미가 있으므로, 먼저 $n$개의 수에 대하여 $g$로 나눈 나머지들을 저장한 배열 $A$를 만들자.
이제, $A$에 있는 수들 중 몇개는 -1을 여러 번 해서 0으로 만들 거고, 몇개는 +1을 해서 $g$로 만들어야 한다. 이때 최소 횟수의 연산을 써야 한다. (그래야 그 최소 횟수와 $k$를 비교해서 가능한지 여부를 알 수 있으니)
어차피 +1 한번 당 -1이 따라올 것이므로, 우리는 나머지들의 합도 바꿀 수 없다. 이 "나머지들의 합" 을 $S'$ 라고 하자. 이 값은 원래 바꿀 수 없지만, 나머지 $x$를 $x-g$ 로 (즉, $g = 8$ 이 가능한지 판정하고 싶다면 3을 -5로) 보는 것은 문제가 없다. 이때, 하나를 음수로 바꿀 때마다 합이 $g$만큼 줄어들게 되므로, 적당히 $\frac{S'}{g}$ 개를 골라서 저 연산을 수행해 주면 된다. 이 과정에서 +의 개수 자체는 최소화되어야 하므로, 큰 거부터 저만큼 골라서 음수로 바꾸고, 양수들의 합을 더하면 해결. 말은 복잡하지만 코드는 비교적 어렵지 않다.
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define ll long long
#define int ll
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef pair <int, int> pii;
vector <int> arr;
int n, k;
vector <int> divisor;
bool chk(int x)
{
int r = 0;
vector <int> t;
for (auto it:arr)
{
t.push_back(it%x);
r += (it%x);
}
sort(all(t));
int ss = arr.size();
int u = r/x;
int rr = 0;
for (int i = 0; i<ss-u; i++)
rr += t[i];
return rr <= k;
}
int32_t main()
{
usecppio
cin >> n >> k;
int sum = 0;
for (int i = 0; i<n; i++)
{
int x;
cin >> x;
arr.push_back(x);
sum += x;
}
for (int i = 1; i<=(int)(sqrt(sum)); i++)
{
if (sum%i==0)
{
divisor.push_back(i);
divisor.push_back(sum/i);
}
}
int ans = 1;
for (auto it:divisor)
if (chk(it))
ans = max(ans, it);
cout << ans;
}
F. Enclosed Points
이 문제는 라운드 중에는 풀지 못했다.
$n$개의 점이 주어질 때, 이 점의 어떤 Subset을 $T$라고 하자.
이때, 각 $T$에 대해서, $f(T)$ 는 "$T$에 포함된 점들을 모두 포함하는 가장 작은 직사각형을 그릴 때, 이 직사각형이 앞서 제시된 $n$개의 점 중 몇 개를 포함하는지" 이다.
모든 부분집합 $T$에 대해서 $f(T)$의 합을 구하는 문제.
먼저, 각 부분집합에 대하여 포함되는 점의 개수를 세는 것은 너무 어려운 일이다. 또한 부분집합 자체가 $2^n$ 개 있기 때문에, 절대 시간 안에 들어오지도 않는다.
따라서, 각 점에 대하여, "직사각형을 그려서 이 점이 들어갈 수밖에 없는 부분집합의 개수" 를 세는 문제로 바꾸자. 이제, 각 점에 대해 $\log n$ 정도에 셀 수 있다면 문제를 풀 수 있다.
몇개 케이스를 종이에 그려서 확인해 보니 대략 그 점을 기준으로 왼쪽 아래 / 왼쪽 위 / 오른쪽 위 / 오른쪽 아래에 점이 몇 개 있는지 세면 어렵지 않게 포함배제의 원리를 이용해서 풀 수 있을 것 같았다. 그런데 이 점의 수를 어떻게 빨리 세지? 라운드 중에는 뭔가 적절한 자료구조가 있어서 이걸 셀 수 있을 것 같았는데 그걸 잘 몰랐다.
(세그먼트 트리로 세면 된다고 dlwocks가 알려줬다... 팬이예요!)
오랜만에 앳코더 치는데 꽤 재밌었다. 계속 뭔가를 해볼 수 있는 라운드는 그래도 좀 재밌는거 같은데, 코포에서 가끔 20분 정도 뭔가 해보고 남은 1시간 40분동안 거의 아무것도 못하는 라운드가 있는데 이런건 진짜 너무 힘들다 ㅠㅠ
'알고리즘 문제풀이 > AtCoder' 카테고리의 다른 글
| Sumitomo Mitsui Trust Bank Programming Contest 2019 (0) | 2019.12.02 |
|---|---|
| AtCoder Beginner Contest 137 (0) | 2019.08.11 |
