안녕하세요?
SRM371 div2 ☆★승리의zizavino☆★ 입니다 >_<
div2라도 우승하니 짜릿한 것이 감격스럽습니다 >_<
잡설 그만하고 editorial..
A. 250
이 n명이 m명에게 일일이 한명씩 투표합니다.(# of votes = n times m) 투표는 알파벳을 주는데 a가 좋은거고 z가 나쁜겁니다.
이 때 당선자 i는 누구냐 하면은..
[다른 임의의 사람 j에 대해 (i를 j보다 좋게 평가한 사람) > (j를 i보다 좋게 평가한 사람)]
인 사람입니다. 즉 1 on 1으로 매치시켰을 때 전부 이기는 사람이죠..
그런 사람 없으면 없다고 하는 문제였습니다. 난이도는 그렇게 높진 않았지만..
저는 [i와 j를 같게 평가한 경우]를 고려하지 않고 테스트 3개만 넣어보고 "WE ARE BUT MEN, SUBMIT!"하고 나서 4번째 테스트를 넣어보니 틀렸길래 =_= 고쳐서 리섭했습니다ㅠ
제가 이문제만 챌을 5개 성공시켰는데 많은 사람들이
SUM(vote[n][m] - 'a')을 기준으로 제일 큰 애를 당선시켰더군요.
za
bc
bc
로 챌해서 5개나 건졌-_-;;
B. 500
이 문제는 div1의 250? 300? 과 같다고 하더라구요.
가로 길이 w와 세로 길이 l가 입력으로 주어집니다.
이 때 (0, 0)부터 시작해서 (1, 0) 방향으로 가다가 벽에 부딪히면 (0, 1) 방향으로 가고.. 해서
(1, 0) -> (0, 1) -> (-1, 0) -> (0, -1) 방향으로 갑니다.
그 때 마지막 점을 구하는건데요
예를 들면
mlkji
nwvih
oxytg
pqrsf
abcde
하면 마지막 점은 (2, 2)입니다. 이걸 내보내는 문제입니다.
저는
spoiler="더 보기..." <- (0, 0)
(a, b) <- (w - 1, l - 1)
while(x + 1 < a && y + 1 < b) {
++ x; ++ y; -- a; -- b;
if(x == a || y == b) return (a, b)
return (x, y + 1)
[/spoiler]
과 같이 했습니다. 증명은 해보셔요 >_<
C. 1000
땅의 높낮이가 있어서 비가 오면 높이가 같거나 작은 곳으로 흐릅니다.
이 때 모든 곳에 비가 올 때 어느 곳에 하수도를 설치하면 모든 물을 뺄 수 있는지
그 최소 하수도 수를 구하는게 문제입니다.
저는
[spoiler="더 보기..."]while(아직 안된데 있을 때) {
안된 곳 중에서 제일 낮은 곳 (a,b)를 고른다
그 곳에 설치하고 물 뺄 수 있는데 다 뺀다
카운터 증가
}
출력 카운터
[/spoiler]
와 같이 했습니다.
가장 낮은 곳에 설치하는건 당연한 그리디인거 같구요 >_<
읽어주셔서 감사합니당
코드는 복사를 못하네요 ㅠ