7월 4-5주차 Weekly PS

• Recent Updates
• Rounds
  • (Testing) Codeforces Global Round 15
• Problems
  • BOJ 1766 문제집
  • POI 1994 Ones and Zeros (BOJ 8111 0과 1)
  • BOJ 1602 도망자 원숭이
  • ICPC Germany Regional (GCPC) 2010 D Field Plan (BOJ 3977 축구 전술)
  • BOJ 4196 도미노
  • ICPC Jakarta Regional 2018 Boomerangs (BOJ 16583)

July 19 - July 28, 2021

이 글에 구현코드 링크가 없더라도 PS 레포 링크 에 가서 대회 단위로 들어가면 보통 올려놓은 코드를 볼 수 있습니다.

7월 마지막 주는 일반생물학 시험을 비롯, 몇가지 할일이 있어서 PS를 거의 못할듯 합니다 :(

읽는 사람이 문제를 읽고 조금 생각해봤다고 가정하고, 대략적인 아이디어만 간단히 적을 생각입니다 ㅎㅎ

Recent Updates

• 어리석은 실수로 UCPC에 참가하지 못하게 되었습니다.
• 뭔가 SCPC 2차 준비는 마땅히 할수있는게 없고 해서… 순수하게 재밌는 공부를 하려고 노력 중입니다.
• ICPC 철이 되면 팀원들과 함께 또 재밌게 할수있을듯 합니다. 팀연습이 제일 재밌는거 같아요
• 올해 PS 성과는 코드잼 R3 간걸로 마무리하게 될듯…

Rounds

(Testing) Codeforces Global Round 15

• Global Round 15에 테스터로 참여했습니다.
• 제가 테스팅했을때랑 비교하면, B번 문제가 새로 생겼고, 원래의 B번이 D번으로 이동했습니다. 테스팅했을때도 B (지금의 D) 가 너무 어려운거 같다는 생각은 들었었습니다.

Problems

그래프 연습.

BOJ 1766 문제집

• 난이도 Gold 2
• 사용하는 알고리즘들에 대한 이해만 명확하면 쉽습니다.
• BFS로 노드들을 위상 정렬하는 방법을 따르되
• queue 대신 항상 가능한 쉬운 문제를 풀라는 조건이 있으므로 BFS에서 Queue 대신 Priority Queue를 쓰면 됩니다.

POI 1994 Ones and Zeros (BOJ 8111 0과 1)

• 난이도 Platinum 5
• 어떤 수의 뒤에 0과 1을 이어서 다음 수를 만들 수 있습니다. 이를 0부터 $N-1$까지의 노드가 있다고 생각하면 나머지가 $r$에 서, $10r$ 또는 $10r + 1$ 로 노드가 이어져 있음을 관찰합니다.
• 이제 1에서 BFS를 통해 노드들을 방문하면서, 0이 100-step 이내에 방문 가능한지 확인하면 됩니다.

BOJ 1602 도망자 원숭이

• 난이도 Platinum 5
• 노드 가중치는 합이 아니라, 경로 상의 가중치의 max만 한 번 더합니다.
• 이 문제를 해결하는 방법은, 그냥 노드 순서대로 ‘중간 노드’ 를 쓰는 F-W와는 달리 노드 가중치가 작은 것부터 중간 노드로 써서 업데이트하는 것입니다.
• 이렇게 하면, 새로운 노드를 쓰는 경우 항상 노드가중치는 새 노드의 것을 따라가게 되므로, 비교적 쉽게 해결할 수 있습니다.

ICPC Germany Regional (GCPC) 2010 D Field Plan (BOJ 3977 축구 전술)

• 난이도 Platinum 4
• 그래프를 SCC로 묶어서 생각합니다. 같은 SCC에 있는 정점끼리는 언제든 서로 오갈 수 있기 떄문입니다.
• 이제, indegree가 0인 SCC를 찾아서, 그 SCC로부터 출발하면 됩니다.
• 단, indegree가 0인 SCC가 여러개이면 이 두개를 서로 오갈수가 없어서, 불가능합니다.
• SCC 구현은 Tarjan 아니면 Kosaraju인데, Tarjan이 구현할게 적고 좀더 빠릅니다. Kosaraju는 최소 2번 이상의 DFS를 돌아야 하기 때문입니다.
• 별개로 저는 예전에 짜놓은 Kosaraju를 대충 박아넣었습니다.

BOJ 4196 도미노

• 난이도 Platinum 4
• 마찬가지로, SCC를 묶은 다음 indegree가 0인 SCC를 찾는 문제입니다. 위 문제와 거의 똑같습니다.
• 다만 이번엔 불가능한 경우가 아니라, indegree가 0인 모든 SCC를 직접 넘어트리면 됩니다.

ICPC Jakarta Regional 2018 Boomerangs (BOJ 16583)

• 난이도 Platinum 2
• 먼저, 트리에 대해 문제를 풀어 봅시다. 어떤 노드의 child가 짝수개라면, 짝수개의 자식노드들과 현재 노드를 부메랑으로 서로 이어주면 됩니다.
• 홀수개라면, 방금전처럼 잇고, 이어지지 않은 하나의 노드와 현재 노드, 현재 노드의 부모 노드를 부메랑으로 이어주면 됩니다.
• 이때, 부모 노드에게 현재 노드는 이미 사용되었으므로 부모 노드의 자식노드를 잇는 과정에 참여하면 안 된다는 사실을 report해야 합니다.
• 이렇게 하면, 트리를 DFS 순서로 돌면서 모든 간선을 (간선이 홀수개면 1개 빼고) 부메랑에 참여시킬 수 있습니다.
• 따라서, 트리에 대해서는 문제를 해결하였습니다. 이를 일반화해서 임의 그래프에 대해 해결해 보겠습니다.
• 우리는 정점이 중요하지 않고, 간선만 중요하므로, 그래프를 강제로 트리처럼 펴면 됩니다. 이 방법은, 사이클을 이루기 시작하는 간선을 만나면 그 간선의 끝에 새로운 정점을 만들어서, 사이클을 이루지 못하게 막으면 됩니다. 이때 새로운 정점은 나중에 부메랑을 만들 때 다시 원래 정점으로 돌려줘야 하기에, 이 사실을 기억해야 합니다.
• 말은 복잡하지만, 코드는 굉장히 깔끔하게 나옵니다. build_tree(r, p) 함수를 보면 됩니다.
• 전체 과정을 DFS 2번으로 해결할 수 있습니다. 두번째 BFS인 build_boo(r, p) 에서, child node 들 중 이미 사용한 노드를 표현하는 등 디테일은 조금 주의해야겠습니다.