티스토리 뷰

ICPC/2014 전대프연

B. 말고스팟

전명우 2014. 8. 24. 16:43

한글 문제임에도 불구하고 문제를 이해하기가 다소 까다로운 편이다. 이 문제는 DP로 해결할 수 있다.


가능한 상황은 $2^N \times 2^M$ 가지가 있다. 이는 최대 $2^{40}$ 가지로 경우의 수가 꽤 많다. 가능한 경우를 줄이도록 생각해야한다. 현재 상황에서 문제별로 채점이 되었는지, 아직 채점이 되지 않았는지 경우는 총 $2^M$가지가 있다. 그 중 한 상황에서 여태까지 살아남은 사람은 필요충분으로 여태까지 채점된 문제들에 대해서 모두 Yes라고 대답한 사람이다. 따라서, 어떤 문제들을 채점했는지를 알면, 살아남은 사람 또한 알 수 있게 된다. 따라서, DP를 $2^M$ 가지 경우에 대해서 돌리면 된다.



댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함