뇌를 비우고 쓴 글이라 이상하게 적은 부분이 있을 수 있습니다. 댓글 등으로 지적해주시면 감사히 수정하겠습니다.
진짜 최종 구데기컵 2: Marathon Edition
나흘동안 치뤄진 온라인 대회다. 진지하게 PS 실력을 겨루는 대회라기보단 컨셉 / 이벤트성 대회에 가깝지만, 문제의 질은 많이 높았다고 느껴졌다. 구데기인데 구데기가 아니야...?
G. 연속합 2147483647
맨 처음으로 잡은 문제다. 배낭 문제처럼 해서 섭테 점수들로 최고 점수 받는 법을 확인해 봤는데, 6번 테케 빼고 전부 맞춰야 했다.
그냥 생각없이 7 8 11번 섭테를 거르는 풀이를 내서 적당한 점수를 받았고, 난 대회 끝까지 이 점수를 갱신하지 못했다...
F. 0초 후에 제출할 수 있습니다
맞을 때까지 아무 거나 제출하면 된다! 대회 초기에는 제출이 많아서 생각보다 AC를 받기 쉬웠다.
A. 홀수와 짝수의 대결
이 문제에 공지가 떠있길래 별 생각 없이 들어가서 문제를 읽는데, 아래에 공백이 좀 많길래 뭐지?? 하고 스크롤을 내려봤더니 추가 지문이 있길래 그럼 그렇지 ㅋㅋㅋ 하고 쭉 읽었다.
일단 "다들 진짜 홀수/짝수인 줄 알고 E만 출력하고 계시네요"라는 공지가 사실 낚시일 가능성을 고려해 그냥 테케마다 E만 출력했다. 그리고 틀렸다.
대충 섭테라도 긁으려고 에라토스테네스를 냈는데 틀리고, 뭐지?? 하고 다시 읽어 보니 홀수 개의 소수로 표현할 수 있으면 짝수라는 걸 짝수 개여야 짝수란 걸로 잘못 생각했었다; 일단 고치고 다시 냈다.
근데 또 틀리더라?? 문제에 낚시가 한 개 더 있구나 싶었고, 가 아니라 나 나 중 하나로 바꿔야 하지 않을까 의심이 들었다. 근데 귀찮아서 안 내봄 ㅎ
느긋하게 다른 문제들 하나둘 읽는 와중에 공지가 하나 더 올라왔다. 지문에서 '많으면'을 '적지 않으면'으로 정정한다는 내용이었다. 의심했던 게 맞았네! 하면서 고치고 내서 섭테 1을 맞았다. 스피드런 에디션이 끝나고 그리 지나지 않아 공지가 올라온 점에 근거해서, 공지를 활용해서 에디션마다 스코어보드를 바꿔보려고 한 건가? 하는 생각이 지나갔다.
사실 실제로 어땠건 간에 개인적으론 구데기컵에 참여하고 있다는 느낌을 받는 것 같아서 오히려 재밌었다. 맞왜틀을 3일정도 하다 공지가 나왔으면 좀 화났을 것 같지만 대회 시작한지 얼마 안 돼서 공지가 뜬지라 별 생각 안 들었음
여튼 섭테 3을 풀기 위해 규칙을 찾으려고 까지 돌려봤는데 예외가 밖에 없길래 그대로 제출하고 냈다. 만점을 못 받길래 뭐지?? 를 또다시 외치고 혹시 입력에 이나 음수가 있나 같은 삽질을 하다 까지 돌려본 뒤에야 반례가 더 있구나 싶었다..
검색해 보니 이름까지 붙어있는 좀 유명한 건가 본데 그냥 반례들 전부 DB 박고 냈다 ㅎ
E. 눈치 게임
그냥 연속합만 슬쩍 보고 탈주하려고 했는데 스코어보드 한 번 보고 나니 계속 풀게 되더라.. 여튼 이 문제 맞은 사람이 21명이라 순서상 분명 벡터 매칭을 내야 하는데 틀렸다!!
스피드런/레귤러/마라톤 에디션 중에서 빠진 사람 있나 확인도 해보고 중복 있나 확인도 해보고 다 해봤는데 차이가 없었음.. 그 후로 1000번부터 1021번까지 거의 다 내보기도 했는데 계속 틀리길래 뭐지?? 하다가 그냥 누가 풀어서 큐가 밀리길 기다렸다
나중에 큐 좀 밀리고 나서 다시 제출하니까 맞던데 뭐가 틀린 거였을까..
J. 하이퍼 수열과 하이퍼 쿼리
17114 하이퍼 토마토의 패러디 문제다. 당연하지만 푸는 방법은 많이 다르다.
부분점수가 긁히나 하고 아주 무식한 나이브를 내봤는데 당연히 틀리더라 ㅎ; 정신차리고 일단 구간합이라길래 매우 자연스럽게 펜윅이나 세그를 떠올렸다가, 업뎃이 없다는 걸 그제서야 보고 그냥 prefix sum이란 걸 깨달았다.
다차원 prefix sum의 원리가 포함배제이고, 이 경우는 매우 쉬운 편이라 그냥 하면 된다. 구현할 때 알아둘 점은, 다차원 배열 대신 1차원 배열을 사용하는 게 약 11배정도 더 짜기 편하다. 방법은 C/C++에서 다차원 배열의 인덱스를 어떻게 접근하는지 생각해 보면 간단히 답이 나올 것이다.
근데 제출했더니 섭테3이 안 나와서 다시 읽어보니 가 개인가 좀 작아서 자연스럽게(??) 도 그정도일 거라고 생각했는데 이었다 ㅋㅋ! 그래서 빌드를 좀 분할정복스럽게 하도록 고쳤는데, 예제도 안 나오길래 이렇게 하는 게 아닌가 싶어서 뇌절을 했다. 랑 를 헷갈려서 인덱스를 잘못 쓴 거였더라..
뭔가 구데기컵이 아니라 일반 대회에 나왔어도 이거 괜찮은 문제군! 하고 넘어갈 정도로 구데기성이 옅은 대신 좋은 연습문제였던 것 같다. 아니 구데기컵이니까 이렇게 말하면 까는 게 되나??
D. 4차 산업 혁명
크기의 칸에 숫자가 적혀 있다. 각 칸이 얼마나 진하게 칠해져 있는지 범위로 주어질 때, 이 숫자를 인식하는 문제... 어디서 많이 봤을 형태인데, 다름아닌 머신러닝의 헬로월드인 MNIST다.
물론 난 그 헬로월드조차 해본 적이 없었기 때문에 어떻게 해야 할지 고민을 꽤 했는데, 결국 적당한 코드를 복붙해봐서 로컬에서 돌리고 가중치를 코드에 박은 다음 제출했다..
파이썬과 numpy에 전혀 익숙하지 않아서 문법부터 다시 공부함 ㅠㅠ
C. Nonogram QR
해야 할 건 명확한데 익숙하지 못해서 삽질을 좀 했다..
우선 QR코드를 텍스트로 바꾸는 작업부터 해야 했는데, 맨 처음에는 quirc를 가져와서 열심히 짜고 나니까 주어진 QR코드의 ECC가 잘못되었다면서 인식을 못 하더라??? 뭔가 잘못 했나 싶어서 크기도 키워보고 수동으로도 넣어보고 깃헙 이슈도 다 읽어보고 했는데 결국 끝까지 안 되서 포기했다...
일단은 QR코드 인식 라이브러리를 바꿔보기로 했고, glassechidna/zxing-cpp를 써봤다. 근데 얘도 인식을 못 하더라???? 어이가 없었다.. 참고로 인터넷에서 아무 QR코드나 복붙해서 인식하게 해봤는데 두 라이브러리 전부 이것들은 잘 인식했다
그래서 이건 사실 유사 QR코드처럼 생긴 다른 무언가인가 싶어서 QR코드 비슷하게 생긴 것들이나 파생작들을 계속 찾아봤는데 소득이 하나도 없었다... 결국 마지막으로 다시 라이브러리를 바꿔보기로 함
이번에 고른 건 nu-book/zxing-cpp이었고, 사실 위에서 이미 같은 zxing을 써보기도 했는데 의미가 있나 싶었는데 인식이 되더라????? 대체 왠지 의문에 허탈하기도 하고 참 여러 감정이 들었는데 일단은 됐으니까 기뻐하면서 노노그램 솔버를 찾기로 했다.
사실 크기도 작고 무엇보다도 노노그램을 푼 결과가 QR코드라는 게 보장되어 있으니 고정된 점들이 많아 직접 짜도 빠르게 풀릴 것 같긴 한데, 좀 생각해보다 귀찮아서 던지고 열심히 솔버를 검색했다
그래서 찾은 게 naughty란 프로그램인데, 다른 코드에 포함될 생각 없이 단독 실행파일로만 짜려고 했는지 적용하려고 보니까 짜증나는 부분이 너무 많았다... 특히 전역변수 남발 ㄹㅇ 개화나더라
그래도 간신히 작업을 마무리하고 답을 구해서 제출하니 맞음 히히
사실 섭테 2번의 점수가 매우 작아서 그냥 섭테 1번만 손으로 풀어서 긁는 게 나았겠지만 그냥 프로그램으로 만들어서 해보고싶었음 ㅋㅋ
G, 연속합 2147483647
남은 문제들은 건드릴 엄두가 나지 않는 것들이 대부분이라, 다시 연속합으로 돌아와 이것저것 커팅을 다 시도해보고 될만한 것들도 계속 내봤지만 전부 섭테 11에서 시간초과가 났다 ㅜㅜ
일단 부분점수라도 더 받아보려고 했는데 데이터의 악랄함에 질려서 중도포기함 ㅋㅋ 사실 더 하면 만점 근접하게 받을 것 같았지만 현탐이 너무 왔었다.. 얘기할 건 많지만 쓰기 귀찮으니까 생략
파이썬으로 짜서 느린가 싶어서 C++로 빅인티저를 구현해서 내려고 했는데, 이게 의외로 재밌어서 삼천포로 빠지다가 결국 제출 못하고 대회 끝남 엌ㅋㅋ
끝말
재밌었다. 뭔가 더 쓸 말이 있던 것 같지만 쓰려고 보니까 아무튼 재밌었단 말밖에 생각이 안 나서 이것만 쓴다.
제목에는 구데기란 단어가 들어가있는데 반해 문제 퀄리티도 훌륭했고, 그렇다고 PS판에서 구데기 취급받는 형식이나 문제, 데이터란 컨셉을 버린 것도 아니라 며칠동안 즐겁게 참여했다. 이제 다시 PS할 시간~