2024 KOI 1차 풀이

알고리즘 공부도 할 겸, 대회 때 접했던 문제를 다시 풀어보려 합니다.

대회 때는 40분동안 200점 맞고 1시간동안 삽질만 했습니다.

1. 반품 회수 (Silver 1)

그냥 끝까지 쭉 가서 돌아오는 길에 아직 안 오면 대기타다가 갖고 가면 될 것 같이 생겼습니다.

바로 구현해서 100점을 맞고 시작했습니다.

#include <iostream>

using namespace std;
typedef long long int LL;

LL d[3001], t[3001];

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n;
  cin >> n;

  for(int i=1;i<=n;i++) cin >> d[i];
  for(int i=1;i<=n;i++) cin >> t[i];

  LL res = 2 * d[n];
  for(int i=1;i<=n;i++) res = max(res, max(2 * d[n] - d[i], t[i]) + d[i]);
  cout << res;
}

 

2. 이진 트리 (Platinum 5)

일단 문제만 한 3번은 읽은 것 같습니다. 솔직히 아직도 문제 설명하라 하면 못합니다.

대충 그림을 그려서 생각해보면, 두 트리가 결합하며 다음과 같은 정보가 필요함을 알 수 있습니다.

일단 트리가 나누어지기 때문에 새로 추가되는 값들에 대해서 개수가 줄어드는 일은

모든 구간이 커버되는 경우 빼면 존재하지 않습니다. 따라서 따로따로 계산해도 무방합니다.

 

왼쪽 노드에서 오른쪽부터 시작되는 구간에 대해서,

오른쪽 노드에서 왼쪽부터 시작되는 구간이 총 N개로 독립적으로 대응된다 생각하면,

구간은 총 N개가 필요함을 알 수 있습니다.

 

이를 일반화하면 새로 추가되는 구간의 합은 (왼쪽 노드의 오른쪽부터 시작되는 구간들의 합) × (오른쪽 노드의 구간 길이) + (오른쪽 노드의 왼쪽부터 시작되는 구간들의 합) × (왼쪽 노드의 구간 길이) 가 됩니다.

이때 모든 구간을 커버하는 경우 1개의 노드로 색칠할 수 있으며, 위의 계산에서는 1 + 1 = 2로 계산되었으므로 1을 빼줍니다.

 

금광 세그를 풀어봤다면 비교적 점화식을 떠올리기 쉬웠을 것으로 예상됩니다.

#include <iostream>

using namespace std;
typedef long long int LL;

const LL mod = 1e9+7;

LL dp[100001];
LL Lsum[100001], Rsum[100001], sz[100001];

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n;
  cin >> n;

  Lsum[0] = 1; Rsum[0] = 1; sz[0] = 1; dp[0] = 1;

  for(int i=1;i<=n;i++)
  {
    int p, q;
    cin >> p >> q;

    Lsum[i] = (Lsum[p] + sz[q] + Lsum[q] - 1) % mod;
    Rsum[i] = (Rsum[q] + sz[p] + Rsum[p] - 1) % mod;
    sz[i] = (sz[p] + sz[q]) % mod;
    dp[i] = (dp[p] + dp[q] + Rsum[p] * sz[q] + Lsum[q] * sz[p] - 1) % mod;
    cout << dp[i] << '\n';
  }
}

 

3. 오름차순 (Diamond 5)

대회 때 12점 긁고 못 풀었던 문제입니다.

끝나고 레이지 오프쿼리 어쩌고 얘기 나왔는데, 모범 답안 보니 스택이더라고요.

 

일단 필요한 가장 작은 시프트 값을 기록해 줍시다.

log함수를 사용해도 되고, 어차피 범위가 그닥 크지 않으므로 O(NlogN)으로 구현해도 됩니다.

당연하지만 진짜 나이브하게 구현하면 시간복잡도가 사실상 O(N³)까지도 갑니다.

 

간단히 작은 테스트케이스를 고려해 봅시다.

