레주메는 보통 MS Word 등의 워드프로세서나 LaTeX로 작성하는 것이 일반적입니다. 하지만 둘 모두 문서 작성에 초점이 맞춰져 상호작용 기능이 부족했고, 여기에 제 힙스터 기질이 더해져 웹 기반 레주메를 만들어보자는 생각이 들었습니다. 그래서 구글의 머티리얼 디자인을 채용해 웹 기반 레주메를 만들었었습니다. CSS 전처리기로는 Less를 사용했고, Font Awesome 아이콘도 활용해 각 프로젝트의 GitHub 페이지 링크를 걸고, 아이콘을 누르면 프로젝트 스크린샷을 보여주는 기능 등을 넣었습니다.

그런데…

여기까지 작업은 작년에 마치고, 학교 후원 인턴 프로그램인 SES에 지원할 때 사용했습니다. 별도로 문서 파일로 된 버전이 없었기 때문에 이력서 제출할 때는 연락처와 레주메 링크를 txt 파일로 저장하고 이 txt 파일을 제출했습니다. 지금 생각해보면 정말 패기있는 결정이었네요. 제가 지원했던 회사는 졸업 예정 학생만 뽑는다고 해서 결국 인턴십은 하지 않았지만 그래도 연락이 온 걸 보면 썩 나쁘지는 않았나 봅니다.

…라고 착각하고 있었습니다. 내년 1학기 인턴을 준비중이라 업데이트를 위해 GitHub에 들어갔더니 예전에 만들어 놓은 레주메에 고칠 점이 너무 많이 보였습니다. 1년 학교를 더 다니는 동안 성장한 증거라고 생각하고 있습니다. 큰 문제점은 두 가지였습니다.

  1. 지나치게 많은 정보를 담고 있었습니다. 지원하는 회사는 수많은 지원서를 봐야 하는데, 작은 취미 프로젝트들까지 전부 써 놓았더니 지원서가 너무 길어 보였습니다. 레주메 보다는 포트폴리오에 가까운 구성이었습니다.
  2. 파일로 존재하는 실체가 없었습니다. 레주메 링크를 txt로 첨부하는 것은 상황에 따라 무례해 보일 수도 있고, 추가 접속을 필요로 한다는 점에서 좋은 UX가 아니었습니다.

그래서 기존에 만들어 놓은 웹 기반 레주메의 내용을 다듬으며, 브라우저에서 보이는 웹 문서 파일 뿐 아니라 PDF 출력 파일까지 같은 소스코드에서 뽑는 것을 목표로 리팩토링을 시작했습니다.

서론이 길었네요. 그래서 이번 게시글에서는 기존 포트폴리오 스타일 레주메를 리팩토링하면서 어떤 내용과 디자인을 다듬는데 주력했는지, 그리고 웹 기반 PDF 문서 파일을 만들 때 사용한 CSS 기술 소개와, 화면 기반 컨텐츠와 어떤 차별점을 두었는지를 공유해보려고 합니다.

내용 다듬기


리팩토링 전 레주메 페이지와 프린트 미리보기입니다. 장황하고, 한 눈에 잘 안 들어오고, 두서가 없습니다. 프린트 미리보기에서는 페이지가 잘려 있는 모습도 확인할 수 있습니다. 또 하나의 문제점은 오래된 내용을 위쪽에 배치하고, 새로운 내용을 아래쪽에 배치한 것입니다. 기존 구성은 Education과 Works 두 파트로 나뉘어 Education에서는 학업 진행상황과 관련 연구 및 프로젝트를 혼합해 서술했고, Works 문단에서는 수상 내역과 진행한 프로젝트를 혼합해 서술했습니다.

이러한 구성이 전체적인 내용 파악을 어렵게 한다고 생각되어 새로운 레주메 페이지는 Education, Researches and Projects, Awards의 세 부분으로 나누고 최근 진행한 프로젝트가 위쪽에 오도록 내용을 다듬으며, 각 프로젝트에 대한 설명을 핵심만 짧게 포함하도록 다듬었습니다. 또한, 페이지 마지막에 최종 수정 날짜를 추가해 얼마나 최신 변경사항까지 다루고 있는지를 표기했습니다.

