SRM 585 & おふろについて

①するめの話題

SRM585に参加しました。久しぶりの参加です。

250:数える問題。
DPする。

public class TrafficCongestion{
	public int theMinCars(int a){
		int MOD=1000000007;
		int dp[]=new int[1000001];
		dp[0]=dp[1]=1;
		int val=0;
		for(int i=2;i<=a;i++){
	
			val=(val+dp[i-2])%MOD;		
			dp[i]=(1+val*2)%MOD;
		}
		return dp[a];
	}
}

500:数える問題。
DPする。

public class LISNumber{
	public int count(int []a,int b){
		int dp[][]=new int[a.length][1300];
		int MOD=1000000007;
		int C[][]=new int[1300][1300];
		C[0][0]=C[1][0]=C[1][1]=1;
		for(int i=2;i<1300;i++){
			C[i][0]=C[i-1][0];
			C[i][i]=C[i-1][i-1];
			for(int j=1;j<i;j++){
				C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
			}
		}
		dp[0][a[0]]=1;
		int S=a[0];
		for(int i=1;i<a.length;i++){
			
			for(int j=1;j<b+1;j++){
				for(int k=1;k<=j;k++){
					if(dp[i-1][k]==0||j-k>a[i])continue;
					int B=a[i]-j+k;
					dp[i][j]=(int)(dp[i][j]+(long)dp[i-1][k]*C[k][B]%MOD*C[S-(k-B)+j-k][j-k]%MOD)%MOD;
					
				}
			}
			S+=a[i];
		}
	//	for(int i=0;i<a.length;i++)
		//	for(int j=1;j<=b;j++)System.out.println(i+" "+j+": "+dp[i][j]);
		return dp[a.length-1][b];
	}
}

Challenge:
事前に自分の1000は落ちます、と言ってた人のコードを落とす。250で1回ミスる。

System Test:通る
235.96+302.63 + 50 !!!!!!-25!!!!!! = 563.59(8th)
Rating: 2273 -> 2398 ( +125 )

初の1桁順位。2400まではいけるっしょ、と言ってたけど本当に2400寸前まで来てしまった…。これからもモリモリレート上げます。
数え上げ得意なので数え上げが出るとレート爆上がりするし作問も数え上げに偏る

②ICPCの話題

いろいろあって6位(絶望)、校内4位(許容)で普通枠落ちてました。が、なんとかワイルドカードをもらいました。これで会津にいけます。ICPCも練習せねばなあ。
ちなみにEのEPSまわりでずっと悩んでいました(死)

③おふろについて
浴槽につまづいて変な入り方をしてしまうと抜け出せなくなります。

縦幅は人一人分あるが横幅はとても狭い。浴槽に背を向けて後退しないようにしましょう。