[ day 10 ] 계단 카드 뽑기

계단 카드 뽑기

• 시간 제한 : 5초

카드 주머니 N개가 차례로 있다.
이 중 i번째 카드 주머니에는 1이 적힌 카드, 2가 적힌 카드, ..., Ai​가 적힌 카드까지 총 Ai​장의 카드가 들어있다.
엘리스 토끼는 연속된 K개의 카드 주머니를 고르고, 각 카드 주머니에서 카드를 한 장씩 고른다.
이때, 엘리스 토끼가 고른 K장의 카드들에 1이 적힌 카드, 2가 적힌 카드, ..., K가 적힌 카드가 모두 하나씩 순서 상관없이 포함되어 있어야 한다.
엘리스 토끼가 이와 같이 카드를 고르는 방법이 존재하도록 하는 가장 큰 K의 값을 구해보자.

---

10일차에는 이론 영상이 제공되지 않습니다.

 

지시사항

입력

• 첫째 줄에 카드 주머니의 수 N이 주어진다.
  
  1≤N≤50000
• 둘째 줄에 Ai​들이 공백으로 구분되어 주어진다.
  
  1≤Ai​≤50000

출력

• 엘리스 토끼가 선택할 수 있는 가장 큰 K의 값을 출력한다.

입력 예시

5
1 1 2 5 3

출력 예시

4

• 2번째 주머니부터 5번째 주머니까지 연속으로 선택하면 1부터 4까지의 카드를 얻을 수 있습니다.

정답 코드 

 

C++

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double dl;
typedef pair<dl, dl> pdi;
typedef pair<ll, ll> pii;
typedef pair<ll, pii> piii;

#define ff first
#define ss second
#define eb emplace_back
#define ep emplace
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) lower_bound(all(v), x) - v.begin()
// cout<<fixed;
// cout.precision(12);

struct poi {
  ll val, xx, yy;
};

vector<ll> x;
ll n, m;
ll mod = 998244353;
string s;
string t;
ll arr[1010101];
vector<ll> v[1010101];
pii tree[4010101];
void lz(ll s, ll e, ll nod) {
  if (tree[nod].ss) {
    if (s != e) {
      tree[nod * 2].ss += tree[nod].ss;
      tree[nod * 2 + 1].ss += tree[nod].ss;
    }
    tree[nod].ff += tree[nod].ss;
    tree[nod].ss = 0;
  }
}

ll upt(ll l, ll r, ll val, ll s, ll e, ll nod) {
  lz(s, e, nod);
  if (r < s || e < l)
    return tree[nod].ff;
  if (l <= s && e <= r) {
    tree[nod].ss += val;
    lz(s, e, nod);
    return tree[nod].ff;
  }
  ll m = (s + e) / 2;
  return tree[nod].ff = min(upt(l, r, val, s, m, nod * 2),
                            upt(l, r, val, m + 1, e, nod * 2 + 1));
}

ll sol(ll l, ll r, ll s, ll e, ll nod) {
  lz(s, e, nod);
  if (r < s || e < l)
    return 0;
  if (l <= s && e <= r) {
    return tree[nod].ff;
  }
  ll m = (s + e) / 2;
  return min(sol(l, r, s, m, nod * 2), sol(l, r, m + 1, e, nod * 2 + 1));
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  ll a, b, c, d, i, j, k, p, q;
  cin >> n;
  for (i = 1; i <= n; i++)
    cin >> arr[i];
  ll ans = 0;
  ll lo = 0, hi = n + 1;
  while (lo < hi) {
    ll mid = (lo + hi) / 2;
    for (i = 1; i <= 4 * n; i++)
      tree[i].ff = tree[i].ss = 0;
    for (i = 1; i <= mid; i++)
      upt(i, i, i - mid - 1, 1, mid, 1);
    ll fl = 0;
    for (i = 1; i < mid; i++)
      upt(1, arr[i], 1, 1, mid, 1);
    for (i = mid; i <= n; i++) {
      ll x = i - mid + 1;
      upt(1, arr[i], 1, 1, mid, 1);
      ll val = sol(1, mid, 1, mid, 1);
      if (val >= 0)
        fl = 1;
      // cout<<mid<<' '<<i<<' '<<val<<'\n';
      upt(1, arr[x], -1, 1, mid, 1);
    }
    if (fl) {
      ans = max(ans, mid);
      lo = mid + 1;
    } else
      hi = mid;
  }
  cout << ans;
}

 

Python

