0~9까지 적혀 있는 키패드가 있다. 수열과 키패드에 지문이 묻어있는 숫자가 주어진다. 비밀번호는 지문이 묻어있는 숫자들로 이루어져있고, 주어진 수열의 가장 긴 부분수열이다. 단, 부분수열은 연속적이지 않아도 된다. 이때 비밀번호를 구하는 문제다.
간단하다. 설명이 필요없다.
B. Knights of a Polygonal Table
검사들이 서로를 죽이는데, 자기보다 힘이 약한 기사만 죽일 수 있다. 헌데 검사들은 양심이 있어서 $k$명 초과로 죽이지 못 한다. 그리고 검사들은 다른 검사를 죽이고 나면 그 검사의 돈을 모두 가져올 수 있다. 각 검사가 얻을 수 있는 돈의 최대값을 구하는 문제다.
검사들의 power를 오름차순으로 정렬한 뒤 for문으로 올라가면서 가장 큰 $k$개의 돈들을 저장해두면서 update해나가면 된다.
B번치고 매우 어려웠던 문제. 내가 푼 방법은 따로 있는데 다시봐도 어떻게 풀었는지 감이 안 잡혀서 tutorial을 보니 깔-끔. vector로 관리해도 되지만 multiset을 한 번도 안 써봐서 multiset으로 관리해봤는데 조금 까다로운 면이 있다.
두 직사각형이 주어지는데 하나는 $x, y$축에 평행하며 하나는 45도 기울어져있다. 두 직사각형이 조금이라도 겹치는 부분이 생기면(점 이라도) YES를, 아니면 NO를 출력하는 문제다.
좌표가 -100~100으로 매우 작으므로 배열에 다 넣을 수 있다.
좌표가 작은걸 알았음에도 배열을 생각 못 했는데 배열을 쓰니 별찍기 문제로 바뀌어서 너무 쉬워졌다.
사실 처음 봤을 때 좌표로 판단하려면 if문 덕지덕지 난리치겠다 싶어서 CCW로 판단하려했다. 한번 틀린건 CCW에서 한 점이 다른 직선 위에 있을 때 판단을 안 해주었고, 그 다음 틀린건 한 점이 다른 사각형 안에 있지 않아도 겹치는 부분이 생길 수 있다는걸 몰라서 틀렸다. 두 선분이 교차하는지 판단하는 방법으로 나중에 풀긴 풀었는데 배열에 다 넣고 판단하는 것 보다 수십배 어렵다.
두 명이 각각 하나의 pair를 갖고 있고 서로 pair값을 모른다. 두 pair는 하나의 공통 원소를 갖고 있고 나머지 원소는 반드시 서로 다르다. 두 명은 서로 아무 pair나 얘기해주는데 각자 얘기하는 pair에는 자기가 갖고 있는 pair도 반드시 포함된다. 서로 pair를 얘기해주는 것을 듣고 다른 사람이 두 명이 갖고 있는 pair의 공통 원소를 유추할 수 있으면 그 공통 원소를 출력, 다른 사람이 유추할 수는 없지만 두 사람이 상대방이 말하는 pair들을 듣고 공통 원소를 유추할 수 있으면 0, 두 사람도 유추할 수 없으면 -1을 출력하는 문제다.
두 사람이 갖고 있는 pair쌍의 후보를 먼저 선택하자. 그리고 그 후보들을 모두 보는데, 후보의 공통 원소 외의 원소를 갖는 pair가 있으면 -1이다. 모든 후보를 다 돌았는데 그런 경우가 없다면, 공통 원소가 될 수 있는 수가 1개이면 다른사람도 유추할 수 있고, 공통 원소가 될 수 있는 수가 2개이면 다른 사람은 유추할 수 없지만, 두 명은 각자 자신의 pair는 알고 있기 때문에 서로의 pair의 공통 원소를 유추할 수 있다.
일단 문제를 이해하는게 너무 힘들었다. 문제이해만 하면 그냥 구현문제수준이라서 쉬운데...
$x$좌표 -100지점에 큰 배들이 $n$척 있으며 $x$좌표 100지점에 큰 배들이 $m$척 있다. 두 큰 배무리는 $x$좌표 0에 있는 작은 배 2척를 향해 레이저를 쏜다. 레이저는 쭉 직진하여 작은 배 뿐만 아니라 다른 무리에 있는 큰 배 까지 파괴시켜버리는데, 두 큰 배무리를 가장 많이 파괴하도록 작은 배 2척을 배치했을 때 파괴되는 큰 배의 수를 구하는 문제다.
$n, m$이 작으므로 2중 for문으로 서로가 다른 무리의 배에게 레이저를 쐈을 때 레이저가 $y$축을 지날 때 $y$좌표를 모두 구할 수 있다. 그런 $y$좌표마다 파괴되는 배들을 set으로 저장해놓으면 각 좌표에 작은 배를 1대 놓았을 때 파괴되는 배의 수를 알 수 있다. 레이저가 지나는 $y$좌표는 최대 60 * 60개 나오므로 총 3600개의 좌표 중 2개를 골라 파괴되는 배들의 개수를 시간 내로 구할 수 있다.
구현 수준의 매우 쉬운문제.
F번은 읽어보지 않았지만 E번까지 전부 구현문제인데다가 문제이해가 어려운 경우가 많아 아쉬운 라운드. 다른 한국 사람들도 D번은 전부 이해가 어렵다고 언급한걸 보면 나만 그렇게 느낀것은 아닌것 같다.
