JOI 2025/2026 二次予選 : F - 船 (Ship)

解けはしたけど、想定解かわからん。
https://atcoder.jp/contests/joi2026yo2/tasks/joi2026_yo2_f

問題

N個の船が並んでおり、それらの位置A[i]が与えられる。Aは昇順である。
各船を彩色することを考える。ただし以下を満たさなければならない。

• 各色の船は、0個または２個以上でなければならない。
• 同色の船同士の座標は、等差数列を成さなければならない。

条件を満たす彩色は可能か。可能なら、同色の船の間の距離の最小値の最大値を答えよ。

解法

Nが偶数の場合、i番とi+(N/2)番の船を同色にすればよい。

Nが奇数の場合、１色だけ３個の船を塗り、残りの船は、Nが偶数の場合と同様に色を塗ればよい。
３個同色にする船を総当たりしよう。これはO(N^2)で総当たりできる。
問題は、残った(N-3)個の船に対し、距離の最小値の最大値を求めることである。

f(a,b,k) := 区間[a,a+(1<

int N;
int A[3553];
map<int,int> M;
int dp[3553][3553][12];

int hoge(vector<pair<int,int>> V) {
	queue<pair<int,int>> L,R;
	int Llen=0,Rlen=0;
	int lef=(N-3)/2;
	FORR2(a,b,V) {
		if(Llen<lef) {
			int len=min(lef-Llen,b);
			L.push({a,len});
			Llen+=len;
			a+=len;
			b-=len;
		}
		if(b) {
			R.push({a,b});
			Rlen+=b;
		}
	}
	assert(Llen==Rlen);
	int mi=1<<30;
	while(L.size()&&R.size()) {
		if(L.front().second==0) {
			L.pop();
			continue;
		}
		if(R.front().second==0) {
			R.pop();
			continue;
		}
		int d=0;
		while(1<<(d+1)<=min(L.front().second,R.front().second)) d++;
		mi=min(mi,dp[L.front().first][R.front().first][d]);
		L.front().first+=1<<d;
		R.front().first+=1<<d;
		L.front().second-=1<<d;
		R.front().second-=1<<d;
	}
	return mi;
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		M[A[i]]=i;
	}
	
	if(N%2==0) {
		int mi=1<<30;
		FOR(i,N/2) mi=min(mi,A[i+N/2]-A[i]);
		cout<<mi<<endl;
		return;
	}
	
	FOR(y,N) FOR(x,y) dp[x][y][0]=A[y]-A[x];
	FOR(i,11) {
		FOR(y,N) FOR(x,y) {
			dp[x][y][i+1]=dp[x][y][i];
			if(y+(1<<i)<N) dp[x][y][i+1]=min(dp[x][y][i+1],dp[x+(1<<i)][y+(1<<i)][i]);
		}
	}
	
	int ret=-1;
	FOR(y,N) FOR(x,y) if(M.count(A[y]*2-A[x])) {
		int z=M[A[y]*2-A[x]];
		int tmp=A[y]-A[x];
		vector<pair<int,int>> V;
		V.push_back({0,x});
		V.push_back({x+1,y-x-1});
		V.push_back({y+1,z-y-1});
		V.push_back({z+1,N-(z+1)});
		ret=max(ret,min(tmp,hoge(V)));
	}
	cout<<ret<<endl;
}

解法

Nが3500って微妙に大きいな。2000じゃ3000じゃないのは何か意味があるのかな。