25.07.03 PS

6월은 PS를 안 했다.

 

BOJ 24617. Redistributing Gifts(#) [추천!]

대타로 쓸 수 있는 그래프를, 각 row마다 만들어주고, 각 row마다 만든 그래프로 dfs를 돌려준다.

SCC 또는 플로이드워셜 또는 이분매칭을 이용한 풀이도 있다는 것 같다. 신기하네..

 

ARC 138. Differ by K bits(#) [추천!]

• K=1은 간단하다. 그레이 코드다.
• K: 짝수는 불가능하다. 이분되기 때문.
• 손으로 열심히 풀어보면 K: N 미만의 홀수일 경우 항상 될 것이라는 추측을 할 수 있다.
• K=N-1은 가능하다. 짝수번째 원소들만 negative를 취하면 된다.

 

이러고서 결국 K: 홀수일 때 일반적인 방법은 찾지 못했다.

귀납적으로 간단하게 $(n,k)\leftarrow (n-1,k)$식으로 construct 할 수 없을까만 고민했는데,

edit distance라면 XOR이 중요하기 때문에 XOR을 들고 열심히 construct를 했어야 한다. 기억해두자.

이 문제에서는 XOR의 자기소거성질과 difference 관찰이 가능하기 때문에 이점이 있는 것 같다.

 

정해 코드를 보니, basis는 가우스 소거법 따위를 이용할 필요 없이 간단히,

\begin{bmatrix}
0 & 1 & 1 & 1 & 0 \\
1 & 0 & 1 & 1 & 0 \\
1 & 1 & 1 & 0 & 0 \\
1 & 1 & 0 & 1 & 0 \\
1 & 1 & 0 & 0 & 1 \\
\end{bmatrix}

이런 식으로 채워주면 linearly independent하게 구할 수 있다는 것 같다.

 

다른 분들 코드를 읽다보니, koosaga님은 그냥 능지 $(n,k)\leftarrow (n-1,k)$ 컨스트럭션을 하여 푸신 것 같아서 확인해 봤는데, 할 접근 다 해 놓고서 못 풀었다.

 

$(n-1,k)$에 있던거 들고서 gray code처럼 앞에 1 붙이고 순서 거꾸로 해서 이어붙이면 이음새가 안 맞물린다. 이걸 맨 뒤에 $k-1$개만 전체 flip하면 되는거다. 하아.. 이음새를 고칠 생각을 안 하고 그냥 깔끔하게 만들어보려다가 못 찾았다. 슬프다.

 

코드는 따로 짜지 않겠다. 오늘은 여기까지.