디자인 다듬기

폰트 사이즈 축소

기존에는 구글의 머티리얼 디자인 타이포그라피 가이드를 최대한 지키려고 노력하며 작업했습니다. 폰트 사이즈와 줄 간격 등을 개발자 도구로 뽑아서 그 값을 그대로 사용하려고 했습니다. 하지만 해당 가이드는 앱이나 웹 가독성에 최적화 되어 있었고, 레주메에 사용하기에는 줄 간격 등의 여백이 조금 넓어 보였습니다. 그래서 이번 리팩토링에서 머티리얼 디자인의 느낌은 유지하면서, 전체적으로 여백과 폰트 사이즈를 조금씩 줄였습니다.

Chip 삭제

기존 디자인은 머티리얼 디자인의 chip을 사용해 다양한 정보를 표시했습니다.

하지만 내용 리팩토링을 하면서 연구나 프로젝트를 제외한 소규모 취미 프로젝트들 관련 내용을 대부분 삭제했기 때문에 chip을 사용할만한 자리가 많이 남지 않았고, 어설프게 사용할 경우 실제 중요한 내용보다 chip에 시선이 머무르는 것처럼 느껴져 대부분의 chip을 삭제했습니다.

페이지 우측 공간 활용

위쪽 스크린샷에서 확인하시는 바와 같이, 기존 디자인에서는 프로젝트 제목 바로 옆에 GitHub 링크나 소개 스크린샷, 사용 기술 등의 정보가 포함되어 있었습니다. 새로운 디자인에서는 연도 정보를 제외한 다른 추가 정보들을 float: right CSS를 활용해 페이지 우측으로 옮겼고, 시선을 덜 차지하도록 변경했습니다. 아래는 변경된 디자인입니다.

여기까지 변경 사항을 적용해 레주메 웹 페이지는 다음과 같이 변했습니다. 이제 PDF 페이지를 디자인할 차례입니다.

문서 파일로 내보내도 예쁜 웹페이지 만들기

웹페이지를 인쇄할 때 PDF 내보내기 옵션을 사용하면 PDF 파일로 출력이 가능합니다. 하지만 별도로 신경써서 만들지 않는 경우 세로로 무한히 스크롤이 가능한 웹 페이지와, 페이지 단위로 내용이 잘리는 문서 파일의 차이로 인해 그렇게 예쁜 레이아웃이 나오지는 않습니다. 여기서 CSS의 기능을 활용하면 문서 파일에서도 예뻐 보이는 페이지를 디자인할 수 있습니다. 제가 사용한 CSS 기능은 두 가지입니다. 첫 번째는 CSS의 media 쿼리, 두 번째는 page-break-before 스타일입니다. 각 요소에 대한 자세한 설명은 MDN의 미디어 쿼리 페이지와 page-break-before 페이지를 참고하시고, 이 포스트에서는 간단한 사용법만 다룰 예정입니다.

  • CSS 미디어 쿼리는 어떤 미디어에서 보고 있냐에 따라 다른 CSS를 적용할 수 있게 해 줍니다. @media screen {} 내부에 정의한 내용은 화면으로 볼 때만 적용되며, @media print {} 내부에 정의한 내용은 프린트 할 때만 적용됩니다. 화면 크기 등의 제한 조건을 넣어 반응형 웹사이트를 만들 때에도 CSS 미디어 쿼리가 사용됩니다.
  • page-break-before은 문서를 프린트할 때 HTML 요소 앞에서 페이지가 어떻게 넘겨질지를 결정합니다. always로 설정할 경우 Word 등에서 Ctrl+Enter로 페이지를 넘기는 것처럼 페이지가 인쇄되도록 할 수 있습니다.

