교내 동아리 ALOHA의 본 내전 ALOHA 벚꽃컵의 출제/검수를 하였습니다.
처음으로 해보는 출제/검수 경험이라 많이 미숙한 점도 있었고 특히 문제 데이터 오류가 발생한건 검수진으로서 반성해야 할점이라 생각합니다. 앞으로 더 다양한 문제를 정확하게 검수하기 위해 더 많은 문제들을 접해봐야 겠다고 생각했고 결론적으로는 PS/CP를 이어하는데 좋은 동기부여가 되는 경험이였다고 생각합니다.
이번 내전은 시험적으로 동아리 회원분이 자체 제작한 PPS (https://project-ps.com/) 라는 사이트에서 개최했습니다. 개발 초기 사이트인 만큼 버그도 좀 있었고 불편한 사항들도 없진 않았지만 대회 자체는 문제없이 진행되었습니다. 이 자리를 빌려 사이트를 개발해주신 구건모 선배님께 감사하다는 말을 드립니다.
운영진으로서 제일 불편했던건 풍선 가져다 줬는지 마크하는 기능이 없었던거 (이거 ㄹㅇ 초반에 체크하느랴 고생했네요) 참가자 입장에서 제일 불편했을만한건 제출할때 마다 기본 언어가 C99로 바뀐다는 점이였을거라 생각합니다. C로 컴파일 에러를 제일 많이 낸 참가자에게 뽀로로 비타민 C를 특별상으로 주기로 할 정도로 많은 참가자들이 C로 잘못 제출하는 일이 있었습니다...
저는 이번에 총 3문제를 출제했고 그중 대회에서 풀린 문제는 1문제 밖에 없었습니다... (분명 3문제 다 킬러 문제가 아니였음에도 ㅠㅠ 좀 슬프네요) 다음은 그 3 문제의 링크/설명 그리고 해설입니다.
이번 내전은 Div 1 (고급반), Div 2 (중급반), Div 3 (초급반), 이렇게 3개의 디비젼으로 나누어서 진행되었습니다. 이하에서 3E 는 Div3의 E번 문제였음을 의미합니다.
3C - 별 찍기 와 쿼리 (https://project-ps.com/problem/36)
Boj의 별 찍기 - 5 를 변형한 문제입니다. 1학년 2학기 창의적소프트웨어프로그래밍 과목에서 나왔던 과제의 아이디어를 더했습니다.
초기 설정은 비어있는 2차원 배열을 생성해 격자를 표현하면 됩니다.
그 후 각 점의 가장 높은 꼭짓점을 저장할 pair<int, int>형의 2차원 배열도 만들면 됩니다.
1번 쿼리는 그냥 별 찍기 - 5를 꼭짓점에서 시작하여 실행해주면 됩니다. 이 과정에서 2번 쿼리를 위한 준비까지 가능한데바로 그 꼭짓점의 정보를 별을 찍는 칸들에 저장해주는 겁니다. 2번 쿼리에서 가장 최근 그려진 삼각형만 보기 때문에 이미 어떠한 값이 채워져 있어도 덮어 씌워주면 됩니다.
다만 한가지 주의할 점은 삼각형이 격자를 벗어나는지 벗어나지 않는지를 판별하는것인데 이는 삼각형의 대칭성을 활용해 왼쪽 끝 꼭짓점과 오른쪽 끝 꼭짓점이 격자를 벗어나는지 벗어나지 않는지만 계산해주면 됩니다.
2번 쿼리는 1번 쿼리의 과정에서 저장한 꼭짓점의 정보를 출력하면 됩니다. 만약 비어있다면 -1을 출력하구요 (비어있는지 판별은 애초에 vector<pair<int,int>> 로 정보를 저장하거나 절대 답이 될수 없는 초기값을 미리 설정해두는 방식으로 처리 가능합니다)
여담으로 원래는 여러개의 삼각형이 겹쳐져 있을 경우 두번째로 가장 최근에 그린 꼭짓점을 출력해야 했으나 검수 과정에서 너무 뇌절이고 어렵다는 평을 들어 수정하게 되었습니다.
3번 쿼리는 그냥 격자를 출력하면 됩니다.
문제 자체는 어렵지 않지만 초급반 셋에서는 찾아보기 드문 쿼리라는 개념과 많은 구현량으로 인해 대회중 0제출 0정답 0틀렸습니다를 기록하게 되었습니다.
출제자 코드 (MCS):
#include <bits/stdc++.h>
using namespace std;
//#define endl '\n'
#define PRECISION 0
#define fr first
#define sc second
using ll = long long;
using ld = long double;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const ll MOD = 1e9+7;
int n, m, q;
char board[105][105];
vector<pii> info[105][105];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
cin >> n >> m >> q;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
board[i][j] = '.';
}
}
while(q--){
int query;
cin >> query;
if(query == 1){
int row, col, height;
cin >> row >> col >> height;
if(row+height-1>n || col+(height-1)>m || col-(height-1)<=0){
continue;
}
for(int i=row; i<row+height; i++){
for(int j=col-(i-row); j<=col+(i-row);j++){
board[i][j] = '*';
info[i][j].push_back({row, col});
}
}
}
if(query == 2){
int row, col;
cin >> row >> col;
if(info[row][col].empty()){
cout << -1 << endl;
}
else{
cout << info[row][col][info[row][col].size()-1].fr << ' ' << info[row][col][info[row][col].size()-1].sc;
cout << endl;
}
}
if(query == 3){
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
cout << board[i][j];
}
cout << endl;
}
//cout << endl;
}
}
}
3F - Sorting for 97 Keys (https://project-ps.com/problem/34)
두가지 풀이가 존재합니다.
1. 커스텀 compare function을 만들어서 std::sort함수의 인자로 넘겨주기 O(n log n)
2. 값의 범위가 작다는 점과 도, 레, 미, 파, 솔, 라, 시 의 순서로 정렬된다는 점을 활용해 counting sort등의 O(n)정렬 활용하기
두 코드 모두 당연히 충분히 빠르게 동작합니다. 출제 의도 자체는 커스텀 compare function을 잘 짤수 있는가? 였습니다.
제가 출제한 문제중 유일하게 대회중 정답 코드가 나온 문제였습니다...
출제자 코드 (MCS):
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define PRECISION 0
#define fr first
#define sc second
using ll = long long;
using ld = long double;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef tuple<ll, ll, ll> tl3;
const ll MOD = 1e9+7;
int n;
ll arr[200005];
char notetype[7] = {'C', 'D', 'E', 'F', 'G', 'A', 'B'};
bool cmp(ll i, ll j){
if(j%7 > i%7){
return true;
}
else if(j%7==i%7 && j/7 < i/7){
return true;
}
return false;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
cin >> n;
for(int i=0; i<n; i++){
ll tmp;
cin >> arr[i];
}
sort(arr, arr+n, cmp);
for(int i=0; i<n; i++){
cout << notetype[arr[i]%7] << arr[i]/7 << endl;
}
}
2G - 이차원의 함정 속으로 (https://project-ps.com/problem/37)
우선 문제를 보자마자 가중치가 있는 그래프에서의 최단 경로라는 점에서 다익스트라를 쉽게 떠올렸을 겁니다. 그리고 전체 최단 경로를 a 에서 k로 가는 최단 경로, k에서 k로 가는 최단 사이클, k에서 b로 가는 최단 경로 이렇게 세 부분으로 나눌수 있다는 점 또한 직관적입니다.
하지만 실제로 구현을 함에 있어서 한가지 난관에 부딪힐텐데 바로 k에서 k로 가는 최단 사이클 을 구하는 과정입니다. 단순히 k에서 시작하는 다익스트라를 돌리는것 만으로는 k에서 k로 가는 최단 경로를 구할수는 없습니다. (시작 정점의 최단 경로를 처음에 0으로 설정하기 때문)
따라서 약간의 아이디어를 떠올려야 하는데 우선 결론부터 말하자면
"k에서 k로 가는 최단 사이클은 k에서 k에 인접한 각 정점 u에 대해 k에서 u로 가는 간선의 가중치와 u에서 k로 가는 최단 경로의 합중 최소이다. 여기서 k에 u가 인접하다는 것은 k에서 u로 가는 간선이 있음을 의미한다."
k에 인접한 정점을 확인하는건 쉽습니다. 각 정점으로 이어지는 간선의 길이도 우리는 이미 저장하고 있고요. 하지만 모든 u에서 각각 다익스트라를 실행한다면 시간초과 판정을 받게 될 것입니다. 따라서 우리는 간선을 전부 뒤집은 역방향 그래프를 만들고 그 역방향 그래프에서 k에서 시작하는 다익스트라를 실행해야 합니다. 다익스트라가 시작 정점에서 출발해 모든 정점들에 대해 최단 경로를 구해주는 알고리즘임을 활용하면 우리는 이 역방향 다익스트라 한번으로 모든 k에 인접한 정점들 u에 대해 u에서 k로 가는 최단 경로를 구했음을 알 수 있습니다. (역방향에서 k->u로 가는 최단경로는 정방향에서 u->k로 가는 최단경로)
이제 각 u에 대해 금방 구한 최단경로에 간선의 가중치를 더하면 그중 최소가 되는 값이 k에서 k로 가는 최단 사이클이 됩니다.
이 풀이 외에 k를 몇번 지났는지를 parameter로 가지는 multi parameter 다익스트라를 실행해서 한번의 실행으로 답을 구하는것도 가능합니다. 시간 복잡도는 동일합니다.
데이터를 만드는게 굉장히 힘들었는데 정해 기준으로 다익스트라를 세번 실행하기 때문에 세번중 한번이라도 잘못 구현하였을 경우 틀리게끔 데이터를 제작해야 하였고 이 과정에서 k에서 k로 가는 최단 사이클을 구하는 과정에서의 다익스트라를 잘못 구현한 코드 를 저격하는것이 가장 어려웠습니다. 이 외의 케이스는 다행히도 다른 학술부원이 작년에 출제하였던 다익스트라 문제의 데이터로 저격이 가능했습니다. SPFA풀이는 테스트해보지 않았지만 일부러 막지는 않았습니다. 대상이 중급반이였던 만큼 SPFA를 알고 또한 이를 구현할 능력이 된다면 굳이 틀리게 만들고 싶지 않았습니다.
여담으로 hibye는 오타쿠가 맞습니다.
또한 여담으로 "이차원의 함정 속으로" 라는 제목은 같은 이름의 유희왕 카드에서 가져왔으며 실물 카드를 이 문제를 가장 많이 틀린 사람에게 "도모 콘니치와 오타쿠=상" 이라는 이름의 특별상으로 줬습니다. (특별히 액자에 스탠드까지 해줬습니다. 액자랑 스탠드 값이 5000원에 배송비가 3000원이였는데 정작 카드는 500원입니다.)
출제자 코드 (MCS):
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define PRECISION 0
#define fr first
#define sc second
using ll = long long;
using ld = long double;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef tuple<ll, ll, ll> tl3;
const ll MOD = 1e9+7;
const ll INF = 1e18;
ll v, e, a, b, k;
ll ans = 0;
ll loopcost = INF;
vector<pll> edges[200005];
vector<pll> redges[200005];
vector<ll> costak(200005, INF);
vector<ll> costkk(200005, INF);
vector<ll> costkb(200005, INF);
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
priority_queue<pll, vector<pll> ,greater<pll> >pq;
cin >> v >> e >> a >> b >> k;
while(e--){
ll v1, v2, w;
cin >> v1 >> v2 >> w;
edges[v1].push_back({v2,w});
redges[v2].push_back({v1,w});
}
//from a to k
costak[a] = 0;
pq.push({costak[a], a});
while(!pq.empty()){
ll cur = pq.top().sc;
ll dist = pq.top().fr;
pq.pop();
if(costak[cur] < dist) continue;
for(auto &i:edges[cur]){
ll nxt = i.fr;
ll nxtdist = dist + i.sc;
if(nxtdist < costak[nxt]){
costak[nxt] = nxtdist;
pq.push({nxtdist,nxt});
}
}
}
ans += costak[k];
//from k to k (important step! pls check)
costkk[k] = 0;
pq.push({costkk[k], k});
while(!pq.empty()){
ll cur = pq.top().sc;
ll dist = pq.top().fr;
pq.pop();
if(costkk[cur] < dist) continue;
for(auto &i:redges[cur]){
ll nxt = i.fr;
ll nxtdist = dist + i.sc;
if(nxtdist < costkk[nxt]){
costkk[nxt] = nxtdist;
pq.push({nxtdist,nxt});
}
}
}
//
//cout << ans << endl;
//
for(auto node:edges[k]){
//cout << "node " << node.fr << ' ' << costkk[node.fr] << endl;
loopcost = min(loopcost, costkk[node.fr]+node.sc);
}
ans+=loopcost;
//
//cout << ans << ' ' << loopcost << endl;
//
//from k to b
costkb[k] = 0;
pq.push({costkb[k], k});
while(!pq.empty()){
ll cur = pq.top().sc;
ll dist = pq.top().fr;
pq.pop();
if(costkb[cur] < dist) continue;
for(auto &i:edges[cur]){
ll nxt = i.fr;
ll nxtdist = dist + i.sc;
if(nxtdist < costkb[nxt]){
costkb[nxt] = nxtdist;
pq.push({nxtdist,nxt});
}
}
}
ans += costkb[b];
//
//cout << ans << endl;
//
//check ans
if(ans >= INF){
cout << "HIBYE IS OTAKU";
}
else cout << ans;
}
un-특별상
동아리 차원에서 후원금과 동비로 준비한 특별상과는 별개로 제가 사비로 특별상을 두개 준비했습니다. 순수 재미를 위한 상이고 실제 특별상과 구분하기 위해 un-특별상이라는 이름을 붙였으며 위의 유희왕 카드가 그 중 하나입니다.
나머지 하나는 한양대 최고 미남이자 과탑 똑붙 갓갓 개발자 디자이너 2023 ALOHA 동아리 회장인 최철민 선배의 얼굴이 그려진 하트모양의 손부채였습니다. 수상 조건은 회장님과 제일 먼저 대화를 나누는 것. 실물이 궁금하신 분은 한양대에서 저를 찾거나 수상자에게 연락을 취해보도록 합시다. ㅎㅎ...
농담인척 사비로 제작하면 만들게 해줄거냐고 회장님에게 물어보니 사비면 괜찮다 하셔서 풀 악셀을 밟게 되었습니다.
마치며:
빠듯하게 출제와 검수를 하다 보니 출제 할당량을 채우지 못했고 개인 실력 부족으로 인해 검수하지 못했던 문제도 상당했어서 다른 학술부원에 의존하기 보다는 개인 실력을 늘려야겠다는 다짐을 하게 되었습니다. 그래도 준비 과정과 대회 당일 모두 즐거웠으며 큰 후회 없이 마무리 되었다고 생각합니다.
다시 한번 참가해주신 ALOHA 회원 모두와 같이 고생해준 운영진, 그리고 PPS플랫폼을 개발해주신 구건모 선배님께 감사인사를 드리며 후기를 마치겠습니다.
'HYU ALOHA' 카테고리의 다른 글
| 2022 ALOHA 월반멘토링 1주차 - C++기초, DP, 그리디, 분할정복 (후기/풀이) (0) | 2022.07.28 |
|---|---|
| 2022 6월 월간알로하 (MALOHA) 후기 (0) | 2022.07.03 |
| 2022년 05월 월간 알로하 후기 (0) | 2022.05.19 |
| ALOHA 초급반 5주차 연습 후기 (0) | 2022.05.15 |
