2021년 1월 8일 PS 일지

다른 분들처럼 막 거창하게 쓸거 아니다.

나만의 방식으로, 매일 쓰는게 목표다.

 

레이지 연습문제 하나 풀려 그랬는데, 그러지 말고, 수업 시작 전에 (월,목) 풀 테스트 문제로 남겨두었다.

그날은 테스트 문제, PST, CosmoCraft를 푸는게 학습 목표.

 

오늘은 Codeforces Round #695 (Div. 2)에 참가할거다.

7분 뒤 시작!

끝나고 간단한 후기 남겨보겠다.

 

Codeforces Round #695 (Div. 2)

 

끝나고 Div2 치고는 어렵다는 평이 많았다.

Worst contest 이런 댓글도 있었는데 반응이 좀 과하다는 생각이 든다.

 

 

C를 잡다가  D로 넘어갔는데 이건 굉장히 좋은 선택이었다.

 

A는 그리디

B는 Brute Force

C는 Case Work

D는 dp + prefix sum

E는 Tree

 

이정도인데 A,B는 쉬웠다. B 구현하는데 오래 걸린게 아쉽고 C는 흠... 아직도 이런 Case Work에 많이 약하다는 생각이 든다. 보완해야겠다. D는 바로 풀어서 만족이 크다.

 

D를 첨언하자면 각 위치에 대해 위치가 포함되는 경로의 수를 세주면 된다.

dp[i][j]: a[i]를 길이 j 경로의 마지막 위치로 하는 경로의 수

로 정의하면 dp[i][j] = dp[i+1][j-1] + dp[i-1][j-1]이므로 dp를 쉽게 세줄  수 있다.

이를 이용해 i번째 위치를 포함하는 경로의 수를 세어 ans에 더해주면 된다.

 

코포 업솔빙할 문제들

Three Bags - COMPLETE

Distinctive Roots in a Tree - COMPLETE

이 문제는 요놈이랑 같다고 한다.

다이아 꿀~

E번 처음에 구현 잘못했는데 우연히 얻어걸려서 AC 떴다.

그 이유는,.. 0-based를 1-based로 착각했는데 0번 노드의 값이 N번 노드의 값으로 그대로 가버리는 바람에 개수 세는 문제이므로 AC가 뜬거였다. 백준 문제 풀면서 잘못된걸 깨닫고 고침.

 

지난번 코포 E

다음날 하려다가 그냥 하고 자기로 했다.

Strange Shuffle - COMPLETE

인터랙티브 문젠데 굉장히 좋은 문제라고 생각한다.

이런 시뮬레이션 문제는 직접 시뮬레이터 돌려서 작동하는 방법을 익혀야한다는 것을 깨달았다.