04.04 ~ 04.08 PS

하루 한 문제를 풀었다고 가정한 페이스 대비 3일 밀리긴 했지만 복구할 수 있지 않을까

 

3090. 차이를 최소로

쉬운 문제. 풀고 P4를 매겼나 그랬다.

값 증가도 가능한 줄 알고 잠시 동안 아무 접근을 못 하고 있었다.

 

CERC 2019

• 확실히 실력이 늘었다. 저번에 INC 2023 2인 팀연습에서 혼자 7문제 풀었는데, 이번에는 3인 팀연습에 준혁이가 껴있었는데 4문제를 풀었다. 패널티도 확실히 많이 줄었다. 맞힌 문제 중에 틀린 제출은 A에 한 번 밖에 없는데, 이건 영어 이슈였다.
• 문제 번호가 없는 문제지를 뽑아서 소통에 어려움이 있었다.
• A. ABB
  • 앞뒤 중 하나를 골라 거기에 원하는 문자열을 삽입할 수 있을 때, 삽입해야 하는 문자열의 최소 길이를 구하는 문제였다.
  • 팀노트에 있는 나랑 base가 다른 해싱 코드를 따라 적다가.. "이건 뭐 0.5-base냐?? 왜 작동을 안 해 ㅋㅋ"를 시전하며 그냥 지우고 혼자 새로 짰다.
  • 그러고 틀렸는데.. 아무래도 앞뒤 중 하나인지 뒤에만인지 표현이 굉장히 헷갈렸다. 그래서 누스에게 물어봤는데, 앞뒤 중 하나가 맞는 것 같다 그랬다. 그래서 준혁이한테 물어봤는데 당연히 뒤만이지 뭔 개소리야 이러길래 얼른 바꿔서 내봤고 AC가 나왔다.
  • 다시 봐도 왜 뒤만인지 모르겠다 ㅋㅋ 영어 너무 어려움..
• F. Zeldain Garden
  • 누스가 컴퓨터 앞에서 멍때리고 있길래 당황했다.
  • 누스에게 문제 설명을 듣고 준혁이에게 컴을 넘기고 그동안 식 정리를 해둔 뒤 바로 짜서 맞혔다.
  • '그냥 짜면 되겠지' 하고 앉으면 뭘 해야 될 지 모를 만 하다.
  • 준혁이가 아까부터 누스 옆에서 "제곱수 뺐어??"라고 말한걸 들어서, 맞힌 뒤에 그런거 필요없다고 말해줬다.
• D. Crimson Sexy Jalapeños
  
  • 준혁이가 전부터 인터랙티브만 나오면 눈 돌아가서 혼자 다 가져가고 그랬는데,
  • 하노이에서 크게 데여서 그런지 이제는 떠넘기는 눈치여서 받아 풀었다 ㅋㅋㅋ
  • 읽어보니, 독약 초콜릿 셀이 구분선 기준으로 양쪽에 존재하면 반드시 독약을 먹고 죽기 때문에..
  • 독약 초콜릿 셀들의 min, max - x, y들을 기준으로 묶은 뒤 더미 네 개 짜리 님게임을 구현하면 된다고 말하고, 어떤 더미를 취하는지는 최상위 비트랑 관련이 있었던 것 같은데 잘 기억이 나지 않으니 네 개 전부 돌려보면 된다고 말했다.
  • 준혁이한테 떠넘기고 다른 문제 보려 그랬는데, 준혁이도 뭐 짜고 있었고 뭔 말인지 잘 모르겠으니 니가짜라 reject를 받았다.
  • 풀이 나왔으니 냅두고 딴거 고민하다 컴 비었을 때 코딩해서 맞혔다.
