본문 바로가기 메뉴 바로가기

PS 이야기

프로필사진
  • 글쓰기
  • 관리
  • 태그
  • 방명록
  • RSS

PS 이야기

검색하기 폼
  • 분류 전체보기 (141)
    • 문제 (1)
    • 해법 (18)
    • IOI (42)
      • IOI2011 (6)
      • IOI2012 (5)
      • IOI2013 (7)
      • IOI2014 (8)
      • IOI2015 (3)
      • IOI2016 (2)
      • IOI2017 (3)
      • IOI2018 (2)
      • IOI2019 (0)
      • IOI2020 (6)
    • ICPC (52)
      • 2012 대전 (3)
      • 2013 인터넷예선 (11)
      • 2014 전대프연 (1)
      • 2014 인터넷예선 (10)
      • 2014 대전 (11)
      • 2015 이후 한국대회 (6)
      • 해외리저널 (6)
      • World Finals (4)
    • Codejam (2)
      • Korea 2012 (1)
    • 우분투&서버 (0)
    • 공부 (24)
    • 잡담 (2)
  • 방명록

ICPC/2014 전대프연 (1)
B. 말고스팟

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

ICPC/2014 전대프연 2014. 8. 24. 16:43
이전 1 다음
이전 다음
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG
  • ioi
  • Algorithm
  • Greedy Method
  • moore
  • Segment tree
  • Tree
  • Dijkstra
  • Splay Tree
  • HackerRank
  • USACO
  • BOI 2009
  • BOI 2001
  • TRIE
  • Knuth Optimization
  • Dynamic Pramming
  • IOI2011
  • Boyer
  • IOI2012
  • Parametric Search
  • idea
  • optimization
  • IOI2014
  • Divide & Conquer
  • IOI2013
  • majority
  • BOI
  • dynamic programming
  • z-trening
  • vote
  • Boyer-Moore Majority Vote Algorithm
more
«   2025/05   »
일 월 화 수 목 금 토
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
글 보관함

Blog is powered by Tistory / Designed by Tistory

티스토리툴바