[1, 2, 3월]

군대에 간 덕분에 시간이 남아돌았다. 남는 모든 시간을 ps에 쏟아부었더니 루비 5와 다이아 1을 엄청 풀게 되었다. 푼 문제도 많으니 기억나는 문제들만 간략하게 정리해보자.

아직 코딩을 한 문제도 안 했다.

경찰과 도둑은 SCPC 2022 2번에서 했던 이분탐색을 비슷하게 트리에서 하면 되는 것 같은데 D2가 박혔다. 들려오는 소문으로는 구현이 어려워서 그렇다고 하더라.

과일 게임의 토픽은 이미 usaco에서 99번 우려져서 난이도를 보기 전에는 쉬운 문제일 줄 알았는데 생각보다 안 풀려서 쩔쩔맸다.

평균 최대화는 적당한 비빔밥인 것 같다. 아직 코딩을 안해서 내 풀이가 맞는지 잘 모르겠다.

뚫기는 timeismoney와 같은 아이디어로 접근하면 쉽게 풀렸다. 몇몇 루비들은 풀이를 까는 것이 도움되는 것 같다.

하나 둘 셋은 이미 스포를 많이 들었기 때문에 풀어도 푼 느낌이 안 났다.

아이싱은 hld에 sweeping을 열심히 비벼서 풀었는데 까보니까 랜덤 풀이도 있었다. 랜덤 풀이를 보면 허탈하긴 하지만 그래도 난이도가 어려운 것은 맞는 것 같다.

지름길은 푼 건지 모르겠다. 적당히 풀다가 다른 문제로 넘어갔다. 할 것 없으면 다시 올 예정.

코딩 테스트 65점이 내가 낸 merging branches와 똑같았다! 이래서 평소에 문제 열심히 읽고 다녀야 한다.

코딩 테스트는 컨벡스 헐로 재미있게 노는 문제로, 수구구구쿼(경곽 22 송년 문제) 혹은 까마귀를 풀어봤으면 적당히 풀만하다고 생각한다. 물론 아직 안 짜서 시간 내에 로그제곱이 돌지는 모른다.

회의실 2는 재미있는 앳코더 맛 문제이었다. festival in joi kingdom 2와 비슷한 맛이다. 재미있다.

옛날에 참가한 대회 업솔빙을 했다. Counting rectangles는 다항식의 사용이 얼마나 강력한지 보여주는 문제이다. 한참을 고민했는데 답이 정말 간단하다.

Strange Graph는 MST 구하는 문제이다. MST 구하는 문제들은 대체로 그래프를 잘 관찰하고 크루스칼을 박으면 풀리는데 이 문제는 그렇게 쉽게 풀리지 않았다. 크루스칼을 프림처럼 쓰니까 풀리는 것 같다. 재미있었다.

(+) 사실 사풀이었다. 보르부카? 같은 것을 쓰더라. small to large랑 bound를 사용하고 싶었으나 실패해버렸다.

Seats가 정말 재미있었다. 서브태스크 아니었으면 못 풀 뻔

Islands는 거의 다 푼 것 같은 상태가 오래 지속되고 못 풀었다. 그래프 문제 넘 어렵다.

Longest trip은 정말 힘들게 풀었다. 쿼리 개수 1.5n+2logn의 랜덤 풀이를 만들고 끙끙댔다. 별의별 짓을 다했지만 정풀은 깔끔하다.

Soccer은 재미있는 dp 문제이다. 아직 안 봤다면 꼭 풀어보자.

Parks는 아이디어가 뭔지 모르겠다. 나는 정말 열심히 풀었지만 실패!

아인타님의 문제가 맛있는 애드혹인 경우가 많다. 신탁, comparing plants, 하나 둘 셋, 점 연결하기, 섬 모두 재미있다!

사진에서 잘렸지만 jealous teachers는 신기한 그래프 문제이다. 저런 문제는 어떻게 만드는지 모르겠다.

구사과님의 문제는 자구맛이 강하다. MST and Rectangles 푸는데 오래 걸렸다. 첨에 이게 왜 되나 싶기도 했다.

Minimum Diameter Spanning Tree는 단 하나의 아이디어만 있으면 되는데 그것을 찾기 어려운 그래프 문제이다. 재미있다.

Wind of Change는 센트 비비면 되는 것 같은데 맞는지 모르겠다.

애드혹은 맛있다. 그래프는 더 맛있다.

군대 가고 D2~R5가 잘 풀려서 기분이 좋다. 앞으로도 꾸준히 어려운 문제들을 잘 풀 수 있으면 좋겠다.

azber의 블로그