남남서의 블로그

우리 팀 789가 대회 1등을 차지했다.내가 푼 문제는 C, I, J, K 이다. J. Starwars (32 min., +2, First Solve; 2nd AC from 789) n(≤1,000)개의 정점(solar system)이 있고, 그중 일부는 human-controlled이며, 또 다른 일부는 military base가 설치되어 있다. human-controlled와 military-base-installed 여부는 독립적이다. 또한 각 정점 사이에 m(≤8,000)개의 간선(wormhole)이 있다. 간선을 사용할 때마다, 그 간선에서 인증서(certificate)를 발급해 준다. 여러 간선을 사용하면, 그 경로에 의해 얻는 인증서가 순서대로 쌓인다. 인증서는 총 C(≤20)가지가 존재한다..

팀으로 참가해, 12문제 중 10문제를 풀고 전체 4등의 결과를 얻었다. 팀 연습을 안 해봤어서 걱정했는데 좋은 결과가 나와서 다행이었다.대회 준비에 부족한 부분이 있긴 했지만 내가 준비해도 저런 문제가 안 생겼을 거라고는 장담 못 할 것 같다... 주최 분들이 정말 수고하신게 보였다. 내가 푼 문제는 E, K, I였다. 각각 내 풀이를 써본다. E배열을 one-based로 사용해 min-heap을 만든다. ($i$번째 노드의 부모가 $\lfloor i/2 \rfloor$가 되는 식으로) 이 때, $1$부터 $N$까지의 수를 어떤 특정 순서로 힙에 삽입해서, 모든 작업이 끝났을 때 $p$번째 위치에 $k$가 적혀 있도록 하는 방법을 아무거나 하나 출력하는 문제이다.처음에는 방법의 수를 세는 것으로 잘못 ..

nypc01_review.md 제 1회 NYPC에 참가했다.예선예선 문제는 처음 보는 유형들이라 당황스러웠다. 간단한 문제들은 적당히 풀었고, 지질학자 마리드도 풀었다. 넥스카 유적 문제도 적당히 만져봤는데, 그렇게 좋은 결과가 나오지는 않았다.본선본선 대회는 판교에 있는 넥슨 사옥에서 열렸다.옷이 기모가 들어있어서 적당히 따뜻해서 좋았다. 그런데 대회 때는 긴장하고 긴장하면 배가 아픈데, 그래서인지 꽤 춥게 느껴져서 힘들었다.SN과 M이 주어지고, N×N 격자에 있는 블럭들은 중력에 따라 아래쪽으로 쏠린다. 90도 회전시키고 모든 블럭이 떨어질 때까지 기다리는 것을 M번 했을 때 최종적인 결과를 출력하는 문제였다.풀이N, M ≤ 100 이어서 적당히 풀면 된다.M성냥개비로 이루어진 수식이 있다.숫자는 ..

이번 라운드는 상품이 꽤 화려했다.1 place — PlayStation 42 place — Xbox One3-5 places — Sega MegaDrive 16bit with games1-50 places — Wunder Fund T-Shirts!51-500 places — 50 T-Shirts to random participants!꽤 많은 참가자들이 참가했고, 라운드 시작 시 서버가 힘들어해서 시작이 5분 지연되기도 했다. A. Slime Combining\(x\) 슬라임은 \(1\) 슬라임이 총 \(2^{(x-1)}\)개 뭉쳐져 생긴 것이다. 귀납적인 생각을 통해, \(n\)에 \(2^x\) 비트가 켜져 있다면, \(x+1\) 슬라임이 존재하고, 모든 슬라임들은 내림차순으로 있을 것이다.본인 소..

A번. 그냥 위치가 x에 있으면 x+(a_x) 로 이동한다는 말 같아서 대충 했더니 잘 된거같다.B번.연결되어있는 수(=교환할 수 있는 수)들을 BFS로 묶고, 정렬해서, 재배치하고, 끝.그런데 지금 보니까 시스템 테스트 통과를 못했다. 어...?C번.첫 번째로 읽을 책과, 나머지 책들을 생각해보자.첫 번째 책이 중간에 꽂혀있으면, 그걸 다 들어내고 읽어야 하고, 결국 나머지 책들의 순서는 그대로인채 첫번째 책만 제일 위에 놓이게 된다.그러면 애초에 아무것도 안 드는게 이득이겠지? 그래서 첫 번째로 읽을 책은 제일 위에 가야 한다.두 번째로 읽을 책을 찾기 위해 다른 책들을 들어낼 때도, 어차피 그 두번째 책이 어디에 꽂혀있었든 결과는 같다.그렇다면 최소한으로 책을 드는 것이 최적이겠고, 첫번째 책이 방..