이 두 가지 기능을 활용해 웹 기반 레주메 페이지를 문서 파일로 볼 때에도 예쁜 디자인을 유지하도록 추가 작업에 들어갔습니다.

  1. 문서 파일 처음에 있는 마진을 제거했습니다. 웹 페이지에서는 머티리얼 디자인의 특징인 ‘실제 종이를 들고 읽는 듯한 느낌’을 중시했기에 페이지 상단에 배경이 보이도록 여백을 넣었습니다. 문서 파일에서는 페이지 상단에 어색한 공백을 만들기 때문에 이를 제거했습니다.
  2. 동작하지 않는 인터랙션 기능을 제거했습니다. 웹 페이지에서 해당 아이콘을 클릭하는 경우 라이트박스를 이용해 스크린샷과 영상 자료 등을 띄워주도록 구성되어 있습니다. PDF 파일 내에 링크는 넣을 수 있기 때문에 GitHub 링크는 남기고, JavaScript가 필요한 버튼들은 제거합니다.
  3. 1번과 마찬가지 이유로 머티리얼 디자인의 그림자는 제거했습니다.
  4. 문서 파일에서는 페이지 개념이 있는 관계로, 적절한 곳에 page-break를 삽입합니다. 페이지가 나뉘는 경우 page-break-before 전에 프린트 미디어에서만 보이는 hr 태그를 하나 더 삽입해 문서의 각 섹션이 하나의 페이지 안에 담기도록 합니다.
  5. 웹 페이지에서는 hr 태그가 가로를 전부 채우지만, 실제 문서 파일에서는 문서 양쪽에 공백을 두는 것이 일반적이므로 추가 패딩을 적용합니다.
  6. 최종 수정 날짜 옆에 온라인 레주메 링크를 삽입합니다. 이를 통해 예전 버전의 문서 파일을 가지고 있을 때 최신 버전의 레주메를 쉽게 찾을 수 있습니다.

이렇게 완성된 레주메는 제 GitHub Page에서 확인하실 수 있습니다. 출력 파일은 Letter, 여백 없음을 기준으로 작업했으니 PDF 버전도 Ctrl + P로 확인해보세요!

올해는 hacking4soju, 그레이해시, 삼성 소프트웨어 센터와 함께 연합해 hacking4danbi 팀으로 대회에 출전했다. 작년에는 그레이해시와 PLUS의 연합 팀인 playhash로 진출해 아쉽게 예선 통과에 실패했었는데, 올해는 성공적으로 본선에 나갈 수 있었다. 특히 해외 팀과의 연합으로 예선 때 사이클이 잘 맞아서 우리가 잘 때 hacking4soju에서 문제를 풀어주거나, 그 쪽 새벽 시간대에 우리가 활발하게 문제를 풀었다.

대회는 라스베가스에서 3일간 열리지만, 올해는 대회가 legitBS 팀의 커스텀 아키텍처인 cLEMENCy 아키텍처를 기반으로 문제가 출제될 것으로 예고되어 있었고 아키텍처 정보가 대회 24시간 전에 공개되어 사실상 4일 대회라 봐야 했다. 대회 방식은 Attack & Defense로 첫 두 날은 8시간 정도, 마지막날은 4시간으로 짧게 끊는 스케줄이었다.

대회 전에 PLUS 멤버들은 ndh 아키텍처를 기반으로 IDA 로더, ROP gadget, binary diff 툴 등의 설계를 연습해 갔다. 나는 x64 아키텍처로 컨버팅 하는 부분을 준비했다. 하지만 cLEMENCy 아키텍처가 9bit, middle-endian으로 작정하고 더럽게 나와서 컨버팅을 제대로 처리할 수가 없었다. 아키텍처가 공개되었을 때 9bit aligned instruction은 처리할 수 있었지만 middle-endian 메모리 액세스를 효율적으로 처리할 수 없고, 작업량이 많아 대회 전에 끝낼 수 없을 것 같아 컨버팅은 포기하고 다른 툴링에 집중했다. 우리는 어셈블러, 디스어셈블러, ROP gadget, 웹 기반 CFG 분석 도구를 준비했고 꽤 잘 준비한 편일거라 생각했지만 다른 팀들이 준비한 수준도 굉장히 높아 깜짝 놀랐다.

