第五回 アルゴリズム実技検定 : M - 棒の出荷

この回は終盤少し難しめか。
https://atcoder.jp/contests/past202012-open/tasks/past202012_m

問題

細長い棒があり、(N-1)個の切込みの位置が与えられる。
一部の切込みで棒を切断し、各棒の長さがL以下となるようにしたい。
一番短い棒の長さの最大値を求めよ。

解法

一番短い棒の長さvを二分探索する。

dp(n) := n個目の切込みで棒を切断したとき、それ以降の位置で条件を満たす切断が可能かの真偽値
とする。dp(N)=Trueからnの大きい順に求めて行き、最終的にdp(0)=Trueにできるか判定すればよい。

S(n) := n個目の切込みの位置
とすると、S(n)+v≦S(m)≦S(n)+Lとなるmのうち、１個でもdp(m)=Trueならdp(n)=Trueになる。
よってBITなど使って区間内のdp(n)の累積和を取れるようにしておけばよい。

int N;
ll L,A[202020],S[202020];

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<int,20> bt;
int dp[202020];

int ok(ll v) {
	if(v>L) return 0;
	ZERO(bt.bit);
	ZERO(dp);
	dp[N]=1;
	bt.add(N,1);
	for(int i=N-1;i>=0;i--) {
		ll a=S[i]+v;
		ll b=S[i]+L+1;
		int x=lower_bound(S,S+N+1,a)-S;
		int y=lower_bound(S,S+N+1,b)-S;
		dp[i]=(bt(y-1)-bt(x-1))>0;
		bt.add(i,dp[i]);
	}
	return dp[0];
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>L;
	FOR(i,N) {
		cin>>A[i];
		S[i+1]=S[i]+A[i];
	}
	ll cur=0;
	for(i=50;i>=0;i--) if(ok(cur+(1LL<<i))) cur+=1LL<<i;
	cout<<cur<<endl;
}

まとめ

棒の切断系問題、二分探索解が異様に多い気がする。