• I. Ponk Warshall
  
  • 뭔가 이 문제에 관해 둘이서 소란스럽길래 확인하러 갔다.
  • 준혁이가 사이클을 짜두고 틀렸다는 것 같았다. 그리고 누스한테 문제를 들어보니 최소 스왑으로 문자열 만들기 뭐 이런거였다.
  • 그래서 누스는 자기는 인접한 케이스만 우선시하는 그리디가 먹히는 것 같다고 말했다.
  • 그래서 나는.. 그냥 하면 되는거 아니냐? 하고 몇 마디 해보니까 인접 스왑이 아니라 임의 스왑이라는 걸 확인했다. 늦지 않게 파악해서 다행이다. 아무튼,
  • 듣고 보니 사이클이 나올 법 했다. 누스는 그리디를 주장했는데, 근본적으로 두 풀이의 기반이 비슷해 보여서 준혁이의 풀이의 반례를 찾는게 더 나은 전략인 것 같다고 판단했다.
  • 근데 준혁이가 사이클의 개수를 세었다길래, 사이클을 어떻게 세냐에 따라 최적해가 달라지는거 아닌가 싶었고, 반례를 제시해 주었다.
  • 그때쯤에 이제, 준혁이가 뭐 사이클의 크기가 4 이하라서 그리디가 통할 수도 있는건데 뭐 이런 얘기를 했던 것 같았다. 그래서, 2-사이클, 3-사이클, 4-사이클 순서대로 도려내는 풀이를 냈고, 짜서 맞혔다.
  • N-사이클이 될 경우에는, 이 그리디가 성립 안 할 것 같다. 사실 case work를 통해 내 풀이도 검증했으면 좋았겠지만, 확실한 듯 싶었고, 이게 아니면 많이 풀릴 리가 없었을 것 같아서 그냥 했다.
• E. Deep800080
  
  • 기하폐기물은 당연히 내게로 왔다.
  • 열심히 짰으나 왜 틀렸는지 결국 알아내지 못했다.
  • 기하 연습도 해야 하는데, 기하 연습만 하면 PS에 현타 와서 PS 자체를 안 하게 되더라.
  • 즐겁게 기하 연습하는 법은 이 세상에 없는걸까?
• J. Saba1000kg
  • 막바지에 핑크퐁뭐시기 왔다갔다 하면서 슬쩍 봤다.
  • 문제는 아주 심플한데, 요약하면: $G=(V,E)$, 각 쿼리:vertex set $S$, $|V|, |E|, \sum |S| ≤ 10^5$가 주어질 때, 매 쿼리에 $\#$ of component in $G[S]$를 세면 된다.
  • 어렵다.. 나는 잘 몰라서 딥뭐시기 기하 궁시렁대면서 짜고 있었는데, 준혁이가 슥 보더니 루트질 기본이 골드고 유파 기본이 골드니까 골드네 골드 이러면서 누스한테 풀이를 알려줬고, 누스가 짜서 맞혔다.
  • 업솔빙할 때 루트질 생각을 해봤는데 잘 모르겠어서 슬라이드를 깠다.
  • 쿼리 셋의 총합 제한 $\sum |S| ≤ 10^5$ 같은게 있을때 종종 나오는 접근이다. 해볼 거 다 해본 뒤, 분할정복 안 먹히면 해봐야 하는게 루트질이다. $|S| ≤ B$일 경우 näive하게 돌리고, $|S|>B$인 경우는 적기 때문에 $O(V)$로 처리하기가 풀이이다.
  • 루트질 할 때는 웬만해서는 로그를 안 붙여야 통과하기 때문에 언오맵을 썼다.

 

28587. Bojanje stabla

아니 요즘에도 뭔 HLD 기본 문제가 나오고 이러냐 하면서, HLD는 내가 라이브로 못 짜니까 루트질을 연습해보자! 하고 루트질을 짰다.

실패~!

전에 루트질로 뚫었던 트리 문제가 1.5초에 돌았었는데.. 왜 안 돌지.. 좀 무거운가..

걍 HLD 복붙해서 맞혔다.

 

 

8158. Blockade

dfs tree를 그리고 조금 고민하니 small to large로 ordering이 높은 서브트리에서 ordering이 낮은 정점으로 가는 역간선?들을 관리해주면 될 것 같았다.

 

그러나.. 너무 많이 틀렸고 도움을 요청했다.

IBory님이 친히 반례를 만들어주셨는데, 선인장을 만들고, 새로 생겨도 답에 영향을 주지 않아야 하는 간선들을 추가/삭제 하면서 반례를 찾으신 듯 하다.

유파로 건너건너 연결되어야 하는 쌍이 잘 연결됐는가?를 헷갈리는 유파 문제에서 잘 고려해야 한다는 것을 다시금 깨달았다.

 

문제점을 고치고 맞힐 수는 있었으나... small to large를 짠 사람은 나 밖에 없었던 것 같다...

코드도 간단하던데.. 나 빼고 다 쉽게 하신건가..