대회장 안에 자리는 팀별로 총 8자리가 준비되어 있었고, PLUS 학부생 멤버는 그 중 두 자리를 할당 받았다. 나는 세 날 모두 들어갔고 다른 멤버로 첫 두 날에는 ebmoon이, 마지막 날에는 flamehaze가 참가했다. 처음에는 대회장에 들어가는게 exploit 경험이 많은 멤버가 들어가야 한다고 생각했으나, 대회를 마치고 나서 대회장 내에는 모니터링 및 커뮤니케이션 담당을 두고 실력이 좋은 멤버들이 편한 환경에서 작업할 수 있게 하는게 중요하다는 것을 깨달았다. PPP 박세준님의 후기에도 비슷한 내용이 있었다.

처음에 나는 하루나 하루 반 정도 대회장에 들어가보고 다른 멤버들을 들여보내려 했었다. 하지만 첫 날의 대회 결과에 대해 논의하는 과정에서 패치를 한 군데서 관리할 필요성이 제기되었고, 내가 패치 및 모니터링을 담당하게 되어 대회 끝날때까지 대회장에서 공격 및 수비 모니터링과 대회장 내외 커뮤니케이션 역할을 맡았다. Attack & Defense 방식과 망분리 환경에 익숙하지 않아 따로 모니터링 도구가 필요할 거라고 생각하지 않아서 관련 도구 개발을 대회 둘째 날부터 시작했는데 이를 미리 준비했더라면 첫 날에 더 나은 성적을 냈을 거라 생각한다. 팀이 흩어져 있어 정보가 잘 공유되지 않다보니 현재 공격/수비 상황을 알지 못해 팀원들끼리 전략적으로 문제에 집중하지 못했던 점이 아쉽다. 올해는 중하위권인 11위로 마무리했는데 다음해 또 나올 기회가 된다면 더 잘할 수 있을 것이라 생각한다.

이번 대회를 거치며 다양한 분들에게 도움을 받았다. 왕복 항공료는 삼성 소프트웨어 센터에서 지원을 받았고, 숙소는 POSTECH 학생지원팀의 지원을 받아 개인 부담이 크지 않게 국제 대회에 다녀올 수 있었다. 그레이해시 측에서도 함께 대회를 하기 좋은 큰 방을 잡아 주시고 대회에 필요한 장비를 준비해 주셔서 좀 더 쾌적한 환경에서 대회를 진행할 수 있었다. 금전적인 지원 뿐 아니라 같이 대회를 나가며 어깨 너머로 배운 지식들도 추후 동아리 활동을 하면서 큰 도움이 될 것이라 생각한다.

이번 참가에서 가장 인상 깊었던 부분 중 하나는 커뮤니티가 주도하는 대회와 컨퍼런스 방식이었다. 맥주를 마시며 농담을 섞어 가며 컨퍼런스 결과를 발표하고, 직접 그 대회를 준비한 사람들에게 찬사가 돌아가고 격식없이 서로를 대하는 모습이 대회와 전혀 상관 없는 의전 행사만 한 시간이 넘는 국내 대회들과 비교되었다. 해외 대회들이 국내 대회를 의식해 선수 대우를 더 강화했듯이, 국내 대회들도 해외 대회의 좋은 점을 보며 서로 발전했으면 좋겠다고 생각한다.

이번 DEFCON 본선에 참가하며 국제대회 Qualification을 통과한 것도 처음, 동아리 이외의 사람들과 함께 해킹을 해본 것도 처음, 세계 유명 팀들과 얼굴을 보며 경쟁을 해 본 것도 처음, 여러모로 처음이 많은 대회였다. 대학에 입학하고 2년동안 방학마다 합숙에 참가하며 짧다면 짧고 길다면 길게 해킹을 공부해 왔는데, 다시 초심으로 돌아가 해킹이라는 분야에 대해 한 번 더 생각해 보는 계기가 되었다.

많은 것을 보고 듣는 시간이었고, 세상이 넓다는 것을 다시 한 번 느꼈다.

Attack

Mic Check

The description contains the flag.

Flag: SCTF{Welcome_to_SCTF2017_haha}

Readflag

When we execute the given file, the message says that the sum of the elements in the list should be 10. We can modify dump.py file to change the transmitted Python object. However, even if we send a list which satisfies the requirement, we cannot get the flag.

