블로그 이사 중입니다 >> gumgood.github.io

[Upsolving] NWERC 2017 본문

Problem Solving/분류없음

[Upsolving] NWERC 2017

gumgood 2020. 1. 16. 11:23

 

H. 15606 High Score

일반성을 잃지 않고 a<=b<=c라고 가정합니다. 각 토큰의 수가 a, b, c일 때의 점수를 score(a,b,c)라 합시다.

min(a,b,c) = a인 경우, c에 wildcard를 다 몰아 주면 되므로 score(a,b,c+d)입니다.

min(a,b,c) > a인 경우는 x개의 wildcard를 써서 min(a,b,c)를 최대 x만큼 증가시켜 7x만큼 점수를 더 얻을 수 있습니다. 해당 카드를 c에 넣었으면 (c+x)^2 - c^2 = 2xc+x^2만큼의 점수를 증가시킬 수 있습니다. 따라서 최소한 7x > 2xc + x^2는 만족해야 이 경우가 답이 될 수 있습니다. x의 해는 7-2c미만에 존재할 수 있는데 c>=1이므로 x < 5일 때만 살펴보면 됩니다. 따라서 모든 토큰에 각각 0~4까지 더해보면서 최고 점수를 구했습니다.

 

처음 문제를 봤을 때, 쉬운 문제 같아서 빨리 풀어야겠다는 조바심이 생겼나봅니다. min(a,b,c) > a인 경우를 생각하지 못해 2번의 WA를 받았고, 1시간 쯤 지났을 때 woonikim이 준 힌트를 받아 해결했습니다.

 

B. 15600 Boss Battle

보스가 있을 수 있는 기둥들의 집합을 '후보 기둥'이라고 합시다. 처음 임의의 기둥에서 폭탄을 터뜨리면 후보 기둥은 n-3개가 됩니다. 다음, 보스가 이동하므로 후보 기둥의 개수가 2개 늘어납니다. 이를 정리하면, 폭탄을 터뜨리면 후보 기둥이 n개에서 n-3+2 = n-1개로 줄어들게 됩니다. 마지막 후보 기둥이 3개 남으면 보스를 반드시 잡을 수 있습니다. 따라서, n<=3 일 때 1, 나머지는 n-2를 출력하면 됩니다.

 

스코어보드를 보고 쉬운 문제라는 것을 캐치했습니다. 문제를 읽으면서 해답이 나왔고 빠르게 AC를 받을 수 있었습니다.

 

D. 15602 Dunglish

한 단어를 correct하게 해석하는 경우의 수를 c, incorrect하게 해석하는 경우의 수를 ic라 합시다. 주어진 문장을 해석할 수 있는 모든 경우의 수는 (c + ic)^n입니다. 여기서 correct하게 해석하는 경우의 수는 c^n이므로 incorrect하게 해석하는 경우의 수는 (c+ic)^n - c^n으로 둘 다 쉽게 구할 수 있습니다. 모든 경우의 수가 1인 경우 문장을 출력하고 c^n이 1인지 아닌지로 correct/incorrect를 판별할 수 있습니다. 주의할 점은 한 단어는 최대 8번 사전에 나올 수 있으므로 경우의 수는 최대 8^20 > 10^18이나 되어 int형으로 내면 WA를 받을 수 있습니다.

 

남은 문제들을 읽어보고 A, G를 생각해보는 동안 sogangcse가 AC를 받아줬습니다. 문제를 읽지도 않았는데 AC를 받은건 처음이라 기분이 이상했습니다(... 버스타는 맛인가). 저는 map에 vector<string>을 넣는 방식으로 처리했습니다. 어짜피 유일하게 문장을 해석하는 경우만 출력하면 되기 때문에 map에 string만 넣고 count 배열을 따로 관리하여 메모리를 아낄 수 도 있습니다.

 

G. 15605 Glyph Recognition

도형의 중심과 모양이 같으므로 가장 멀리 있는 점, 가장 가까이 있는 점을 구해 d2^2/d1^2가 점수가 됩니다. 이 거리를 계산하는 법은 해당 점이 도형의 어느 변에 닿는지를 판단하고 그 때 변과 원점과의 거리를 구해야 합니다. 모든 도형은 +x축에 꼭지점이 있으므로 모든 점들을 [0~2PI/k]의 영역에 생기는 삼각형이 있습니다. 이곳에 점들을 모두 모아 한번에 거리를 비교할 것입니다. 점들은 2PI/k단위로 회전시키면 거리를 유지한채 이동시킬 수 있습니다. [0~2PI/k]의 삼각형에 점들이 모두 있을 때 삼각형을 -PI/k만큼 회전시키면 굉장히 편해집니다. x좌표가 곧 원점과의 거리이기 때문에 x좌표만 비교하면 됩니다.

 

유효숫자의 압박에 왠만하면 실수연산은 쓰지말고 CCW로 해결하고자 했습니다. 어느 변에 닿는지, 변과의 거리는 또 어떻게 구할지 열심히 삽질하다가 뒤늦게 회전변환으로 간단하게 풀리는 것을 알게되었습니다. 20분을 남기고 풀이를 세웠으나 결국 구현을 못해 풀지 못했습니다. 업솔빙하면서 tan()와 tan2()함수의 차이를 배우고 실수를 다루는 문제에 큰 약점이 있음을 알게 되었습니다.

 

여기까지가 팀 연습 때 풀었던 문제입니다.

 

 

0 Comments
댓글쓰기 폼