E - Bowls and Beans Editorial
by
physics0523
まず、豆の移動は「現在最も後ろにある豆を動かす」を繰り返すものとして構いません。
理由: 前にある豆を先に動かしてから後ろにある豆を動かすとき、これらの操作を逆にしても損しません。
また、豆を動かす際、複数の茶碗に分けて入れる必要もありません。
理由: 豆を分けて入れる操作をひとつ選び、豆をどこかひとつにまとめて入れても損しません。
このもとで本問題を考察しましょう。
まず、一番前にある豆を茶碗 \(0\) に落とすまでに何手かかるかを考えます。
豆を移動するにあたって、次の性質が成り立ちます。
ある豆を連続して移動させることを考える。
茶碗 \(r\) から始めて \(k\) 手連続で豆を移動させると、移動後に豆が存在しうる茶碗は区間を成す。
厳密には、ある \(l\) が存在して、移動後に豆が存在しうるのは茶碗 \(l,l+1,\dots,r\) となる。
一番前にある豆が茶碗 \(x\) にあるとき、この豆を茶碗 \(0\) に移動させるための最短手数は次のように求められます。
- 最初、豆が存在しうる茶碗の区間は \([x,x]\) である。
- \(k\) 手で豆が存在しうる茶碗の区間が \([l,r]\) のとき、 \(k+1\) 手で豆が存在しうる茶碗の区間は \([{\rm min}_{i=l}^{r} (i-C_i) , r]\) となる。
- これを、豆が茶碗 \(0\) に到達しうる状態になるまで続ける。
これで、一番前にある豆に必要な移動回数は分かりました。
では、一番前にある豆以外に必要な移動回数はどう考えれば良いでしょうか?
この場合、豆を「ひとつ前の豆が存在する茶碗」まで到達させればよいです。というのも、その豆を動かしてひとつ前の豆が存在する茶碗まで到達させれば、そこにある豆とまとめてひとつの豆だと思って動かせばその豆のことを忘れることができます。
移動回数は高々 \(N-1\) 回 (一番後ろの茶碗から豆を除去することを繰り返せば達成可能です) であることに注意すると答えは高々 \(N-1\) となり、愚直にシミュレーションしても時間計算量 \(O(N^2)\) でこの問題に正解できます。
segment tree 等で高速化すれば時間計算量 \(O(N \log N)\) で解けます。
実装例 (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;
}
posted:
last update: