読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.9 モンスターのレベル上げ

問題はこちら
No.9 モンスターのレベル上げ - yukicoder

各戦闘でこちらが出すのがモンスターは「レベルが最小のもの」→「そのうち戦闘回数が最小のもの」なので、これは「(レベル×(大きな数)+戦闘回数)が最小のもの」と考えることが出来る。
戦闘回数は高々Nなので、「(大きな数)」の部分はそれより大きな値を取れば良い。

int main(){
	int a[2000],b[2000],t[2000],i,j,k,p,n,m,M;
	scanf("%d",&n);
	for(i=0;i<n;i++)scanf("%d",a+i);
	for(i=0;i<n;i++)scanf("%d",b+i);
	M=n;
	for(i=0;i<n;i++){
	//i番目から戦闘を始めることにする
		for(j=0;j<n;j++)t[j]=a[j]*2000;
		for(j=0;j<n;j++){
		//実際に戦闘
			for(p=k=0;k<n;k++)if(t[k]<t[p])p=k;
			//次に先頭に出すべきは何番目か探す
			//「毎回ソートして先頭を取り出す」とかやると流石にTLE
			t[p]+=b[(i+j)%n]/2*2000+1;
		}
		for(m=j=0;j<n;j++)m=fmax(m,t[j]%2000);
		if(M>m)M=m;
	}
	printf("%d",M);
	return 0;
}

nとAとBをまとめて1つの配列に読み込むことにする
その他自明な短縮をして

a[4000],t[2000],i,j,k,p,m,M;
main(n){
	for(;~scanf("%d",a+i++);n=*a);
	for(M=i=n;i--;M>m?M=m:0){
		for(k=n;k--;t[k]=a[k+1]*2e3);
		for(j=0;j<n;t[p]+=a[(i+j++)%n-~n]/2*2e3+1)for(p=k=0;k<n;k++)t[k]<t[p]?p=k:0;
		for(m=j=0;j<n;j++)m=fmax(m,t[j]%2000);
	}
	M=!printf("%d",M);
}

よく見るとpの初期化は要らないことが分かる(初めてのときはp=0であり、それ以降は0~n-1のいずれかの値をとっているので、初期化する必要が無い)
またmの代わりに、この時点では不要なkを用いることで変数を1つ減らせ、kが必要になった時の初期値は-1になっているので初期化も不要

a[4000],t[2000],i,j,k,M;
main(n){
	for(;~scanf("%d",a+i++);n=*a);
	for(M=i=n;i--;M>k?M=k:0){
		for(k=n;k--;t[k]=a[k+1]*2e3);
		for(j=0;j<n;t[p]+=a[(i+j++)%n-~n]/2*2e3+1)for(k=n;k--;t[k]<t[p]?p=k:0);
		for(j=n;j--;k=fmax(k,t[j]%2000));
	}
	M=!printf("%d",M);
}

さらによく睨むと、内側にある3つのループのうち、2番目でjが0からnに、3番目でnから0になっているので、上手くやればここも初期化をサボれそう

a[4000],t[2000],i,j,k,p,M;
main(n){
	for(;~scanf("%d",a+i++);n=*a);
	for(M=i=n;i--;M>k?M=k:0){
		for(k=n;k--;t[k]=a[k+1]*2e3);
		for(;j<n;t[p]+=a[(i+j++)%n-~n]/2*2e3+1)for(k=n;k--;t[k]<t[p]?p=k:0);
		for(;j;k=fmax(k,t[--j]%2000));
	}
	M=!printf("%d",M);
}

236B
最初のn=*aを除いてnは6回登場するので、*aを直に使っても±0になる