본문으로 바로가기

Codeforces Round #389 (Div. 2, Rated, Based on Technocup 2017 - Elimination Round 3): http://codeforces.com/contest/752


A. Santa Claus and a Place in a Class

n,m,k가 주어지는데, 전체 책상이 m행 n열만큼 있고 여기서 k번 자리에 앉는다는 뜻.

아래 그림을 보면 이해가 쉽다.


예를 들어, 4 3 9라고 하면 초록색 책상을 의미한다.

lane이 4개 desk가 3줄 있는 곳에서 9번 책상은 2행 2열 왼쪽 책상이다. 그래서 답을 2 2 L로 하면 되고,

파란색의 경우는 4 3 24로 물어보고 답은 4 3 R이라 출력하면 된다.


빨리 풀려고 제대로 계산안하고 대충 때려넣다가 계속 답이 제대로 안나와서 결국 펜 잡고 계산을 정확하게 했음 ㅠㅠ

역시 그냥 정공법이 항상 평균은 보장해주는 것 같다.






B. Santa Claus and Keyboard Check

두 문자열이 주어지는데 이게 키보드가 삐꾸라서 원래 A라는 문자열이 쳐져야 되는게, B라는 문자열이 쳐졌다고 한다.

근데, 이런 경우라면 반드시 각 문자들은 다른 문자와 1:1 matching이 되어야 한다.

helloworld
ehoolwlroz

위에서 두 문자열을 보면, (h,e), (l,o), (d,z) 이렇게 3개가 매칭되는 것을 알 수 있다.

만약 1:1 매칭이 되지 않는 경우는 -1을 출력하고 다른 문자와 매칭되는 경우가 전혀 없는 경우는 0을 출력하면 됐다.


근데, 이거 한참 D풀고 있는데 핵당했다고 메세지가 떴다.

D는 이따가 얘기할거지만, 거의 다 푼거 같아서 빨리 D를 해결하고 B를 보려고 했는데,

아놔.. 결국 5분 남겨놓고 B 핵당한거 체크하다가 B,D둘다 놓쳐버렸다 ㅠㅠ


나중에 핵 당한거 확인해보니 한번에 맞추기 참 까다로운 문제였다.

특히 핵 안당하고 맞춘사람은 정말 몇명 없었고,

system 채점에서 안나간 사람들도 전체에 반도 안됐다.


밑에는 나중에 수정해서 AC를 받은 코드다.





C. Santa Claus and Robot

무슨 말인지 잘 해석을 못해서 좀 고생했다.

문제 자체는 상당히 쉬웠는데, pretest에서 어떤 테케 하나를 제공하지 않았다면,

아주 크리스마스가 핵 축제가 될뻔한 문제였다. ㅋㅋ

,

문제는 로봇이 항상 최단거리로만 움직인다.

그래서 원래 좌표를 딱딱 지정해주면 로봇이 알아서 최단거리로 움직인다는 건데,

그렇게 명령을 내렸던 좌표값들 적어둔걸 어디다 잃어버렸다고 한다.

그런데, 로봇이 지나온 길은 다 알고 있음.


그럼 그러한 좌표들이 최소한 몇개냐~? 하는게 질문이었다.

당근 왼쪽으로 움직이다가 한번이라도 오른쪽으로 움직이려고 하면, +1을 하면 되는 문제

다만 L에서 U로 가다가 R이 나왔다고 하면, 그냥 R빼고 남은 모든 방향을 초기화 해야 된다.

(어설프게 R,U나 R,D와 같이 2개만 초기화 하면 WA를 받는다.)

왜 그런지는 해보면 알거임.


나도 해당 테케를 고려하지 않아 한번 WA를 받았지만, 바로 고쳐서 AC를 받을 수 있었다.





D. Santa Claus and a Palindrome

처음에 k, n이 주어진다.

k개의 문자열과 모든 문자열의 길이는 n이라는 뜻이다.


문자열 옆에는 beauty가 주어지는데,

주어진 문자열들을 사용해서 팰린드롬을 만들고, 이때 이 팰린드롬의 뷰티값은 사용한 모든 문자열들의 뷰티 합이고

이 뷰티 값은 항상 0이상이어야 한다.


나는 이 문제를 trie를 사용해서 접근했다.

스트링 들어오면 그걸 뒤집어서 trie에서 검색하고,

트라이에 해당 스트링이 있으면 그 스트링에 해당되는 고유번호를

지금 입력받은 스트링에도 부여해서 trie에 insert해주고

나중에 그러한 고유번호끼리 묶어서 2개씩 짝지어 beauty를 맥스로 만들려고 했다.


그런데 해보면 알겠지만, 문제가 상당히 많다.

그리고 나중에 콘테 다 끝나고 사람들 코드를 좀 봤는데,

트라이로 푼 사람을 한명도 못봤다 ㅠㅠㅠㅠ


또, 매번 트라이라고 생각되는 문제를 접할 때 마다 항상 문제가 됐던 부분이 있는데,

삭제가 항상 문제다... 결국 나는 트라이 할때마다 삭제를 제대로 구현해본 적이 한번도 없는데

뭔가 삭제를 깔끔하게 해결하는 방법을 아직도 잘 모르겠다.


삭제를 하고 나면 트라이에 그 지저분한 흔적들이 남는거 같아서...

그렇다고 메모리 allocation 한거를 delete하자니 시간이 오래 걸릴 것 같고...


아무튼 결국 제대로 된 답도 안나와서 submit도 못했다.


일단은 답을 수정할 때까지 완전 엉망진창인 소스를 올려본다.

빠른 시일내로 해결해야지 ㅠㅠ





E. Santa Claus and Tangerines

이 문제는 보지도 못했다. 근데 D보다 AC받은 사람이 더 많았다. ㅡ,.ㅡ;;

또, D와 마찬가지로 시스템에서 나가기 쉬운 문제였던 것 같다.

아무튼 오늘 풀어봐야겠다.




F. Santa Clauses and a Soccer Championship

당근 아직 못봤다. ㅋㅋ




# 최종 스코어 #





아직 2016 Good Bye contest가 남긴 했지만, 그 콘테스트가 23시 35분에 있으니까 다 보고 나면 새해가 된다.

결국 올해는 green에서 마무리 하는구나 ㅠㅠ


그래도 새해 첫 스타트는 깔끔하게 cyan에서 시작하기를...

그리고 2017에는 blue좀 달아보자 ㅠㅠ! 제바알~



'PS - OJ > Codeforces' 카테고리의 다른 글

Codeforces Round #390 (Div. 2)  (0) 2017.01.23
오오? legendary grandmaster~!  (0) 2017.01.05
Codeforces Round #388 (Div. 2) - All Solved (Edited)  (2) 2016.12.20
Codeforces Round #386 (Div. 2)  (0) 2016.12.19
Codeforces Round #384 (Div. 2)  (0) 2016.12.15