AOJ2337 ねこ鍋改造計画(仮)

ねこ鍋。良問だという話を聞いたので考えてみたらごり押し解を思いついたので実装した。

(cuteのmax)-(cuteのmin)で二分探索することを考える。そうすると、O(N)個の区間でナップサックをして、取れる重さの値をオスメスともに列挙できればよいことがわかる。

前処理として、cuteの最小値を固定してそれ以上のcuteのやつだけでナップサックをすることを考える。

DP[cuteの最小値のねこのindex][現在みているねこのindex][現在の重さ]: この状態が実現できるかのbool値

とする。このままだと25億くらいになってTLEするはず。しかしDPの式がシンプルでビット演算だけでかけるので、64倍高速化をする。

この前処理をしておけばあとは適当に値を参照しながら二分探索するだけかと思いきや、この前処理のテーブルを全部保存しておくとMLEする。

仕方がないのでcuteのminを全部ためし、その中でcuteのmaxで二分探索することにする。こうするとDPを毎回1個ずつ計算すればいいのでメモリが足りる。

結局O(WN^2+WNlog N)だが、WN^2には定数倍1/64がかかるので600msくらいで通った。

#include<stdio.h>
#include "stdafx.h"
#include<vector>
#include<algorithm>
#include<stdlib.h>
#include<math.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int>pii;
ull dpa[501][160];
ull dpb[501][160];
int na,nb,gen;
vector<pii>va,vb,vec;
int calc(int med,int sta,int stb)
{
	int fa=-1,fb=-1;
	for(int j=0;j<na;j++)
	{
		if(j>=sta&&vec[med].first>=va[j].first)fa=j;
	}
	for(int j=0;j<nb;j++)
	{
		if(j>=stb&&vec[med].first>=vb[j].first)fb=j;
	}
	if(fa==-1||fb==-1)
	{
		return 2000000000;
	}
	int a[10250],b[10250];
	for(int j=0;j<160;j++)
	{
		for(int k=0;k<64;k++)
		{
			a[j*64+k]=((dpa[fa+1][j]&(1ULL<<(63-k)))!=0);
			b[j*64+k]=((dpb[fb+1][j]&(1ULL<<(63-k)))!=0);
		}
	}
	int mi=2000000000;
	int na=-1000000,nb=-1000000;
	for(int j=1;j<=gen;j++)
	{
		if(a[j])na=j;
		if(b[j])nb=j;
		if(na>0)mi=min(mi,abs(na-nb));
	}
	return mi;
}
int main()
{
	scanf("%d%d%d",&na,&nb,&gen);
	for(int i=0;i<na;i++)
	{
		int za,zb;
		scanf("%d%d",&za,&zb);
		va.push_back(make_pair(zb,za));
		vec.push_back(make_pair(zb,za));
	}
	for(int i=0;i<nb;i++)
	{
		int za,zb;
		scanf("%d%d",&za,&zb);
		vb.push_back(make_pair(zb,za));
		vec.push_back(make_pair(zb,za));
	}
	sort(va.begin(),va.end());
	sort(vb.begin(),vb.end());
	sort(vec.begin(),vec.end());
	int mini=2000000000;
	for(int i=0;i<vec.size();i++)
	{
		for(int j=0;j<501;j++)for(int k=0;k<160;k++)dpa[j][k]=dpb[j][k]=0;
		int sta=-1,stb=-1;
		for(int j=0;j<va.size();j++)
		{
			if(vec[i].first<=va[j].first)
			{
				sta=j;
				break;
			}
		}
		for(int j=0;j<vb.size();j++)
		{
			if(vec[i].first<=vb[j].first)
			{
				stb=j;
				break;
			}
		}
		if(sta==-1||stb==-1)continue;
		dpa[sta][0]=dpb[stb][0]=1LL;
		dpa[sta][0]<<=63;
		dpb[stb][0]<<=63;
		for(int j=sta;j<na;j++)
		{
			int cs=va[j].second;
			for(int k=0;k<160;k++)
			{
				dpa[j+1][k]|=dpa[j][k];
				if(k+cs/64<160)dpa[j+1][k+cs/64]|=(dpa[j][k]>>(ull)(cs%64));
				if(k+cs/64+1<160)dpa[j+1][k+cs/64+1]|=(dpa[j][k]<<(ull)(64-cs%64));
			}
		}
		for(int j=stb;j<nb;j++)
		{
			int cs=vb[j].second;
			for(int k=0;k<160;k++)
			{
				dpb[j+1][k]|=dpb[j][k];
				if(k+cs/64<160)dpb[j+1][k+cs/64]|=(dpb[j][k]>>(cs%64));
				if(k+cs/64+1<160)dpb[j+1][k+cs/64+1]|=(dpb[j][k]<<(64-cs%64));
			}
		}
		int beg=i,end=na+nb-1;
		for(;;)
		{
			int med=(beg+end)/2;
			int mi=calc(med,sta,stb);
			if(mi>vec[med].first-vec[i].first)beg=med+1;
			else end=med;
			if(beg==end)
			{
				int k1=beg,k2=beg-1;
				mini=min(mini,max(vec[k1].first-vec[i].first,calc(k1,sta,stb)));
				if(k2<0)break;
				mini=min(mini,max(vec[k2].first-vec[i].first,calc(k2,sta,stb)));
				break;
			}
		}
	}
	printf("%d\n",mini);
}