公式

E - Bowls and Beans 解説 by en_translator


First, we may assume that we always choose the rightmost bowl containing one or more beans.
Reason: if we want to move beans from a bowl and then from another bowl to its right, we may freely swap the order of these operations.
Also, when moving beans, we do not need to distribute them to multiple bowls.
Reason: one can freely pick an operation that distributes beans to multiple bowls, and replace it with an operation of moving all the beans into one of the bowls.

Let us consider the problem based on these observations.
First, let us consider how many operations are required to move the leftmost beans to bowl \(0\).
Regarding moving beans, we have the following property:

Consider moving a bean consecutively. If we start from bowl \(r\) and perform operations \(k\) times, the bowls that the bean may end up forms a segment.
More precisely, there exists \(l\) such that the bean may belong to one of bowl \(l,l+1,\dots,r\).

When the leftmost beans are in bowl \(x\), one can find the minimum number of operations to move them to bowl \(0\) as follows:

  • Initially, the segment in which the beans may exist is \([x,x]\).
  • If the segment in which the beans may exist is \([l,r]\) after \(k\) moves, the segment in which the beans may exist after \((k+1)\) moves is \([{\rm min}_{i=l}^{r} (i-C_i) , r]\).
  • Repeat this until the beans can reach bowl \(0\).

This way, the number of operations required to move the leftmost beans has been found.
How can we consider the number of operations required for the other beans?
In this case, it is sufficient to move the first bowl to its left with a bean in it, because, once the beans reach the next bowl to the left with a bean, one can consider the beans together as one bean to forget about the beans.

The maximum number of operations required is at most \((N-1)\) times (which can be done by successively removing beans from the rightmost bowl), so the answer is at most \((N-1)\). Even with a naive simulation, the problem can be solved in \(O(N^2)\) time.
Using a segment tree allows an optimization up to \(O(N \log N)\) time.

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  vector<int> c(n),a(n);
  for(int i=1;i<n;i++){cin >> c[i];}
  for(int i=1;i<n;i++){cin >> a[i];}
  int res=0;
  int pre=0;
  for(int i=1;i<n;i++){
    if(a[i]){
      int l=i,r=i;
      while(pre<l){
        res++;
        int nl=l;
        for(int j=l;j<=r;j++){
          nl=min(nl,j-c[j]);
        }
        l=nl;
      }
      pre=i;
    }
  }
  cout << res << "\n";
  return 0;
}

投稿日時:
最終更新: