問題はこちら
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になる