If we send malformed data, we can get the server’s file name test.py from the error log. The server unpickles our object, which leads to an arbitrary code execution. It has filtering on some system calls, but open and read is not filtered. We can get the flag by reading test.py source code.

code

Flag: SCTF{3a5y_e4zy_p1ckl1ng}

Letter To Me

  • Stage 1 – Get the php source file

We can get the source files using PHP local file inclusion vulnerability.

Accessing http://lettertome.eatpwnnosleep.com/?page=php://filter/convert.base64-encode/resource=?? gives us base64 encoded ??.php file.

  • Stage 2 – Login with remote database

The login part uses mysql_real_escape_string, so we cannot perform SQL Injection. However, in index.php file, $_GET and $_POST are extracted and we can overwrite connection data in conn.php with those attack vector.

We can login by creating fake id/password pair in our own server and accessing http://lettertome.eatpwnnosleep.com/?page=login&servername={SERVER_URL_AND_PORT}&username=pwn&password=pwn&id=admin&pw=admin.

  • Stage 3 – SQL Injection

There is no SQL Injection filtering on resolve_file in note class. Therefore, we want to control the id variable in the note class.

When we send a message in the send page, a note class is created and saved to the database in PHP serialized form. However, before saving, it passes through the filtering routine which replaces some word to $profanity_word repeated to the length of that word. Since $profanity_word is also defined in conn.php , we can overwrite it and control the filtering routine. PHP unserialize function ignores extra data at the end, so we can create malicious serialized note using filtering routine. Then, we can check our SQL injection result in the show page.

SQL Injection on information_schema table gives us the table name and column name for the flag which is LTOM_Fl3g and flag respectively.

code

Flag: SCTF{Enj0y_y0ur_0nly_life}

Labyrinth

There’s an arbitrary file read vulnerability in the 3rd menu. However, accessing flag or ../flag gives us nothing. Using this vulnerability, we can get the library file from /lib32/libc-2.23.so and read process memory map from /proc/{PROCESS_ID}/maps. I brute-forced the pid during the CTF, but it can be done better by reading /proc/self/maps. With the leaked memory map, we can bypass ASLR and PIE.

When we make the labyrinth, we can leave INFO data in the labyrinth file. If we put a blank character in INFO, only the first part of the INFO will be considered as INFO and characters after that will be considered as the first line of the labyrinth. We can perform a heap overflow because labyrinth load routine only checks the line break and does not check the line length.

Do labyrinth menu first loads a labyrinth file which contains heap overflow, and clearing the labyrinth gives us two size-controlled malloc(name and comment). Therefore, we can utilize the The House of Force technique. I overwrited __free_hook in libc and got a shell.

Flag: SCTF{f0rce_y0u_t0_br34k_th3_h0us3_0f_l4byr1nth}

Defense

Dfa

In the add_node function of auto.c, namelen is defined as unsigned int. If we put length to -1, namelen becomes 4294967295, namelen + 1 will be 0, and we can perform buffer overflow.

Changing the 113th line to if (namelen >= 0x100) gives us the flag.

Flag: SCTF{simple patch tutorial}

Crypto

Toilet

Session json data looks like this {"is_admin": false, "name": "Test"}. We can only control the name part of it.

uHash is calculated in GF(2^{128}) and its value is block_1 \times key ^ {n} + block_2 \times key ^ {n-1} + \cdots + block_n \times key. If we send two requests which have the same nonce and 1 difference of (n-1)th block, xoring two sign gives us the square value of key.

We can perform square root in the field by powering the value by 2^{127} time. This gives us the key of the signer, and we can sign whatever we want.

Creating the fake session with "is_admin": true gives us the flag.

code

Flag: SCTF{Nonce_misuse_in_Wegman_Carter_MAC}

Coding

Asm

We have to automate the parsing of simple add, subtraction, multiply formula image. We can remove character overlap by classifying the RGB characters separately. Then, use the flood fill algorithm to count the number of pixel. The data does not have rotation or size variance, so counting the number of pixel is sufficient to classify each characters.

code

Flag: SCTF{Fun_with_0CR}

Turing Competition

