PKU 2381 Random Gap
http://poj.org/problem?id=2381
線形合同法で使われるパラメーターが入力されるので、生成される乱数をソートして、最も間隔の広いものを答えろというような問題。
C++で書いたらTLEで、入力を書き換えてもそこはほぼ関係してこないし、全然間に合わなさそうだったので、javaに移行しました。
が、MLEをくらいまくって、ちょっと調べるとBoolean型が1bitじゃないと知って唖然としました。
途中でO(mlog(m))からO(m)に変えたので、javaで省メモリにする方法を調べなくても良かったんじゃないだろうかと今思っています。
import java.util.*; public class Main{ static BitSet app =new BitSet(16000000); public static void main(String[] args){ Scanner cin=new Scanner(System.in); long a,c,m,r; a=cin.nextInt(); c=cin.nextInt(); m=cin.nextInt(); r=cin.nextInt(); while(true){ if(app.get((int)r))break; app.set((int)r); r=(a*r+c)%m; } int bidx=0; int ans=0; for(int i=0;i<m;++i){ if(app.get(i)){ bidx=i; break; } } for(int i=bidx+1;i<m;++i){ if(app.get(i)){ ans=Math.max(ans,i-bidx); bidx=i; } } System.out.println(ans); } }