최근 푼 문제 어려운 것들 정리

https://atcoder.jp/contests/abc278/tasks/abc278_g

game 문제

누가 봐도 그런디를 쓰면 될 것 같다.

실제로 정해도 그런디 + 최적화 풀이를 언급. 하지만 실상은 애드혹 문제.
후공이 선공의 선택을 따라 할 수 있다는 것이 중요 포인트.

 

https://codeforces.com/contest/1747/problem/E

그냥 dp 문제인데 중요한 점은 1차원에서 움직이는 걸 잘 합쳐서 2차원짜리 정답을 구하자.

 

https://www.acmicpc.net/problem/22023

미친 문제. 최대 최소가 특정 값을 넘어가는 구간을 잘 찾으면 문제가 해결된다. 갓 문제.

 

https://www.acmicpc.net/problem/25442

미친 문제2. 이분 탐색하는 거까지는 쉬운데, 최적화가 중요. 정확히 말하면, 보통 이분탐색과정에서 O(nlogn)이 보장되므로 대충 구현하는데, 이런 interactive 문제는 쿼리의 개수를 줄이는 최적화가 중요할 수 있음. 이전 이분탐색 결과를 이용해서 해결. 단, 99.89점 이후로는 약간의 휴리스틱 필요. (나는 mid 값 parity에 따라 반복문 순서를 뒤집음)

 

https://www.acmicpc.net/problem/24261

S-T에 대해서 생각하면 놀랍게도 비둘기집이 됨.

굳 문제.

 

https://www.acmicpc.net/problem/20370

ioi pracitce의 jelly falvor과 같은 논리라 생각됨.

비슷한 문제로 neo robin hood도 있음

 

https://www.acmicpc.net/problem/16901

웰 노운 문제인데 최근에 풀이 떠올라서 풀었다.

근데 다4 됐길래 다5로 기여함. (내가 푼 건 다4이상일리 없다)

밑에 2개는 내가 풀었고 나머지는 풀이 봤다.
어려운건 잘 못 풀겠어 ㅠㅠ