def main():

    import typing

    def _ceil_pow2(n: int) -> int:
        x = 0
        while (1 << x) < n:
            x += 1

        return x

    class SegTree:
        def __init__(self,
                    op: typing.Callable[[typing.Any, typing.Any], typing.Any],
                    e: typing.Any,
                    v: typing.Union[int, typing.List[typing.Any]]) -> None:
            self._op = op
            self._e = e

            if isinstance(v, int):
                v = [e] * v

            self._n = len(v)
            self._log = _ceil_pow2(self._n)
            self._size = 1 << self._log
            self._d = [e] * (2 * self._size)

            for i in range(self._n):
                self._d[self._size + i] = v[i]
            for i in range(self._size - 1, 0, -1):
                self._update(i)

        def set(self, p: int, x: typing.Any) -> None:
            assert 0 <= p < self._n

            p += self._size
            self._d[p] = x
            for i in range(1, self._log + 1):
                self._update(p >> i)

        def get(self, p: int) -> typing.Any:
            assert 0 <= p < self._n

            return self._d[p + self._size]

        def prod(self, left: int, right: int) -> typing.Any:
            assert 0 <= left <= right <= self._n
            sml = self._e
            smr = self._e
            left += self._size
            right += self._size

            while left < right:
                if left & 1:
                    sml = self._op(sml, self._d[left])
                    left += 1
                if right & 1:
                    right -= 1
                    smr = self._op(self._d[right], smr)
                left >>= 1
                right >>= 1

            return self._op(sml, smr)

        def all_prod(self) -> typing.Any:
            return self._d[1]

        def max_right(self, left: int,
                    f: typing.Callable[[typing.Any], bool]) -> int:
            assert 0 <= left <= self._n
            assert f(self._e)

            if left == self._n:
                return self._n

            left += self._size
            sm = self._e

            first = True
            while first or (left & -left) != left:
                first = False
                while left % 2 == 0:
                    left >>= 1
                if not f(self._op(sm, self._d[left])):
                    while left < self._size:
                        left *= 2
                        if f(self._op(sm, self._d[left])):
                            sm = self._op(sm, self._d[left])
                            left += 1
                    return left - self._size
                sm = self._op(sm, self._d[left])
                left += 1

            return self._n

        def min_left(self, right: int,
                    f: typing.Callable[[typing.Any], bool]) -> int:
            assert 0 <= right <= self._n
            assert f(self._e)

            if right == 0:
                return 0

            right += self._size
            sm = self._e

            first = True
            while first or (right & -right) != right:
                first = False
                right -= 1
                while right > 1 and right % 2:
                    right >>= 1
                if not f(self._op(self._d[right], sm)):
                    while right < self._size:
                        right = 2 * right + 1
                        if f(self._op(self._d[right], sm)):
                            sm = self._op(self._d[right], sm)
                            right -= 1
                    return right + 1 - self._size
                sm = self._op(self._d[right], sm)

            return 0

        def _update(self, k: int) -> None:
            self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])

    n = int(input())
    a = list(map(int,input().split()))

    def op(a, b):
        return (min(a[0], a[1] + b[0]), a[1] + b[1])

    r = 0
    data = []
    for _ in range(n):
        data.append([1, 1])
    s = SegTree(op, (float("inf"), 0), data)

    ans = 0

    for l in range(n):
        while r <= n - 1 and s.prod(0, r - l)[0] >= 0:
            x = s.get(a[r] - 1)[0]
            s.set(a[r] - 1, (x - 1, x - 1))
            r += 1
            
        ans = max(ans, r - l - 1)
        if r == n:
            if s.prod(0, r - l)[0] >= 0:
                ans = max(ans, r - l)
            break
        x = s.get(a[l] - 1)[0]
        s.set(a[l] - 1, (x + 1, x + 1))
    print(ans)
main()

Java

import java.io.*;
import java.util.*;

class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer;

        int leftIndex = 0;
        int maxLength = 0;
        int arraySize = Integer.parseInt(bufferedReader.readLine());
        tokenizer = new StringTokenizer(bufferedReader.readLine());
        int[] dataArray = new int[50001];
        int[] freqArray = new int[50001];
        for (int idx = 0; idx < arraySize; ++idx) {
            dataArray[idx] = Integer.parseInt(tokenizer.nextToken());
        }
        for (int rightIndex = 0; rightIndex < arraySize; ++rightIndex) {
            updateFrequency(freqArray, 1, dataArray[rightIndex], 1);

            int currentLength = rightIndex - leftIndex + 1;
            while (!validate(freqArray, currentLength)) {
                updateFrequency(freqArray, 1, dataArray[leftIndex], -1);
                ++leftIndex;
                --currentLength;
            }
            maxLength = Math.max(maxLength, currentLength);
        }
        System.out.println(maxLength);
        bufferedReader.close();
    }

    private static void updateFrequency(int[] array, int start, int value, int increment) {
        for (int idx = start; idx <= value; ++idx) {
            array[idx] += increment;
        }
    }

    private static int computeSum(int[] array, int start, int end) {
        return java.util.Arrays.stream(array, start, end + 1).sum();
    }

    private static boolean validate(int[] freqArray, int currentLength) {
        for (int idx = 1; idx <= currentLength; ++idx) {
            if (freqArray[idx] < currentLength - idx + 1)
                return false;
        }
        return true;
    }

}