합성함수와 쿼리

Problem link: https://www.acmicpc.net/problem/17435

Bounded Knapsack 문제를 log-step DP를 통해 0-1 Knapsack으로 풀어주는 아이디어를 활용하면 된다.

아래는 문제를 풀었던 사고의 흐름을 날 것 그대로 정리한 것이다.

• 각 쿼리를 O(n)으로 곧이 곧대로 구해주면 당연히 TLE가 난다.
• 따라서, DP를 활용해서 풀어주면 좋은데 단순하게 풀자니 Problem space의 크기가 너무 커진다(N * M).
• 그럼 Top-down DP를 써볼까 생각해볼 수 있지만,
  • 어차피 답을 저장하기 위한 CACHE 배열만으로 메모리 초과가 나고,
  • 쿼리가 어떻게 주어질지 모르기 때문에 실제로 풀어야할 부분문제의 수가 적으리라는 예상도 할 수 없다.
• 그런데 문제를 잘 살펴보면, 아래의 성질이 만족한다.
  • F_n(x) = F_a(F_b(x)), where a + b = n
• "아! 그럼 n을 수들의 합으로 잘 표현해주는 방법을 찾으면 되겠구나!"
• n의 최대 값은 500000이므로, 2^0, 2^1, ..., 2^18, 총 19개의 수를 활용하면 범위 내의 어떤 n이건 유일하게 표현해줄 수 있다(2진법).
• 따라서, CACHE를 아래와 같이 정의한다.
  • CACHE[i][x]: F_2^i(x)
• 점화식은 아래와 같다.
  • CACHE[i+1][x] = CACHE[i][CACHE[i][x]]
• 위의 점화식을 활용하여 Top-down DP로 문제를 풀어놓은 뒤,
  • 각 쿼리에 대해서 이를 2의 누승들의 합으로 분해하고, 합성을 진행해주면 된다.

#include <cstdio>

using namespace std;

const int kMaxM = 200000;
const int kMaxN = 500000;
const int kMaxExp = 18;  // 2^19 -1 > 500000

int CACHE[kMaxExp + 1][kMaxM + 1];

int M;
int Q;

int Solve(const int n, const int x)
{
  int ret = x;
  for (int bitpos = 0; bitpos <= kMaxExp; ++bitpos)
  {
    if (n & (1 << bitpos))
    {
      ret = CACHE[bitpos][ret];
    }
  }

  return ret;
}

int main(void)
{
  // Read inputs
  scanf(" %d", &M);
  for (int it = 1; it <= M; ++it)
  {
    scanf(" %d", &CACHE[0][it]);
  }

  // DP
  for (int e = 1; e <= kMaxExp; ++e)
  {
    for (int x = 1; x <= kMaxM; ++x)
    {
      CACHE[e][x] = CACHE[e - 1][CACHE[e - 1][x]];
    }
  }

  // Process queries
  scanf(" %d", &Q);
  for (int it = 0; it < Q; ++it)
  {
    int n, x;
    scanf(" %d %d", &n, &x);
    printf("%d\n", Solve(n, x));
  }

  return 0;
}