지난 글에 이어지는 내용으로, 코드포스나 백준에 문제를 출제하기 위해 반드시 알아야 하는 Codeforces Polygon이라는 툴에 대해 소개하고자 합니다.
백준에 문제를 출제하려면 BOJ Stack에 지문, 예제, 데이터, 데이터 검증 코드, 스페셜 저지, 솔루션 코드 등을 업로드해야 하는데, 폴리곤에서 이런 것들을 편리하게 관리할 수 있습니다.
이번 교내대회에 출제했던 가장 쉬운 문제인 볶음밥 지키기를 예시로 들면서 설명해보겠습니다.
1. 회원가입, 문제 생성
먼저 오른쪽 위의 [Register] 버튼을 클릭하여 회원가입을 해줍니다. Codeforces 아이디가 있더라도 폴리곤과 공유되지 않기 때문에 새로 만들어야 합니다.
이후 상단의 [New Problem]을 눌러 문제들을 생성하고,
[View Contests > Create Contest]를 눌러 개최할 대회를 생성합니다.
오른쪽 [Action > Enter]을 클릭해 생성한 대회에 입장하면,
오른쪽 상단의 [Add problems?]에서 생성한 문제들을 추가할 수 있고,
오른쪽 하단의 [Manage developers list > Change list]에 협업할 출제진과 검수진을 등록하면 해당 대회에 등록된 문제들의 편집 권한을 부여할 수 있습니다.
이제 기본 세팅은 끝났습니다!
(협업하실 때는 오른쪽 하단의 [Update Working Copy]와 [Commit Changes]를 잊지 말고 해주세요.)
2. 지문 작성 (+ 그림 추가)
상단 메뉴의 [Statement]를 클릭하면 나오는 아래 페이지에 지문을 작성하면 됩니다.
- Name: 문제 제목을 적는 곳입니다.
- Legend: 지문을 적는 곳입니다.
- Input format: 입력 형식을 적는 곳입니다.
- Output format: 출력 형식을 적는 곳입니다.
문제에 그림을 넣고 싶다면, 하단에서 [Add Files > 파일 선택] 버튼으로 이미지 (ex) image1.png)를 추가합니다.
\begin{center}
\includegraphics[scale=1.5]{image1.png}
\end{center}이후 지문에 코드를 삽입하여 추가하시면 됩니다. (scale로 크기 조정 가능)
지문을 모두 완성했다면, 오른쪽 상단의 [In HTML]을 눌러 확인하시면
완성된 지문을 볼 수 있습니다. 시간/메모리 제한은 상단 메뉴의 [General info]에서 수정할 수 있고,
예제는 아직 보이지 않는 게 정상입니다. (나중에 [Test]에서 추가할 겁니다.)
3. Generator 만들기
Generator는 수작업으로 만들기 어려운 매우 큰 데이터를 자동으로 만드는 데 필요한 코드입니다.
generator.cpp를 만들기 위해 "testlib.h" 라이브러리가 필요한데, 개인 로컬 환경에서 사용하시려면 여기에서 다운받으실 수 있습니다. (Clion을 쓰는 저의 경우 C:\MinGW\include 경로에 넣어주었고, 개인차가 있을 수 있습니다.)
#include "testlib.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int main(int argc, char* argv[]) {
registerGen(argc, argv, 1);
int n=opt<int>(1);
int rmx=opt<int>(2);
int r=rnd.next(1,rmx);
int mx=opt<int>(3);
set<pii> se;
while(se.size()<n){
int x=rnd.next(-mx,mx),y=rnd.next(-mx,mx);
se.insert({x,y});
}
printf("%d %d\n",n,r);
for(auto [x,y]:se)printf("%d %d\n",x,y);
}코드 설명은 잠시 미루고, 완성된 generator.cpp를 상단 메뉴의 [Files > Source Files의 Add Files > 파일 선택]으로 추가해줍시다. 그리고 이제 메뉴의 [Tests]에 들어가서 이 코드로 데이터를 만들 겁니다.
먼저, 오른쪽 상단의 [Add Test]를 눌러 수동으로 데이터를 추가할 수 있습니다.
그리고 [Script 작성 > Save Script]를 눌러 generator를 이용해 랜덤으로 데이터를 만들어 추가할 수 있는데, 의미는 다음과 같습니다.
- generator 5 5 5 asd > 2 : 제너레이터 코드의 이름입니다. generator_2.cpp를 사용하려면 'generator_2 5 5 5 asd > 2'와 같이 사용하면 됩니다.
- generator 5 5 5 asd > 2 : generator.cpp 코드에서 순서대로 opt<int>(1), opt<int>(2), opt<int>(3), ... 에 해당합니다.
- generator 5 5 5 asd > 2 : 데이터의 이름이라고 생각하면 됩니다. (generator 5 5 5라는 데이터를 서로 구분하기 위해 존재)
- generator 5 5 5 asd > 2 : 몇 번째 데이터인지를 의미합니다. 수동으로 만들어둔 첫 번째 데이터가 존재하기 때문에, 2번부터 시작합니다. '$'를 넣는 경우, 중복된 번호를 피해서 자동으로 부여됩니다.
종합해서 'generator 100 20 50 big > 5'를 제너레이터에 맞게 해석해보면,
- generator.cpp를 사용해서,
- 밥알 100개,
- 웍의 반지름은 [1~20]에서 랜덤으로 정해지고, (r=rnd.next(1,20))
- 밥알의 좌표는 [-50~50]으로 랜덤인,
- big이라는 이름의 5번째 데이터가 완성되는 것입니다.
이제 문제에 보일 예제를 정해서, Test 표의 [Actions > Example > Use in statements : Yes > Update example]을 누르면 해당 예제가 지문과 함께 보이게 됩니다.
4. Validator 만들기
Validator는 내가 만든 데이터가 문제의 제한에 맞게 잘 만들어졌는지 검증하는 코드입니다.
Generator와 마찬가지로 [Files > Source Files의 Add Files > 파일 선택]으로 업로드하면 됩니다.
#include <bits/stdc++.h>
#include "testlib.h"
using namespace std;
int main(int argc, char* argv[]) {
registerValidation(argc, argv);
int n = inf.readInt(1, 100, "N");
inf.readSpace();
inf.readInt(1, 100, "R");
inf.readEoln();
set<pair<int,int>> se;
for (int i = 0; i < n; i++) {
int x = inf.readInt(-100, 100, "x_i");
inf.readSpace();
int y = inf.readInt(-100, 100, "y_i");
inf.readEoln();
ensuref(!se.count({x,y}), "coordinates duplicated");
se.insert(pair<int, int>(x, y));
}
inf.readEof();
}간단히 코드에 대해 설명하자면,
- int n = inf.readInt(1, 100, "N") : 밥알 개수(정수여서 readInt입니다.) n을 읽음과 동시에, 크기가 [1~100]인지 검사합니다. 지금 입력받은 변수가 문제에서 "N"을 의미하는 변수라는 의미입니다.
- inf.readSpace() / inf.readEoln() / inf.readEof() : 각각 공백 / 줄 바꿈 / 파일의 끝을 입력받습니다.
- ensuref(조건, 출력문) : 반드시 만족해야 하는 조건과, 만족하지 못하면 그 조건이 무엇인지 확인할 수 있도록 이유를 적어주면 됩니다.
ensuref(!se.count({x,y}), "coordinates duplicated")에서 조건은 'set에 {x,y}가 존재하지 않는다.'를 뜻하고, 만족하지 못했을 때 출력문이 해당 데이터에 좌표가 중복되었다는 사실을 알려줍니다.
이제 상단 메뉴의 [Validator > Select: > validator.cpp 선택 > Set validator] 을 눌러 업로드하면 됩니다.(validator.cpp는 [Or upload]에서 추가할 수도 있습니다.) 아래에서 [Add test]로 만든 validator를 테스트해볼 수 있습니다.
5. Checker 만들기
Checker는 출제자와 참가자의 답이 일치하는지 비교하는 코드입니다.
스페셜 저지 문제의 경우에만 직접 작성하면 됩니다.
상단 메뉴의 [Checker > Select > Set checker]를 누르면, fcmp.cpp, hcmp.cpp 등 다양한 체커가 기본으로 제공됩니다. 설명을 참고하셔서 문제의 출력 형식에 맞는 코드를 쓰시면 됩니다.
이 문제처럼 스페셜 저지의 경우, checker.cpp를 작성해서 generator, validator와 같은 방법으로 업로드해서 사용하면 됩니다.
#include "testlib.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
int n, r;
vector<pii> a;
int readAnswer(InStream &in) {
int x = in.readInt(-1000000000, 1000000000);
int y = in.readInt(-1000000000, 1000000000);
int ret=0;
ll rr=(ll)r*r;
for(auto [rx,ry]:a)
if((ll)(rx-x)*(ll)(rx-x)+(ll)(ry-y)*(ll)(ry-y)<=rr)ret++;
return ret;
}
int main(int argc, char* argv[]) {
registerTestlibCmd(argc, argv);
n = inf.readInt(1,100,"N");
inf.readSpace();
r = inf.readInt(1,100,"R");
inf.readEoln();
a = vector<pii>(n);
set<pii> se;
for (int i = 0; i < n; i++){
a[i].first=inf.readInt(-100,100,"x_i");
inf.readSpace();
a[i].second=inf.readInt(-100,100,"y_i");
inf.readEoln();
}
int jans = readAnswer(ans);
int pans = readAnswer(ouf);
if(jans!=pans){
if(jans>pans) quitf(_wa, "jury answer : %d, participant answer: %d", jans, pans);
else quitf(_fail, "jury answer : %d, participant answer: %d", jans, pans);
}
quitf(_ok, "%d", pans);
}main 함수 윗부분 코드는 validator.cpp와 똑같고, registerValidation(argc, argv) -> registerTestlibCmd(argc, argv)로만 수정해줍시다.
이제 jans(jury's answer, 출제자 정답)와 pans(participant's answer, 참가자 정답)를 입력받고, 각각 해당 좌표에서 몇 개의 밥알을 지켜내는지 리턴하는 readAnswer() 함수를 작성합니다. 어떤 좌표에 웍을 두었든, 결과적으로 같은 개수의 밥알을 지켜냈다면 정답으로 처리해줍니다.(_ok)
6. Solution 작성 / 채점하기
이제 정답 코드를 만들어서 polygon에 등록하고, 만들었던 데이터로 채점해볼 차례입니다.
상단 메뉴의 [Solution files > Add Files > 파일 선택 > Add Files]를 눌러 코드를 등록합니다. 그리고 표의 [Type > Change?]에서 해당 코드가 예상하는 결과를 정해줍니다.(Correct, TLE, WA 등등)
여기서 문제의 약점이 될만한 오답 코드를 많이 넣어줘야 현재 데이터가 얼마나 약한지 알 수 있습니다. 예를 들면 이런 것들을 저격하는 코드를 넣어주면 좋습니다.
- Naive한 풀이나, 출제자의 의도보다 더 쉬운 풀이가 혹시 통과하는지
- 풀이과정에서 나눗셈을 사용하는 경우, floating point error를 잘 막았는지
- 답이 큰 수가 아니더라도 계산 과정에서 값이 커질 경우, Overflow를 고려했는지
- 의도적으로 말도 안 되는 답을 출력하는 코드를 넣었을 때, 내가 만든 Checker가 정상적으로 동작하는지
이제 상단 메뉴의 [Invocations > Want to run solutions? > 채점을 원하는 코드와 데이터 선택 > Run judgement]를 누르면 채점을 시작합니다. [Actions > View]를 눌러 채점 결과를 확인할 수 있습니다.
7. 반례 찾기
만약 데이터가 부족해서 채점 결과가 예상과 다르게 나오는 경우, Generator를 이용해서 랜덤 데이터를 찾아볼 수 있습니다.
상단 메뉴의 [Stresses > Add Stress]를 누르면 아래와 같은 창이 나오는데,
여기서 Script pattern에 [Test > Script]에서 했던 것처럼 데이터를 입력해줍니다.
Total time limit은 반례 데이터를 찾는 시간을 의미합니다.(120초로 설정해도 반례를 찾는 순간 종료됩니다.)
Solutions에서 반례가 필요한 코드를 선택해주고, [Save and Run]을 눌러 반례를 찾아줍시다.
반례를 정상적으로 찾았다면 다음과 같이 파란색 결과 창이 표시되며, [Actions > Add to tests]를 통해 찾은 반례를 [Tests]에 자동으로 추가할 수 있습니다. [Actions > View]를 눌러 해당 데이터가 어떤 데이터인지 확인할 수도 있습니다.
8. 코드/데이터 추출하기
Commit을 마치고 상단 메뉴의 [Packages > Create package: Full]을 누르면, State가 'RUNNING'상태가 되며 파일 추출을 시작합니다.
만약 Checker, Validator, Tests, Solutions의 예상결과 등에 문제가 없다면, 위 화면과 같이 State가 'READY'상태가 되고, 문제가 있다면 'FAILED'상태가 되면서 Comment에 문제점을 남겨줍니다.
추출에 성공했다면 [Download > Linux]를 눌러 파일을 다운받고 압축을 풀어줍니다.
9. BOJ Stack에 등록하기
이제 추출한 파일들을 Stack에 순서대로 등록해보겠습니다.
-
: Polygon의 [Manage developers list]와 같은 기능입니다. 출제자, 검수자의 BOJ handle을 추가해줍시다. -
: Polygon의 초반 세팅에서 [Add problems?]와 같은 기능입니다. -
: Polygon의 [Statement]와 같은 기능입니다. 해당 문제의 경우, 스크롤 중간쯤에 있는 [스페셜 저지]를 [C/C++]로 수정해줍시다. - [예제] : 지문과 함께 보일 예제를 넣는 곳입니다. 해당 문제처럼 그림을 추가하고 싶다면 [예제 설명 >
]에서 추가할 수 있고, 만약 GIF를 추가하려면 [이미지 우클릭 > 이미지 속성 > URL 맨 끝의 -/preview/ 삭제 > 확인]하시면 됩니다. - [데이터] : Polygon의 [Add Test]와 같은 기능입니다. [데이터 추가하기 > drag & drop > Add]를 눌러 업로드하면 되며, 확장자명이 없는 파일은 .in으로, 확장자명이 .a인 파일은 .out으로 자동 변환됩니다.
- [데이터 검증] : Polygon의 [Set validator]와 같은 기능입니다. 추출한 폴더의 \files\validator.cpp를 업로드해줍시다.
- [테스트] : Polygon의 [Invocations]와 비슷한 기능입니다. 하단의 [소스 추가하기]에서 정답/오답 코드와 기대 결과를 등록하고 채점해봅시다. 해당 문제의 경우 상단에 [스페셜 저지]버튼이 추가로 있을 텐데, 여기에 추출한 폴더의 \files\checker.cpp를 업로드해줍시다.
- [더 보기] : 출제자와 검수자를 등록할 수 있습니다.
고생 많으셨습니다. 드디어 문제가 완성되었습니다!
개인적으로 폴리곤을 처음 사용할 때 되게 막막했는데, 이 글이 출제나 검수에 도전해보실 분들에게 도움이 되었으면 좋겠습니다.
꼭 대회 개최가 아니더라도, 출제 자격만 갖춘다면 백준 홍보게시판에 종종 올라오는 Call for Tasks 등의 기회도 있으니 참여해보시면 좋겠습니다.
긴 글 읽어주셔서 감사합니다.