저번에는 LibraryOfRuina로 참가했고 이번에는 LobotomyCorporation으로 참가했습니다. 다음번에는 LimbusCompany로 참가해 프문 게임 3부작 완성하겠습니다 ^^
1등을 하긴 했는데 저번보다 푼 문제수는 더 적었네요. 나중에 확인해보니 실제로 문제 난이도가 저번보다 한층 높아졌다고 합니다.
문제랑은 별개로 오프라인 대회는 처음이였는데 재밌었던거 같습니다. 솔직히 풍선은 대회 다 끝나고나서야 눈에 들어왔는데 그냥 현장 분위기(?)가 좋았던거 같습니다.
[A] - 얼려먹는 스코어보드 00:04 - AC
문제에 주어진대로 조건을 분기하면 끝나는 문제입니다. 제가 쓸대없이 조건을 많이 잡긴 했는데 저때는 좀 긴장한 상태라 그냥 읽으면서 이해한 그대로 풀었습니다.
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--){
int n, a, b;
cin >> n >> a >> b;
if(n-b>=a){
if(n-b!=1) cout << "The scoreboard was frozen with " << n-b << " minutes remaining.\n";
else cout << "The scoreboard was frozen with " << n-b << " minute remaining.\n";
}
else{
if(a!=1) cout << "The scoreboard was frozen with " << a << " minutes remaining.\n";
else cout << "The scoreboard was frozen with " << a << " minute remaining.\n";
}
}
}A번을 풀고나서는 B를 일단 읽어봤습니다. 문제 자체는 간단해보였는데... 뭔가 전혀 풀이는 안 떠오르더라고요? 그래서 B를 넘기고 C부터 보기로 했습니다.
[C] - Javascript는 정말 이상한 언어야 00:10 - AC
실제 문제 풀이랑은 별개로 저번에 HYU-Icewall (한양대 보안동아리) 과제로 webhacking.kr 문제를 보던중 Javascript를 이해해야 하는 문제가 많아서 친구한테 기초적인거만 가르쳐 달라 한적이 있었는데 그 때 저한테 이 문제에서 주어진 상황을 보여주더라구요.
JS 잘 만든 언어라 할때마다 나오는 단골 예시라면서.
그래서 지문 읽으면서 약간 웃었습니다.
이 문제는 약간의 STL관련 사전 지식이 필요한데 C++의 내장 sort()함수는 문자열의 배열에 대해 사전순 정렬을 해줍니다.
따라서 수 입력을 int형이 아닌 string형으로 받은후 sort()하고 출력해주면 되는 간단한 문제였습니다. 문제에서 0으로 시작하는 수는 주어지지 않는다고 나와있기 때문에 0010 같은 수에 대한 예외처리 마저 불필요합니다.
#include <bits/stdc++.h>
using namespace std;
int n;
string arr[200005];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i=0; i<n; i++){
cin >> arr[i];
}
sort(arr, arr+n);
for(int i=0; i<n; i++){
cout << arr[i] << ' ';
}
}C번을 풀고나서는 D, E, F를 한번씩 봤는데 그중에서 풀이가 바로 떠오른 E번을 풀기 시작했습니다...
그리고 여기서 전혀 예상치 못했던 일이 발생합니다.
[E] - 평균 조작하기 ??:?? - WA? WA? WA?
일단 풀이 자체는 간단합니다. 점수순으로 정렬을 해준후 앞에서부터 두개씩 묶어가며 평균을 구해주면 그게 답이 됩니다.
제가 이 풀이에 접근한 방법은 평균을 구하는 과정에서 더 큰 점수쪽에서는 손실이 발생하는데 평균이 최대려면 그 손실을 최소화 해야 합니다. 그리고 이를 달성 하기 위해서는 작은 수들부터 평균을 구해주면 됩니다.
그런데 틀렸습니다.
일단 틀렸다는 판정을 받고나서 풀이를 검토해봤는데 틀린 부분을 못 찾겠어서 구현을 살짝만 고쳐보고 다시 제출했습니다. 실수를 사용하는 문제니까 제가 어딘가서 실수했을거라는 마음으로.
그런데 또 틀리더라고요.
당장 풀이가 떠오르는 문제가 이 문제 밖에 없고 페널티는 점점 쌓여가니 절박해졌습니다. 그래서 분모도 long double로 캐스팅 하고 제출해봤는데 또 틀렸습니다.
솔직히 이 시점에서 이미 좀 심리적으로 많이 흔들렸습니다. 그런데 잠시후...
아 ㅋㅋ 스페셜저지 문제였더라구요. 운영진 분들이 스페셜저지 고치고 금방 재채점 해주시겠지 라는 믿음을 가지고 약간 당황스럽기도 하고 막막했지만 일단 다른 문제들로 넘어갔습니다.
참고로 위에 문제 제출 기록에는 여기서 3틀이 보이지 않을겁니다. 스코어보드에서도 마찬가지고요. 이유는 이후 설명 드리겠습니다.
그리고 이 사태에 대해 운영진 시점에서 후기를 읽고 싶다면 https://blog.naver.com/hibye1217/222788826404
[HYU - 운영진] 제 2차 월간 알로하 후기
다시 풀어보기: https://codeforces.com/group/E3SmB8bN1L/contest/387402 풀이가 궁금한 사람들을 위...
blog.naver.com
[F] - 가장 긴 한번 감소하는 증가하는 부분 수열 00:34 - WA
일단 B, D, F중에 F를 먼저 잡아봤습니다. 처음에 생각해본 풀이법은 그냥 LIS를 구하고 길이를 +1 해주는 거였습니다. 반례는 다양하지만 아직은 멘탈이 터져있는 상태인데다 2등이였어서 검토할 마음도 생각도 안 들고 어떻게든 한 문제라도 더 맞아보자는 마음이 더 급했습니다.
#include <bits/stdc++.h>
using namespace std;
int n, len, longest=1;
int num[1000000];
int L[1000000];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i=0; i<n; i++) cin >> num[i];
for(int i=0; i<n; i++){
auto pos = lower_bound(L, L+len, num[i]);
// position of element less than or equal to current num
//in the length array
*pos = num[i];
//assign element there
if(pos == L + len) len++;
//if that position is end of length array
//then that element is the largest element so far
//increase lis len by 1
}
if(len==n) cout << 0;
else cout << len+1;
}
[B] - 여름은 싫어 00:52, 00:54 - WA WA
F를 틀리고 나서는 인터넷 검색이 허용되었다는 점을 최대한 적극적으로 활용해보기 위해 문제들을 인터넷에 검색해보기 시작했습니다.
그리고 B를 다음과 같이 검색하면 풀이를 찾을수 있습니다.
"selecting k points on a number line so that the minimum distance is maximized"
그래서 코드를 가져온후 문제 조건에 입력을 살짝씩 조정한후 제출하니까... 틀렸습니다! 이번에도 제가 실수 했을거라 생각하고 int만 long long으로 고친후 다시 제출했는데... 또 틀렸습니다!
#include <bits/stdc++.h>
using namespace std;
bool check(int mid, int arr[], int n, int k)
{
int pos = arr[0];
int elements = 1;
for (int i = 1; i < n; i++) {
if (arr[i] - pos >= mid) {
pos = arr[i];
elements++;
if (elements == k)
return true;
}
}
return 0;
}
int solve(int arr[], int n, int k)
{
sort(arr, arr + n);
int res = -1;
int left = 1, right = arr[n - 1];
while (left < right) {
int mid = (left + right) / 2;
if (check(mid, arr, n, k)) {
res = max(res, mid);
left = mid + 1;
}
else
right = mid;
}
return res;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
int shades[500005];
for(int i=0; i<n; i++) cin >> shades[i];
cout << solve(shades, n, k);
return 0;
}
//credits to https://www.geeksforgeeks.org/place-k-elements-such-that-minimum-distance-is-maximized/#include <bits/stdc++.h>
#define int long long
using namespace std;
int shades[500005];
bool check(int mid, int arr[], int n, int k)
{
int pos = arr[0];
int elements = 1;
for (int i = 1; i < n; i++) {
if (arr[i] - pos >= mid) {
pos = arr[i];
elements++;
if (elements == k)
return true;
}
}
return 0;
}
int solve(int arr[], int n, int k)
{
sort(arr, arr + n);
int res = -1;
int left = 1, right = arr[n - 1];
while (left < right) {
int mid = (left + right) / 2;
if (check(mid, arr, n, k)) {
res = max(res, mid);
left = mid + 1;
}
else
right = mid;
}
return res;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
for(int i=0; i<n; i++) cin >> shades[i];
cout << solve(shades, n, k);
return 0;
}
//credits to https://www.geeksforgeeks.org/place-k-elements-such-that-minimum-distance-is-maximized/너무나도 빠르게 2WA를 적립했습니다. 뭔가 해탈해지더라고요. 그래도 어쨌든 코드에 문제가 있다는거니 이분탐색 코드를 살짝씩 손보기 시작했습니다. 위에 있는 credits to 는 no credits로 바꾸었고요. 틀린 코드를 제공한 자에게 credit따위 없습니다.
[B] - 여름은 싫어 01:05, 01:08 - WA WA
그런데 손본거도 틀렸더라고요.
그거도 두번이나.
#include <bits/stdc++.h>
#define int long long
using namespace std;
int shades[500005];
bool check(int mid, int n, int k)
{
int pos = shades[0];
int cnt = 1;
for (int i = 1; i < n; i++) {
if (shades[i] - pos >= mid) {
pos = shades[i];
cnt++;
if (cnt == k)
return true;
}
}
return false;
}
int solve(int n, int k)
{
int st, en, mid, ans;
st=0, en=shades[n-1];
ans=0;
while (st <= en) {
int mid = st+en>>1;
if (check(mid, n, k)) {
ans = max(ans, mid);
st = mid + 1;
}
else
en = mid-1;
}
return ans;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
for(int i=0; i<n; i++){
cin >> shades[i];
}
sort(shades, shades+n);
cout << solve(n, k);
return 0;
}
//no credits to https://www.geeksforgeeks.org/place-k-elements-such-that-minimum-distance-is-maximized/
//cant even make bin search properly.#include <bits/stdc++.h>
#define int long long
using namespace std;
int shades[500005];
bool check(int mid, int n, int k)
{
int pos = shades[0];
int cnt = 1;
for (int i = 1; i < n; i++) {
if (shades[i] - pos >= mid) {
pos = shades[i];
cnt++;
if (cnt == k)
return true;
}
}
return false;
}
int solve(int n, int k)
{
int st, en, mid, ans;
st=shades[0], en=shades[n-1];
ans=0;
while (st <= en) {
int mid = st+en>>1;
if (check(mid, n, k)) {
ans = max(ans, mid);
st = mid + 1;
}
else
en = mid-1;
}
return ans;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
for(int i=0; i<n; i++){
cin >> shades[i];
}
sort(shades, shades+n);
cout << solve(n, k);
return 0;
}
//no credits to https://www.geeksforgeeks.org/place-k-elements-such-that-minimum-distance-is-maximized/
//cant even make bin search properly.
[B] - 여름은 싫어 01:12 - AC
팀노트에 있던 jinhan814님의 이분 탐색 구현법에 대한 블로그글 https://www.acmicpc.net/blog/view/109 을 보고 구현을 고쳐서 결국에 맞았습니다.
인터넷에 있는 구현은 답이 음수에 있는 경우를 고려 안했는지 탐색 범위를 적절하지 않게 잡았더군요.
풀이는 다음과 같습니다.
우선 우리는 좌표를 입력 받은후 정렬을 해줄겁니다. 그 후 이분탐색을 해줄건데 이때 이분탐색을 진행하는 변수는 바로 좌표들 사이에 거리중 최대 거리입니다. 따라서 탐색 시작은 정렬후 첫번째 좌표, 끝은 마지막 좌표와 첫번째 좌표 사이의 거리로 잡아주면 됩니다.
범위를 줄이는 조건은 k명을 현재 탐색중인 거리보다 멀거나 일치하게 배치할수 있는지 입니다. 배치할수 있다면 더 큰 최대거리에 대해서 탐색을 진행하고 없다면 더 작은 거리에 대해서 탐색을 진행해주면 됩니다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
int shades[500005];
bool check(int mid, int n, int k)
{
int pos = shades[0];
int cnt = 1;
for (int i = 1; i < n; i++) {
if (shades[i] - pos >= mid) {
pos = shades[i];
cnt++;
if (cnt == k)
return true;
}
}
return false;
}
int solve(int n, int k)
{
int st, en, mid, ans;
st=shades[0], en=shades[n-1]-shades[0]+1;
ans=0;
while (st <= en) {
int mid = st+en>>1;
if (check(mid, n, k)) {
ans = max(ans, mid);
st = mid + 1;
}
else
en = mid-1;
}
return ans;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
for(int i=0; i<n; i++){
cin >> shades[i];
}
sort(shades, shades+n);
cout << solve(n, k);
return 0;
}
//no credits to https://www.geeksforgeeks.org/place-k-elements-such-that-minimum-distance-is-maximized/
//cant even make bin search properly.
//nor can I lmao저 사이트 필자 뿐만 아니라 저도 이진탐색 구현을 못하길래 nor can I라고 달았습니다. 그리고 이문제를 해결함과 동시에 1등으로 올랐습니다.
이 시점까지 아직 E에 대한 소식은 없었습니다.
[F] - 가장 긴 한번 감소하는 증가하는 부분 수열 01:29 - WA
E번 고쳐지길 기다리는 동안 F를 다시 잡아봤는데 이번에는 이미 정렬되어있는지를 확인하는 부분을 추가하고 시도해봤습니다. B번에서 페널티가 너무 많이 쌓였고 E번은 아직 무소식이라 급하게 무지성 제출을 했고 틀렸습니다.
그리고 잠시후 E번이 고쳐졌다는 소식이 뜨긴 했는데...
[E] - 평균 조작하기 01:43 - AC
재채점이 아니라 문제가 바뀌었더라고요. 기존의 제출기록은 싹 지워졌고요. 솔직하게 말하자면 좀 억울한 기분이 들었습니다. 1시간이 넘는 시간 전에 제출했는데 모든 참가자가 그냥 리셋이라는 점이. 달리기로 비유하자면 열심히 3바퀴째 달리고 있었는데 출발선으로 돌아와서 다시 시작하라는 기분이였습니다.
문제가 바뀌었다고 해도 풀이가 달라질 정도로 바뀌지는 않아서 내가 풀이를 언제 떠올렸는지랑은 별개로 모두가 풀이 생각할 시간 60분을 벌었다는 점도 있고요. "좀 자만하는거 아니냐. 너 풀이가 애초에 틀렸을수도 있지 않았냐." 라고 하실수도 있지만 대회중 심정을 솔직하게 말하자면 그랬다는 겁니다.
결과적으로는 큰 타격이 없었고 운영진 입장에서는 어쩔수 없는 상황에서 최선의 선택을 했다는거도 이해합니다.
대회 후 집에 돌아와서 익명의 운영진 분과의 대화에서:
들어보니 오히려 운영진 측도 많이 힘들었다고 하더라구요. 대회 중에는 좀 이기적으로 제 입장만 생각했습니다. 죄송합니다. 대회 주최는 대회 참가보다 최소 2^32-1 배는 더 힘들다는걸 다시 한번 느끼게 되는거 같습니다.
풀이 자체는 아까 말했다 싶이 기존 풀이에서 바뀐 점이 사실상 없었고. 대신에 실수를 사용한 부분을 정수로 전부 바꿔주면 끝입니다.
#include <bits/stdc++.h>
using namespace std;
int n;
long int arr[200005];
long int avg=0;;
long int divisor = 2;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i=0; i<n; i++){
cin >> arr[i];
}
sort(arr, arr+n);
for(int i=1; i<n; i++){
arr[i] = (arr[i]+arr[i-1])/divisor;
}
cout << arr[n-1];
}그리고 이후 아무 제출도 하지 않은채 대회가 마무리 되었습니다.
[되돌아보며]
문제들이 재밌었습니다. 지문이랑 풀이 모두. 열심히 밤낯없이 대회 준비해주신 운영진 분들 감사합니다!
2연속 1등 하는데 성공했습니다! ㅠㅠ 심리적으로 흔들린 부분도 있었고 초반에는 페이스가 말리기도 했지만 그래도 결과가 좋게 나오니까 기분 좋네요.
앞으로 대회에 무슨일이 있어도 흔들리지 않고 침착하게 해결해나가는 연습이 필요할거 같다고 느꼈습니다.
상장이 받으니까 기분도 좋은데 문구가 되게 재밌네요 ㅋㅋㅋㅋ 누구 아이디어인지는 몰라도 참신한거 같습니다.
참가하신 분들 운영진 분들 모두 수고하셨습니다! 감사합니다.
'HYU ALOHA' 카테고리의 다른 글
| 2023 ALOHA 벚꽃컵 후기 [출제/검수] (4) | 2023.05.29 |
|---|---|
| 2022 ALOHA 월반멘토링 1주차 - C++기초, DP, 그리디, 분할정복 (후기/풀이) (0) | 2022.07.28 |
| 2022년 05월 월간 알로하 후기 (0) | 2022.05.19 |
| ALOHA 초급반 5주차 연습 후기 (0) | 2022.05.15 |
