[11월]

일본 문제들 덕분에 조금이나마 ps를 하고 사는 것 같다... 무슨 문제를 풀었는지 알아보자.

쉽지 않다. P2이고 OI 문제인데 꽤 시간이 오래 걸렸다. 3차원 뇌가 안 돌아가나보다. 예전에 stock prediction이라는 icpc 문제도 못 풀었는데, 3차원에 약하다. 아마 3차원 문제라면 스위핑을 사용할 것이라고 생각했기 때문에 오래 걸리지 않았나 싶다. 이 문제에 대해서 한 가지 더 말할 것이 있는데, 자료구조 근육으로도 풀린다. 나 역시 약간의 자료구조 근육으로 이상하게 돌아가서 풀었다. 역시 근육은 있으면 좋은 것 같다...

 

내가 출제한 문제인 HLD랑 같은 아이디어를 사용한다. 날먹했다.

 

쉽지 않다. 풀이 떠올리기는 나름 쉬운데, 구현을 조금 돌아가서 했기 때문에 TL이 좀 빡빡했다. 직사각형 스위핑을 해야 했는데, 너비와 높이가 모두 같아서 투포인터적 성질을 사용하면 구현이 쉬워진다.

정말 재미있는 문제이다. 이틀인가 고민했는데, 너무 안 풀려서 풀이를 깔 뻔했다. 단조성과 같은 관찰이 얼마나 강력한지 보여주는 문제이다. 여담으로, 정풀과 다르게 푼 것 같다. 언젠가 업솔빙을 해야 될텐데 몰루...

센트디컴 기본문제이다. 하지만 나는 dynamic diameter에서 배운 트릭으로 센트디컴을 짜지 않고 풀었다.

처음으로 아레나를 돌았다. 가운데 보면 H번 문제에서 말렸는데, 지문을 잘못 읽었다. 지문 질문했는데 친절하게 답변해줘서 너무 고마웠다... 암튼 올솔! Mexchange 문제가 재미있었다. 양손정렬, 우정은 bfs처럼 사랑은 dfs처럼은 좋은 교육적인 문제이다.

solved.ac에서 만든 JOISC 스터디 그룹에서 JOI 스터디를 했다. 그림에는 안 보이지만 M도 풀었다. 덕분에 스위핑 문제만 3개 풀었다.

Territory는 생긴 것과 다르게 2차원 평면에서 영역 여러 개를 스위핑하는 문제가 아니다. 재미있게 풀었다.

Snake escaping은 정말 색다른 문제다. bit dp 문제임에도 시간복잡도가 예상이 가지 않는다. 그래도 council 풀면서 bit dp에 대해서 고민을 조금 해놓았어서 풀 수 있었던 것 같다.

Fire은 2가지 풀이가 있는데, 렉처럼 격자를 고정하고 위에 그림을 그려서 푸는 방법이 있고, 스위핑을 하면서 각 위치가 나타내는 영역의 시작과 끝을 관리하는 방법이 있다. 둘 다 재미있는 풀이이다.

Cutting은 그냥 하면 된다. 내 풀이는 다3인 것 같은데 다른 풀이를 들어보면 루비5가 납득이 가기도 하고 잘 모르겠다.

 

이렇게 보니까 일본산 자료구조 문제만 풀었다. 이제 usaco 시즌인데 usaco 문제도 풀 준비 해야겠다.