2024 hackercup 해커컵 후기+풀이
아쉽게 2라운드에서 500등에 들지 못해 3라운드 진출은 실패했지만 작년과 비교하면(2라운드 3000등 티셔츠도 못받음) 2000등 안에 들어 한정판 티셔츠를 받을 수 있다는 생각에 기뻤다.
Practice Round
당시 1년만의 첫 연습을 할 수 있는 기회가 생겨서 늦은 시간이지만 참여했다.
A: Walk The Line
N명이 다리를 건너는데 K시간안에 건널 수 있는지 구하는 문제이다.
할 수 있는 작업은 2가지가 있는데,
1. 한명이 si 만큼 시간이 걸려서 다리를 건너거나 수레를 들고 온다.
2. 한명은 수레에 태우고 si만큼 시간이 걸려서 다리를 건넌다.
그리고 다리를 건널려면 손전등을 가지고 건너야한다.
이 문제는 간단하게 해결 할 수 있는데, 누군가 손전등을 가지고 건너면 반드시 가지고 와야하므로
다리를 건너는데 시간이 가장 적게 걸리는 사람이 다른 사람들은 한명씩 수레에 태우고 왔다갔다를 반복하는게 최선임을 알 수 있다.
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
using namespace std;
typedef long long int ll;
int tt = 1;
void solve(){
ll n,k;
cin >> n >> k;
vector <ll> v;
for (int i = 0; i < n; i++){
ll a;
cin >> a;
v.push_back(a);
}
sort(v.begin(),v.end());
ll ans = 0;
if (n >= 2){
ans += 2*(n-2)*v[0];
}
ans += v[0];
cout << "Case #" << tt++ << ": ";
if (ans <= k){
cout << "YES" << '\n';
}else{
cout << "NO" << '\n';
}
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
freopen("walk_the_line_input.txt","r",stdin);
freopen("outt.txt","w",stdout);
int t;
cin >> t;
while(t--) solve();
return 0;
}
B: Line by Line
처음에 이 문제를 좀 해맸는데, 문제 지문이 이해가 잘 되지 않았다. 계속 읽어보니 수학적인 확률을 계산하는 간단한 문제였다.
어떤 문제의 해결 코드를 작성하기 위해 N줄의 코드를 입력해야하는데, 각각의 줄을 성공적으로 입력할 확률이 P%라고 한다.
그런데 N-1줄만 입력해서, 각각의 줄을 성공적으로 입력할 확률이 P%인 것도 존재할때, 이 두번째 상황과 확률이 같아질려면 첫번째
P를 얼마나 증가시켜야하는지 구하는 문제이다.
수학적으로 보면, ((P+L)/100)^n = (P/100)^(n-1) 을 만족하는 L이 정답인데, L에 대한 식으로 유도해보면,
L = 100x((P/100)^((n-1)/n))-P 가 된다. 처음에 이 식을 잘못 유도해서 말렸는데, 양변을 log10을 취해 안전하게 풀었다.
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
using namespace std;
typedef long long int ll;
int tt = 1;
void solve(){
long double n,p;
cin >> n >> p;
long double a = (1.0-1.0/n)*log10(p/100.0);
cout << "Case #" << tt++ << ": ";
cout << setprecision(10) << fixed << pow(10,a)*100.0-p << '\n';
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
freopen("line_by_line_input.txt","r",stdin);
freopen("outt.txt","w",stdout);
int t;
cin >> t;
while(t--) solve();
return 0;
}C: Fall in Line
최대한 한 직선에 많은 개미가 있도록 하는 문제인데, N이 백만이라 너무 컸다. 백준에 비슷한 문제가 있었지만(각 점마다 스위핑) 그걸로는 O(N^2)으로 시간초과가 나서 되지않았다. 그런데 문제 지문에 좀 수상한 말이 있었는데, 직선에 포함되지 않은 개미의 수를 M이라할때, M <= M <= 2*M 을 허용한다는 것이었다. 음... 이게 무슨말이지? 헤매다가 결국 포기하고 넘어갔다. 나중에 알고 보니 무작위 랜덤으로 직선을 골라서 포함되는 점의 개수를 계속 구해보면 문제의 정답에 거의 수렴한다고 한다. 랜덤의 사기성인가..
D1: Line of Delivery (Part 1)
이 문제를 보고 물리에서 배운 운동량과 충력량이 떠올랐는데 예시 그림이 너무 물리스러웠다.
N줄 마다 에너지Ei가 주어지는데 각 줄마다 순서대로 물체가 0부터 오른쪽으로 이동한다. 어떤 물체와 충돌하면 이동하는 물체는 멈추고 그 물체가 남은 에너지만큼 오른쪽으로 이동한다. 이때, G에 가장 가까운 거리와 그 물체 중 인덱스가 가장 작은 것을 출력하는 문제이다.
이 문제를 풀기 위한 핵심이 되는 관찰이 있는데, 계속해서 맨 왼쪽부터 오른쪽으로 물체가 이동해서 어떤 물체와 충돌하던간에, 결국 각 물체의 순서는 변하지 않는다는걸 알 수 있다. 이렇게 되면 각 물체의 위치만 잘 기록해놓은 다음에, 가능 작은 위치부터 큰 위치까지의 순서가 인덱스가 되어 O(n)에 해결가능하다.
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
using namespace std;
typedef long long int ll;
int tt = 1;
void solve(){
ll n,g;
cin >> n >> g;
vector <ll> v;
deque <ll> d;
int loc = 0;
int diff = INT_MAX;
int cur = 0;
int dex = INT_MAX;
map <ll,int> m1;
for (int i = 1; i <= n; i++){
ll a;
cin >> a;
v.push_back(a);
d.push_front(i);
m1[a] = i;
}
sort(v.begin(),v.end());
for (int i = 0; i < v.size(); i++){
if (abs(v[i]-g) <= diff){
if (abs(v[i]-g) == diff){
if (dex >= m1[v[i]]){
diff = abs(v[i]-g);
dex = m1[v[i]];
loc = i;
}
}else{
diff = abs(v[i]-g);
dex = v[i];
loc = i;
}
}
}
cout << "Case #" << tt++ << ": ";
cout << d[loc] << ' ' << diff << '\n';
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
freopen("line_of_delivery_part_1_input.txt","r",stdin);
freopen("outt.txt","w",stdout);
int t;
cin >> t;
while(t--) solve();
return 0;
}Round 1
연습 라운드때는 그저 연습용이지만 이제 본격적으로 본대회가 시작하는 첫 라운드다 보니 좀 긴장한것 같다.
1라운드는 약 2만명정도가 참가했는데, 5000등안에 들어야 2라운드에 진출한다. 이번 해커컵기준으로 적어도 2문제이상은 풀어야 진출할 수 있는것 같다.
A: Subsonic Subway
일정한 속도로 계속 이동하면서 샌드위치를 배달할때, 각 역마다 [Ai,Bi] 시간안에 모두 배달이 가능한 속도 중 가장작은 속도를 구하는 문제이다. 일정한속도(등속도)로 이동하기 때문에 이차원 좌표에서 직선의 기울기가 각 역의 시간에 모두 성립하는 직선중 기울기가 가장 작은 직선을 찾으면 된다. 각 역마다 가장 빨리 도착했을때 시간인 Ai과 Bi를 각 점의 y좌표로 잡아 구한 기울기가 가능한지 확인 후 가장 작은 기울기가 답이된다. (없으면 -1)
첫번째 문제인만큼 풀이를 떠올리기 쉬웠는데, 기울기를 비교할때 소수점으로 비교해서 소수점 오차때문에 틀렸다. 되도록 정수로 연산 후 소수로 바꾸자.
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
using namespace std;
int tt = 1;
void solve(){
cout << "Case #" << tt << ": ";
tt++;
int n;
cin >> n;
vector <pair<double,double> > v;
for (int i = 0; i < n; i++){
double a,b;
cin >> a >> b;
v.push_back({a,b});
}
double min1 = INT_MAX;
int ii = 0;
double max1 = 0;
int jj = 0;
for (int i = 0; i < n; i++){
if (v[i].first != 0) {
if (min1 > (i+1)/v[i].first){
min1 = (i+1)/v[i].first;
ii = i;
}
}
if (v[i].second != 0) {
if (max1 < (i+1)/v[i].second){
max1 = (i+1)/v[i].second;
jj = i;
}
}
}
int pass1 = 1;
// cout << min1 << ' ' << max1 << '\n';
for (int i = 0; i < n; i++){
if (!(v[i].first*(ii+1) <= (i+1)*(v[ii].first) && (i+1)*(v[ii].first) <= v[i].second*(ii+1))) pass1 = 0;
}
int pass2 = 1;
for (int i = 0; i < n; i++){
if (!(v[i].first*(jj+1) <= (i+1)*v[jj].second && (i+1)*v[jj].second <= v[i].second*(jj+1))) pass2 = 0;
}
if (pass1 && pass2){
cout << setprecision(10) << fixed << min(max1,min1) << '\n';
}else if (pass1){
cout << setprecision(10) << fixed << min1 << '\n';
}else if (pass2){
cout << setprecision(10) << fixed << max1 << '\n';
}else{
cout << -1 << '\n';
}
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
freopen("subsonic_subway_input (2).txt","r",stdin);
freopen("out7.txt","w",stdout);
int t;
cin >> t;
while(t--) solve();
return 0;
}
B: Prime Subtractorization
B번이 오히려 지문자체는 읽기도 쉽고 너무 간단했다. 개인적으로 A번보다 B번이 더 쉬운것 같기도..
관찰이 필요한 문제였는데, N이하의 도 소수의 차로 표현될 수 있는 소수를 -subtractorization 라고 설명하는데, 예를 들어,
5-subtractorization 은 5이하의 소수가 2 3 5 이므로 5 - 3 = 2, 5 - 2 = 3 이렇게 2,3 두개의 소수를 만들 수 있다. 이때 N이 주어졌을때, -subtractorization의 소수의 개수를 구해야한다. N이 최대 천만이기때문에 정말 빠르게 풀어야하는데, 뭔가 규칙이 필요하다. 이 소수는 성질이 하나있는데, 2를 제외한 모든 소수는 홀수라는것이다. 그 이유는 2를 제외한 짝수는 모두 2로 나누어떨어지기때문에 소수가 아니다. 홀수와 짝수 사이에는 또 다른 성질이 있는데, 홀수 - 홀수 = 짝수, 짝수 - 짝수 = 짝수, 홀수 - 짝수 = 홀수 가 성립한다. N이하의 소수들 중에 차로 소수가 만들어지려면 홀수 - 홀수 = 짝수로 2가 생기는 경우 나머지는 홀수 - 짝수 = 홀수 의 방식으로 만들어져야하므로 2가 아닌 홀수가 생길때마다 2를 뺐을때 소수인지만 확신해 주면서 카운팅해주면 된다. N이 최대 천만이므로 에라토스테네스의 체로 N이하의 소수를 구해 O(n)에 해결가능하다.
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
using namespace std;
int tt = 1;
int dp[10000007] = {0};
bool sosu[10000007] = {0};
vector <int> v;
void solve(){
cout << "Case #" << tt << ": ";
tt++;
int n;
cin >> n;
cout << dp[n] << '\n';
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
freopen("prime_subtractorization_input.txt","r",stdin);
freopen("out.txt","w",stdout);
for (int i = 2; i * i <= 10000000; i++){
if (!sosu[i]){
for (int j = i+i; j <= 10000000; j += i){
sosu[j] = true;
}
}
}
dp[1] = 0;
dp[2] = 0;
dp[3] = 0;
dp[4] = 0;
dp[5] = 2;
int temp = 5;
for (int i = 6; i <= 10000000; i++){
if (!sosu[i]){
if (abs(i-temp) == 2){
dp[i] = dp[i-1] + 1;
}else{
dp[i] = dp[i-1];
}
temp = i;
}else{
dp[i] = dp[i-1];
}
}
int t;
cin >> t;
while(t--) solve();
return 0;
}Problem C: Substantial Losses
기댓값 문제였는데, 뭔가 dp를 이용해서 푸는것 같았다. 그런데 문제는 입력되는 G,W 변수의 범위가 최대10^18까지여서 O(1) 혹은 로그안에 풀어야했는데 이게 가능한가... 감 조차 오지않았다. 문제 지문은 현재 몸무게가W 일때 매일 몸무게를 동일한 확률로 1을 늘리거나 줄일 수 있는데, 이때 W+L을 초과하여 몸무게를 늘릴 수 없고 몸무게가 G가 되어야한다. G를 달성하기 위해 필요한 기댓값 일수를 구하는 문제이다. 도저히 방법을 못찾겠어서 예제 입력을 봤는데 어 이게 뭐지? 뭔가 규칙이 있는것 같은데.. 예제에서 |G-W|*(2*L+1) 이 성립했다. 그래서 믿음의 제출을 했는데 맞았다. 이게 되네? 나중에 알고보니 dp식으로 유도해보면 저런 수학적인 식으로 나온다고 한다.
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
using namespace std;
typedef long long int ll;
ll mod = 998244353;
int tt = 1;
void solve(){
cout << "Case #" << tt << ": ";
tt++;
ll a,b,c;
cin >> a >> b >> c;
cout << ((abs(a-b)%mod)*((1+2*(c))%mod))%mod << '\n';
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
freopen("substantial_losses_input.txt","r",stdin);
freopen("out.txt","w",stdout);
int t;
cin >> t;
while(t--) solve();
return 0;
}
대회 때는 A,B,C 를 제출했는데, 나중에 채점할때 A가 터져서 B,C만 맞아서 아슬아슬하게 2라운드 진출은 성공했다.
Round 2
이제 본격적으로 티셔츠와 3라운드를 진출하기위한 중요한 라운드였는데, 좀 긴장되었다.
A1: Cottontail Climb (Part 1)
정수 A,B,M이 주어질때 [A,B] 에 해당하는 정수중 M으로 나누어떨어지면서 2xk+1 k >= 0 을 자릿수를 만족하는 정수중 1씩 증가하다가 감소하는 정수의 개수를 찾아야한다. 123454321 과 같이 1씩 증가하다 감소하는 정수는 그리 많지 않기에 백트래킹으로 각 자릿수에 해당하는 정수를 모두 찾아보면서 개수를 세주었다.
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
using namespace std;
typedef long long int ll;
int tt = 1;
void solve(){
cout << "Case #" << tt++ << ": ";
ll m;
string a,b;
cin >> a >> b >> m;
ll len1 = (ll)a.size();
ll len2 = (ll)b.size();
ll cnt = 0;
// if (stoll(a) <= 0 && 0 <= stoll(b)) cnt++;
for (ll i = 0; i < 10; i++){
if (2*i+1 >= len1 && 2*i+1 <= len2){
ll fi = (2*i+1)/2;
ll se = (2*i+1)/2+1;
for (ll k = 1; k <= 9-se+1; k++){
string temp2;
string temp;
for (ll p = k; p <= k+se-1; p++){
temp += p+'0';
temp2 += p+'0';
}
temp2.pop_back();
reverse(temp2.begin(),temp2.end());
temp += temp2;
ll ans = stoll(temp);
if (stoll(a) <= ans && ans <= stoll(b) && ans % m == 0) cnt++;
}
}
}
cout << cnt << '\n';
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
freopen("cottontail_climb_part_1_input.txt","r",stdin);
freopen("outtttttt.txt","w",stdout);
ll t;
cin >> t;
while(t--) solve();
return 0;
}A2: Cottontail Climb (Part 2)
전 문제보다 좀더 강화된 버전이다. 이번엔 1씩증가하다 감소하는것이 아닌 증가하다 감소하는 것의 개수를 구해야한다. 이러면 가능한 정수가 너무 많아지기에 시간이 안될것 같았는데, 마지막 제출 과정에서 제한시간 6분동안 2분을 기다리니 정상적으로 출력이 되어서 제출했다.(이게 되네)
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
using namespace std;
typedef long long int ll;
int size1 = 0;
ll l = 0;
ll r = 0;
ll cnt = 0;
ll mod = 0;
void dfs(int k, string a){
if (k >= size1){
ll pp = stoll(a);
if (l <= pp && pp <= r && pp % mod == 0) {
cnt++;
}
return;
}
if (k == size1/2){
for (char j = a.back()+1; j <= '9'; j++){
dfs(k+1,a+j);
}
}else if (k < size1/2){
for (char j = a.back(); j <= '9'; j++){
dfs(k+1,a+j);
}
}else{
if (k == size1/2+1){
for (char j = a.back()-1; j >= '1'; j--){
dfs(k+1,a+j);
}
}else{
for (char j = a.back(); j >= '1'; j--){
dfs(k+1,a+j);
}
}
}
}
int tt = 1;
void solve(){
cout << "Case #" << tt++ << ": ";
ll m;
string a,b;
cin >> a >> b >> m;
ll len1 = (ll)a.size();
ll len2 = (ll)b.size();
cnt = 0;
l = stoll(a);
r = stoll(b);
mod = m;
// if (stoll(a) <= 0 && 0 <= stoll(b)) cnt++;
for (ll i = 0; i < 10; i++){
if (2*i+1 >= len1 && 2*i+1 <= len2){
size1 = 2*i+1;
for (char j = '1'; j <= '9'; j++){
string temp;
temp += j;
dfs(1,temp);
}
}
}
cout << cnt << '\n';
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
freopen("cottontail_climb_part_2_input.txt","r",stdin);
freopen("outtttttt.txt","w",stdout);
ll t;
cin >> t;
while(t--) solve();
return 0;
}B: Four in a Burrow
게임 이론문제였는데, 서로 돌을 놓아 꽉차서 끝난 상태의 판이 주어질때 승패여부를 출력하는 문제이다. 6X7 크기의 판이기 때문에 두 명다 가로로 돌을 놓아 4개씩 빙고를 하면 가장 맨 밑에서 4개가 연속으로 있는 사람이 이기게 된다. 나머지 경우 대각선 세로, 혼합 여러가지 경우의 수가 있었는데, 어찌저찌 구현하고 예시를 하드코딩해서 제출했는데 틀렸다. 너무 빡구현 문제 같았다.
후기
1년만에 다시해보는 해커컵이었는데, 1라운드에서 A를 틀려서 망했나 싶었지만 2라운드에서 A2까지 빠르게 풀고 B의 테스트케이스가 약해서 그런지 다 텨져버려 순위가 너무 올랐다. 1000등 안에 드는건 본 라운드에서 처음해보는 기록이었는데, 한정판 티셔츠를 받을 수 있다는 것이 기쁘다. 못풀었던 문제를 나중에 업솔빙하면서 풀어보고 다음번에는 코드포스 블루이상을 찍은 실력을 가지고 3라운드에 진출하고 싶다.