여기서 d[i]를 다음 값을 오름차순으로 만들기 위해 필요한 값이라 정의해 봅시다.

arr[L+1]을 오름차순으로 만들기 위해 d[L]만큼 끌어올린다면,

arr[L+2]을 오름차순으로 만들기 위해서는 d[L+1]에 더해 앞에서 끌어올린 d[L]만큼 추가로 더 끌어올려주어야 합니다.

 

이를 일반화하면, 모든 배열에 연산이 필요한 어떠한 구간 [L, R]에 대해서 오름차순으로 만들기 위해 필요한 비용은

(R-L)d[L] + (R-L-1)d[L+1] + (R-L-2)d[L+2] + .... + (R-R+2)d[R-2] + (R-R+1)d[R-1] 이 됩니다.

대회 때는 여기서 줄일 방법을 못 찾아서 더 이상 진전이 없었는데, 신기한 누적합으로 계산하더라고요.

isum[i] = 1 × d[1] + 2 × d[2] + ... + i × d[i] 꼴로 누적합을 정의해준 후,

일반적인 d에 대한 누적합과 어떻게 잘 조합해서 저런 꼴을 O(1)에 계산할 수 있습니다.

 

이제 다음과 같이, 굳이 이전 경우에 맞추어 내리지 않아도 되는 경우를 생각해 봅시다.

아무튼 충분함

이때 역연산 (2로 나누는 것)은 불가능하므로 저렇게 이미 충분하다면 그냥 넘어가서 마저 계산해주면 됩니다.

수식으로 표현하면, 인덱스 L과 R에 대해 (d[l] + d[l+1] + d[l+2] + ... + d[R-1]) < 0이면

구간을 [L, R - 1]까지만 고려한 후, R부터 추가로 시작하면 된다는 것입니다.

 

누적합을 활용해 주어야 하므로, sum[i] = d[1] + d[2] + ... + d[i]라 하면

sum[L-1] > sum[R-1]로 정리해줄 수 있습니다.

 

이제 단조 스택을 활용하여 구간을 분리해 줍시다.

어떤 지점 i에 대해서, 다음으로 넘어갈 구간을 nxt[i]라 합시다.

이제 인덱스에 유의해서, 구현해주면 답을 얻을 수 있습니다.

#include <iostream>
#include <stack>

using namespace std;
typedef long long int LL;

LL arr[250001], d[250001];
LL sum[250001], isum[250001];
int nxt[250001];

stack<LL> st;

LL cost(LL l, LL r) //구간[l, r]: (r-l)d[l] + (r-l-1)d[l+1] + ... + (r-r+1)d[r-1]
{
  if(l >= r) return 0;
  return r * (sum[r - 1] - sum[l - 1]) - (isum[r - 1] - isum[l - 1]);
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n, Q;
  cin >> n >> Q;
  for(int i=1;i<=n;i++) cin >> arr[i];

  for(LL i=1;i<n;i++)
    {
      LL cur = arr[i+1];
      while(arr[i] > cur) cur *= 2, d[i]++;
      while(arr[i] <= cur / 2) cur /= 2, d[i]--;
      sum[i] = sum[i-1] + d[i];
      isum[i] = isum[i-1] + i * d[i];
    }
  nxt[n + 1] = n + 1;
  for(int l = n; l > 0; l--)
    {
      while(!st.empty() && sum[st.top() - 1] >= sum[l - 1]) st.pop();
      if(!st.empty()) nxt[l] = st.top();
      else nxt[l] = n + 1;
      st.push(l);
    }
  while(Q--)
    {
      int l, r;
      LL res = 0;
      cin >> l >> r;
      while(nxt[l] <= r)
        {
          res += cost(l, nxt[l] - 1);
          l = nxt[l];
        }
      res += cost(l, r);
      cout << res << '\n';
    }
}

 

소감

어떻게 시험 다음다음날이 본선ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

그냥 참가에 의의를 두겠습니다