Beginner Division 1등했습니다!
팀명 LibraryOfRuina로 (스팀에 있는 그 Project Moon게임 맞습니다 최근 하고 있는데 재밌네요)
+ (최근 햄햄팡팡도 갔다왔는데 그 후기도 언젠가 쓰겠습니다 조만간)
5문제 퍼솔 할 수 있었는데 A에서 실수한게 아쉽네요 :blobsad:
재밌는 셋 만들고 대회 주최하신 임원진 분들께 감사합니다
문제들은 여기서 (https://codeforces.com/group/E3SmB8bN1L/contest/382314) 직접 풀어보실수 있습니다!
(마지막 제출은 대회 끝나고 테스트용이였습니다)
[A] 수열의 주인 00:04 - WA
읽자마자 16으로 나눈 나머지를 활용하는 풀이가 생각나서 구현후 제출했습니다!
하지만 사실 그 구현에는 실수가 있었지만 제출 당시 발견하지 못했고 그렇게 맞았다고 생각하고 넘어갔습니다.
[B] 계단 초능력 (easy) 00:07 - AC
A를 제출해놓고 다음은 B를 봤습니다.
BOJ에도 올라와있는 설탕배달 (https://www.acmicpc.net/problem/2839) 과 동일한 문제입니다. 풀이를 알고있는 문제이니 바로 구현에 들어갔습니다.
우선 우리는 계단을 두가지 방법으로 오를수 있습니다.
1. 한번에 88칸
2. 한번에 138칸
그리고 최소 소요시간을 만들기 위해서 우리는 138칸을 한번에 올라가는 횟수를 최대화 시켜야 합니다.
하지만 그 횟수를 찾기 위해 0층부터 시작해서 138칸씩 올라가는 방법은 적합하지 않습니다. 대신에 우리는 N번째 층에서 88칸 씩 내려오는 방법을 택해야 합니다.
88칸씩 내려오다가 138로 나누어 떨어지는 칸에 도달할시, 그 칸을 n번째 칸이라 했을때 우리는 그 칸에 n/138번으로 가장 빨리 도착할수 있습니다. 여기서 주의해줘야 할게 88칸씩 내려오다가 음수의 칸 (애초에 그런 칸은 존재할수 없으니까요) 까지 가버리는 경우가 생긴다면 138로 나누어 떨어지는 경우가 존재하지 않았다면 그 층에는 저 두가지 방법으로 갈 수 없습니다.
한가지 더 기억할점은 0은 138로 나누어 떨어진다는 점입니다. (즉 138번 올라가는 횟수가 0번이 최적인 칸도 존재할수 있습니다)
#include <bits/stdc++.h>
using namespace std;
int n,ans;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
while(n%138!=0 && n>0){
n -= 88;
ans++;
}
ans += n/138;
if(n%138==0) cout << ans;
else cout << -1;
}
그리고 이 시점에서 [A]를 틀렸다는 사실을 알게 되어서 A를 고치러 돌아갔습니다.
[A] 수열의 주인 00:08 - AC
구현에 따라 예외처리가 필요없을수도 있고 까다로울수도 있습니다. 저도 처음에는 구현을 잘못해서 예외처리 부분에서 틀렸습니다.
우선 지문에 나와있듯이 주어진 수열은 길이 16의 수열 {0, 1, 2, 0, 1, 3, 0, 1, 4, 0, 1, 3, 0, 1, 2, 2} 이 반복됩니다.
즉 수열의 n번째 항은 n%16번째 항과 동일합니다. 다만 구현을 할때 arr[n%16]을 출력하게 되면 n이 16의 배수인 경우 0번째 index를 가르키게 되니 맨 앞에 16번째 항인 2를 붙여서 {2, 0, 1, 2, 0, 1, 3, 0, 1, 4, 0, 1, 3, 0, 1, 2, 2} 의 n%16번째 항을 출력하게 바꾸면 됩니다.
아마 대회중에는 저렇게 안 풀었을거고 그냥 if(n%16==0)예외처리 박았을겁니다. Domjudge특성상 그때 제출한 코드를 확인 못해서 아쉽네요 :blobsad:
사실 여기서 망한줄 알았습니다. 틀린 문제에 대한 페널티가 20분이나 되기 때문에 푼 문제수로 1등할게 아니면 1WA로 인해 순위에서 밀려날수도 있었거든요.
#include <bits/stdc++.h>
using namespace std;
int t;
int arr[17] = {2, 0, 1, 2, 0, 1, 3, 0, 1, 4, 0, 1, 3, 0, 1, 2, 2};
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> t;
while(t--){
int n;
cin >> n;
n%=16;
cout << arr[n] << '\n';
}
}그리고 이 시점에서 C를 읽어봤습니다. 딱봐도 분할정복을 이용한 별찍기더군요 해본적도 없고 할 자신도 없어서 빠르게 넘어가고 D, E, F를 읽어봤습니다. D는 딱봐도 누적합 문제였고 F는 뭔가 간단하게 풀리는 수학 문제일거 같더군요. 셋중에 가장 어려워 보인 E는 일단 던져두고 D,F를 동시에 잡았습니다.
[D] 지하철 요금 00:20 - AC
둘중에 확실하게 풀이가 떠오른 D부터 구현에 들어갔습니다. 다만 여기서 문제에 부딪혔습니다. 무지성 누적합->부분합 구현을 하니 답이 제대로 안나오던것입니다. 문제를 다시 읽어본후 두가지를 깨달았습니다.
1) 입력 수열 의 i번째 항은 i에서 i+1번째 역으로 가는 거리이다
2) 출발역의 숫자가 도착역보다 작다는 보장이 없다
그래도 저 두가지를 금방 고치고 제출해서 맞았습니다.
특히 저 2번을 고치는 방법은 구간합을 찾을때 그냥 출발, 도착중 더 큰거에서 더 작은걸 빼주는 식으로 처리해주면 깔끔합니다.
아 그리고 거리에 10을 곱해주는거도 까먹지 맙시다.
#include <bits/stdc++.h>
using namespace std;
int n,m;
int dist[150005];
int dp[150005];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i=1; i<n; i++) cin >> dist[i];
dp[1]=dist[1];
for(int i=2; i<=n; i++){
dp[i] = dp[i-1] + dist[i-1];
}
cin >> m;
while(m--){
int st, en;
cin >> st >> en;
cout << (dp[max(st,en)] - dp[min(st,en)])*10 << '\n';
}
}
[F] 해의 존재성 00:29 - AC
D를 풀고 다시 F를 잡았습니다. 문제를 읽다보니 뭔가 익숙하다는 느낌은 들었는데 PS에서는 본적 없는거 같고... 감이 쉽게 안 왔습니다. 그런데 생각 났습니다. 확실히 PS에서 본적은 없지만 고등학교 수학에서는 본적 있는 문제였습니다.
a+b = x, ab = y 즉 x는 a,b를 해로 가지는 2차방정식의 두 해의 합, y는 두 해의 곱이였습니다. 그리고 두해의 합, 곱, 이차 방정식의 계수와의 관계를 사용하면 -x는 일차항의 계수 y는 상수항입니다.
즉 서로 다른 해 a,b가 존재한다는 것은 x^2 - 4y > 0이라는 의미입니다.
그리고 그걸 그대로 구현해 맞았습니다.
#include <bits/stdc++.h>
using namespace std;
int t;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> t;
while(t--){
long long int x,y;
cin >> x >> y;
if(x*x-4*y>0) cout << "Yes\n";
else cout << "No\n";
}
}
이 시점에서 확인해보니 3솔은 커녕 2솔도 거의 없길래 조금 긴장을 풀게 되었습니다. 그래도 방심할수는 없는 상황이기에 C, E 둘중 하나를 풀어야 겠다고 생각했습니다. 둘중 처음 고민해본거 C지만 도저히 아무리 봐도 너무 풀기 싫고 못 풀거 같아서 E를 잡기로 했습니다.
[E] 공정한 거래 01:20 - AC
29분에서 80분 경과 까지 이 문제 하나 푸는데만 51분을 사용했습니다. 개인적으로 절대 간단한 문제는 아니였다고 생각합니다.
일단 이 문제는 dp문제중에서도 0-1 knapsack 이라는 문제입니다. 저 문제 종류 자체에 대해 더 관심이 있으시다면 https://www.acmicpc.net/problem/12865 를 확인해봅시다.
12865번: 평범한 배낭
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)
www.acmicpc.net
처음 이 문제를 읽었을때는 간단한 조합 문제라 생각했습니다. 하지만 예제 입출력을 보니 두가지 의심이 들었습니다.
1) 광물의 가치가 중복될수 있나?
2) 가치들의 합도 중복될수 있나?
믿져야 본전으로 문의를 넣었는데 문의를 기다리는 동안 2번은 확실하게 존재한다는걸 깨달았습니다. 그리고 곧 이후 답변이 왔는데...
답변할수 없다는 답변이 왔습니다. 하지만 오히려 덕분에 확실하게 중복되는 경우가 있다는 의미로 해석하고 접근하게 되었습니다.
일단 어떠한 조합 i가 가능하다면 i에 i에 아직 포함되지 않은 수를 더한 조합도 가능합니다.
따라서 앞에서 부터 주어진 가치들을 확인해주면서 현재 가치 x를 보고있고 합 i가 가능하다는것을 알고 있다면 i+x도 가능하다는것을 알 수 있습니다.
그러므로 이차원 bool타입의 dp배열을 만들고 dp[i][j]를 "i번째 수까지 확인한 시점에서 합 j가 가능한지 불가능한지에 대한 여부" 로 정의할겁니다. 그러므로 만약 dp[i][j]가 참이라면 dp[i+1][j]와 dp[i+1][j+cost[i]] 도 참이 됩니다.
다만 여기서 문제는... dp배열을 채우는 과정이 이렇게 하면 k번째 광물의 가치를 cost k이라 했을때 n*(cost1 + cost2 + cost3 + ... + costn) 이 됩니다. 문제 제한 상 최고 크게 나올수 있는 가치의 합은 1000*100=100000 이거를 최대 n(1000번) 돌리니 1000*100*1000 = 100000000 = 10^8 이 나옵니다. 일반적으로 저정도가 1초안에 돈다고 보는 연산 횟수 안전선인데... 일단 믿음을 가지고 돌려보니 다행히도 맞았습니다! 심지어 나중에 확인해보니 생각보다 빨리 돌더라고요...?
#include <bits/stdc++.h>
using namespace std;
long long int sum;
long long int n;
long long int cost[1005];
bool dp[1005][100005];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i=0; i<n; i++){
cin >> cost[i];
sum += cost[i];
}
for(int i=0; i<=n; i++){
dp[i][0] = 0;
}
for(int i=1; i<=n; i++){
dp[i][cost[i-1]] = 1;
for(int j=1; j<=sum; j++){
if(dp[i-1][j]){
dp[i][j]=1;
dp[i][j + cost[i-1]]=1;
}
}
}
long long int ans = 0;
for(int i=1; i<=sum; i++){
if(dp[n][i]) ans++;
}
cout << ans;
}
아무튼 이렇게 01:24 시점에서 6문제중 5문제를 풀어 스코어보드는 프리즈 되었습니다.
67?분 남은 시점이였네요. 듣자하니 고급반에서는 30분만에 스코어보드를 프리즈 시킨 엘사가 존재한다던데.... (이분 후기도 꼭 읽도록 합시다!) https://blog.naver.com/PostView.naver?blogId=hibye1217&logNo=222733710725&parentCategoryNo=111&categoryNo=&viewDate=&isShowPopularPosts=false&from=
[Contest] 월간 ALOHA #1 (Advanced) 후기
결과 (참여 아이디 = HY-Bee) 경과 [A] 수열의 주인 수열이 16칸 단위로 반복된다고 하니 16칸을...
blog.naver.com
그리고 남은 시간동안 [C]번을 어떻게든 풀어서 확실하게 1등을 못박으려 했지만... 결국 풀지 못하고 끝났습니다. 그런데 프리즈가 되있는 동안 상당히 많은 분들이 제출을 해서 좀 무서웠습니다. 특히 결국 4솔브로 2등을 하신 garepaps님의 경우 제출을 5번 하셨는데 5번 모두 프리즈 중에 하셨습니다.
들리는 소문에 의하면 저분 늦게 참가한데다 폰코딩 하셨다는데... 제시간에 시작하셨다면 저는 승부도 못보고 졌을거 같습니다... ㄷㄷㄷㄷ...
[총평 및 마무리]
개인적으로 느끼는 난이도 순서는 쉬운거에서 어려운거 순으로
A -> B -> F -> D -> E -> -> -> -> -> -> -> -> -> -> -> -> -> -> -> -> -> -> -> C 입니다.
실제로 C는 결국 아무도 못 푼채로 끝났더군요.
전반적으로 문제들이 초급반 범위에 적당한 난이도이면서도 굉장히 재밌었습니다.
특별상이 텀블러라는데... 아니 제발 1등상 텀블러로 하면 안되나요... 너무 탐나는데...
garepaps 팀명으로 참가하신 분 누군지는 몰라도 언제한번 꼭 만나뵙고 싶습니다... 덕분에 끝까지 긴장하게 되었고 1분 남은 시점에서는 저를 그냥 기도 메타를 타게 만드셨습니다 ㅋㅋ...
여러분도 라이브러리 오브 루이나 하세요 정말 갓 겜 인데 심지어 국산 인디겜입니다. 오히려 최근 세계적으로 성공한 몇 안되는 인디겜의 좋은 예시라고 생각합니다 :+1:
'HYU ALOHA' 카테고리의 다른 글
| 2023 ALOHA 벚꽃컵 후기 [출제/검수] (4) | 2023.05.29 |
|---|---|
| 2022 ALOHA 월반멘토링 1주차 - C++기초, DP, 그리디, 분할정복 (후기/풀이) (0) | 2022.07.28 |
| 2022 6월 월간알로하 (MALOHA) 후기 (0) | 2022.07.03 |
| ALOHA 초급반 5주차 연습 후기 (0) | 2022.05.15 |