The problem asks us to classify the given tape using turing machine.

  • 1st stage – '0' * n + '1' * m where (n>=0 and m>=0)
  • 2nd stage – '1'*x where (7 * x) % 13 == 1
  • 3rd stage – '0'*n + '1'*n where (n>=0)
  • 4th stage – '0'*p where p is prime

1st~3rd stage is quite easy. We can solve the 4th stage easily by pre-calculating the primes.

code

Flag: SCTF{Turing_Machine_is_v3ry_p0werful1}

Reversing

Easyhaskell

The program converts three bytes of argv[0] to four bytes of output, just like base64. We can do byte-by-byte brute-forcing on argv[0] to find the input which creates =ze=/<fQCGSNVzfDnlk$&?N3oxQp)K/CVzpznK?NeYPx0sz5.

code

Flag: SCTF{D0_U_KNoW_fUnc10N4L_L4n9U4g3?}

들어가며

대회 덕분에 오랜만에 또 문제풀이 코딩을 했다. 전부 풀긴 했는데 시간을 좀 오래 썼다. D에서 코딩 미스가 한 번 있었다. 문제풀이를 좀 쉬었을 때 풀 수 있는 문제 풀은 크게 안 변하는데, 코딩 속도나 풀이를 떠올리는 속도가 좀 줄어든 것 같다는 기분을 느꼈다.

풀이

Problem A. Oversized Pancake Flipper

같은 위치에서 두 번 뒤집는 것은 불필요하므로 왼쪽부터 하나씩 뒤집어보면 된다. O(N^2)으로 Large input이 풀리기 때문에 특별히 자료구조를 쓸 필요도 없다.

A.cpp
#include <cstdio>
#include <cstring>

const int MAX = 1020;

char cake[MAX];
int flipSize;

void solve() {
	int ans = 0;

	int len = strlen(cake);
	for (int i = 0; i <= len-flipSize; i++) {
		if (cake[i] == '-') {
			ans++;
			for (int j = i; j < i+flipSize; j++) {
				cake[j] = cake[j] == '+' ? '-' : '+';
			}
		}
	}

	// final check
	for (int i = len-flipSize+1; i < len; i++) {
		if (cake[i] == '-') {
			puts("IMPOSSIBLE");
			return;
		}
	}

	printf("%d\n", ans);
}

int main() {
	freopen("output.txt", "w", stdout);

	int numCase;
	scanf("%d", &numCase);
	for (int nowCase = 1; nowCase <= numCase; nowCase++) {
		scanf("%s%d", cake, &flipSize);

		printf("Case #%d: ", nowCase);
		solve();
	}

	return 0;
}

Problem B. Tidy Numbers

입력이 tidy한 경우 그대로 출력한다. 입력이 tidy가 아닌 경우 112333445552 형태로 증가하다가 감소하는 지점이 있을텐데, 그 감소하기 직전의 반복되는 부분(여기서는 555)의 첫 숫자를 1 낮추고, 그 뒤쪽을 전부 9로 채우면 된다.

B.cpp
#include <cstdio>
#include <cstring>

const int MAX = 20;

char data[MAX];

void solve() {
	int len = strlen(data);
	int lastIncrease = 0;

	int now;
	for (now = 1; now < len; now++) {
		if (data[now-1] > data[now]) {
			break;
		} else if (data[now-1] < data[now]) {
			lastIncrease = now;
		}
	}

	if (now == len) {
		// monotonic
		puts(data);
	} else {
		char ans[MAX];
		for (int i = 0; i < lastIncrease; i++)
			ans[i] = data[i];
		ans[lastIncrease] = data[lastIncrease]-1;
		for (int i = lastIncrease+1; i < len; i++)
			ans[i] = '9';
		ans[len] = 0;

		for (int i = 0; i < data[i]; i++) {
			if (ans[i] != '0') {
				puts(ans+i);
				return;
			}
		}
	}
}

int main() {
	freopen("output.txt", "w", stdout);

	int numCase;
	scanf("%d", &numCase);
	for (int nowCase = 1; nowCase <= numCase; nowCase++) {
		scanf("%s", data);

		printf("Case #%d: ", nowCase);
		solve();
	}

	return 0;
}

Problem C. Bathroom Stalls

