PS 이야기

지금 IOI2014 대회가 한창 진행 중이다. Contest Day 1은 어제 진행 되었으며, Contest Day 2는 내일 진행된다. 개최국은 대만이며, 우리나라와 시차가 1시간 밖에 안된다. 시험은 내일 우리나라 시간으로 아침 10시부터 오후 3시까지 5시간 동안 진행된다. 문제는 아직 공식적으로 공개된바 없으며, 구글링을 해본 결과 http://math.mit.edu/~rpeng/IOI2014/ 에서 영문판, 중국어판 문제를 볼 수 있다. Live Scoreboard는 http://live.ioi2014.org/Ranking.html 에서 볼 수 있다. 한국 대표 최석환, 조승현, 윤지학, 이창수 군 모두 좋은 성적 받고 기쁜 마음으로 귀국할 수 있길 바란다. Day 1 문제 셋은 3개의 문제로 ..

링크: https://code.google.com/codejam/korea/ 구글 코드 잼은 다들 잘 알 것이다. 구글 코드잼 한국 대회가 2012년에 딱 한 번 열렸다.2013년도에도 열리길 기대했었지만, 내가 알 수 없는 이유로 열리질 않았다. 우연히 기회가 되어 Google Codejam Korea 2012에 참가했다.1년도 지난 일이라 당시 상황이 잘은 기억이 나질 않는다.예선 라운드는 그럭저럭 코딩이 빨리 되어 2등을 했었고,1차 본선 때는... 말렸었던 것으로 기억한다.여러 문제로 1차 본선은 무효처리 되고, 2차 본선이 열리게 되었다. 2차 본선 때는 그리 컨디션이 좋진 못했지만, C번 문제가 평소 즐겨 풀던 매칭 문제가 나와 무난하게 해결하여 패널티가 낮은 덕분에 결선에 진출할 수 있었다...

문제 설명은 매우 긴 반면에 문제는 매우 간단하게 풀 수 있다. 판도라(로봇)가 가리킬 수 있는 방향은 상,하,좌,우 뿐이다. 처음 시작 방향은 중요하지 않다. 문제 입력에서 R이 세 번 이상 반복하면, X,Y 축 모두에 대해 monotone하지 않게 된다.만약 R이 두 번 반복한 경우가 있다면, 판도라의 방향에 따라 X축이나 Y축 둘 중 하나가 monotone 하지 않게 된다. 이 두 조건을 알면 문제를 해결할 수 있다.한 가지 주의해야 할 점은 입력 Sequence가 R로 시작할 경우 Sequence 끝의 R과 연결이 될 수 있다는 점이다.