시뮬레이션으로 풀 수 있다. 당연히 한 명씩 넣는 건 아니고, 연속된 구간의 크기와 개수를 이용해 시뮬레이션 하면 지수적으로 수를 줄여나가면서 O(log K)만에 해결 가능하다. 한 가지 관찰이 필요한데, 반씩 줄여 나가는 방식으로 시뮬레이션 하더라도 어떤 시점에서 구간의 크기의 종류가 최대 두 종류라는 사실이다. (n) -> (a, a+1) -> (b, b+1)과 같이 연속한 두 수에 대해서만 관리하면 되고, atomic하게 처리하지 않는 경우에도 최대 네 종류만 관리하면 된다. 탐색 최대 크기가 작아 굳이 Balanced Binary Tree를 쓸 필요는 없었지만 코딩하기 귀찮아서 set을 발라서 해결했다.

C.cpp

#include <cstdio>
#include <set>

typedef long long ll;

ll total, k;

struct state {
	ll n;
	mutable ll count;

	bool operator < (const state &t) const {
		return n < t.n;
	}
};

void insertToSet(std::set < state > &set, ll n, ll count) {
	auto it = set.find(state {n, 0});
	if (it != set.end()) {
		it->count += count;
	} else {
		set.insert(state { n, count });
	}
}

void solve() {
	state start = { total, 1 };

	std::set < state > set;
	set.insert(start);

	while (k) {
		auto it = --set.end();
		if (it->count >= k) {
			printf("%lld %lld\n", it->n/2, (it->n-1)/2);
			return;
		} else {
			k -= it->count;
			insertToSet(set, it->n/2, it->count);
			insertToSet(set, (it->n-1)/2, it->count);
			set.erase(it);
		}
	}
}

int main() {
	freopen("output.txt", "w", stdout);

	int numCase;
	scanf("%d", &numCase);
	for (int nowCase = 1; nowCase <= numCase; nowCase++) {
		scanf("%lld%lld", &total, &k);

		printf("Case #%d: ", nowCase);
		solve();
	}

	return 0;
}

Problem D. Fashion Show

굉장히 마음에 드는 문제였다. 독립된 두 개의 문제를 하나의 문제인 것처럼 섞어서 꼬아 놓았는데, 두 제한조건이 사실 독립이라는 것을 깨달아야 해결할 수 있다. 임의의 같은 가로줄/세로줄에 있는 두 모델을 골랐을 때 둘 중 최소 하나가 +여야 한다는 말은, 바꿔서 말하면 +가 아닌 칸은 같은 가로줄/세로줄에 최대 하나 존재할 수 있다는 말이다. 비숍 배치 문제처럼 가로세로, 대각선 조건에 대해 각각 이분매칭으로 해결한 뒤 겹치는 칸은 o로, 겹치지 않는 칸은 x와 +로 설정해 주면 된다.

D.cpp
#include <cassert>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

const int MAX = 110;

class BipartiteMatcher {
public:
	const int size;
	int *matched;
	bool *visited;

	vector < int > *edge;

	BipartiteMatcher(int size) : size(size) {
		matched = new int[2*size];
		visited = new bool[2*size];
		edge = new vector < int >[2*size];

		for (int i = 0; i < 2*size; i++) {
			matched[i] = -1;
		}
	}

	~BipartiteMatcher() {
		delete[] matched;
		delete[] visited;
		delete[] edge;
	}

	void addConnection(int a, int b) {
		assert(0 <= a && a < size && 0 <= b && b < size);
		b += size;
		edge[a].push_back(b);
		edge[b].push_back(a);
	}

	vector < pair < int, int > > match() {
		for (int left = 0; left < size; left++) {
			memset(visited, 0, sizeof(bool)*(2*size));
			tryMatch(left);
		}

		vector < pair < int, int > > ret;
		for (int left = 0; left < size; left++) {
			if (matched[left] != -1) {
				ret.push_back(make_pair(left, matched[left]-size));
			}
		}

		return ret;
	}

private: 
	bool tryMatch(int left) {
		for (auto right : edge[left]) {
			if (!visited[right]) {
				visited[right] = 1;
				if (matched[right] < 0 || tryMatch(matched[right])) {
					matched[right] = left;
					matched[left] = right;
					return 1;
				}
			}
		}
		return 0;
	}
};

int gridSize, numModel;
char original[MAX][MAX], ans[MAX][MAX];

void input() {
	scanf("%d%d", &gridSize, &numModel);

	for (int r = 1; r <= gridSize; r++) {
		for (int c = 1; c <= gridSize; c++) {
			original[r][c] = '.';
		}
		original[r][gridSize+1] = 0;
		ans[r][gridSize+1] = 0;
	}

	for (int i = 0; i < numModel; i++) {
		char t[2];
		int r, c;
		scanf("%s%d%d", t, &r, &c);
		original[r][c] = t[0];
	}

	for (int r = 1; r <= gridSize; r++) {
		for (int c = 1; c <= gridSize; c++) {
			ans[r][c] = original[r][c];
		}
	}
}

bool rowCheck[MAX], colCheck[MAX], ldiagCheck[MAX*2], rdiagCheck[MAX*2];

void solve() {
	memset(rowCheck, 0, sizeof(rowCheck));
	memset(colCheck, 0, sizeof(colCheck));
	memset(ldiagCheck, 0, sizeof(ldiagCheck));
	memset(rdiagCheck, 0, sizeof(rdiagCheck));

	for (int r = 1; r <= gridSize; r++) {
		for (int c = 1; c <= gridSize; c++) {
			int rowNum = r-1;
			int colNum = c-1;
			int ldiagNum = r+c-2;
			int rdiagNum = r-c+gridSize-1;
			if (ans[r][c] != '.') {
				if (ans[r][c] != '+') {
					rowCheck[rowNum] = 1;
					colCheck[colNum] = 1;
				}
				if (ans[r][c] != 'x') {
					ldiagCheck[ldiagNum] = 1;
					rdiagCheck[rdiagNum] = 1;
				}
			}
		}
	}

	BipartiteMatcher xy(gridSize), diag(gridSize*2-1);

	for (int r = 1; r <= gridSize; r++) {
		for (int c = 1; c <= gridSize; c++) {
			int rowNum = r-1;
			int colNum = c-1;
			int ldiagNum = r+c-2;
			int rdiagNum = r-c+gridSize-1;

			if (!rowCheck[rowNum] && !colCheck[colNum]) {
				xy.addConnection(rowNum, colNum);
			}
			if (!ldiagCheck[ldiagNum] && !rdiagCheck[rdiagNum]) {
				diag.addConnection(ldiagNum, rdiagNum);
			}
		}
	}

	for (auto p: xy.match()) {
		int rowNum = p.first;
		int colNum = p.second;

		int r = rowNum+1;
		int c = colNum+1;

		if (ans[r][c] == '.') ans[r][c] = 'x';
		else if (ans[r][c] == '+') ans[r][c] = 'o';
	}

	for (auto p: diag.match()) {
		int ldiagNum = p.first;
		int rdiagNum = p.second;

		int r = (ldiagNum+rdiagNum-gridSize+3)/2;
		int c = (ldiagNum-rdiagNum+gridSize+1)/2;
		
		if (ans[r][c] == '.') ans[r][c] = '+';
		else if (ans[r][c] == 'x') ans[r][c] = 'o';
	}

	int score = 0;
	int changed = 0;
	for (int r = 1; r <= gridSize; r++) {
		for (int c = 1; c <= gridSize; c++) {
			if (ans[r][c] != original[r][c]) {
				changed++;
			}
			score += ans[r][c] != '.';
			score += ans[r][c] == 'o';
		}
	}

	printf("%d %d\n", score, changed);

	for (int r = 1; r <= gridSize; r++) {
		for (int c = 1; c <= gridSize; c++) {
			if (ans[r][c] != original[r][c]) {
				printf("%c %d %d\n", ans[r][c], r, c);
			}
		}
	}
}

int main() {
	freopen("output.txt", "w", stdout);

	int numCase;
	scanf("%d", &numCase);
	for (int nowCase = 1; nowCase <= numCase; nowCase++) {
		input();

		printf("Case #%d: ", nowCase);
		solve();
	}

	return 0;
}